Комментарии 17
Составлю свой список:
BSP дерево, октодерево (позволяют альтернативную реальность рисовать)
Очередь с приоритетом и основанная на ней пирамидальная сортировка (не требует дополнительной памяти, всегда быстрая, но не устойчивая)
Сортировка слиянием (работает на больших объёмах данных)
Префиксное и суффиксное деревья (структуирование информации)
Бинарный поиск (удобно искать место перебитого кабеля, например)
Значит ли это, что Карацуба не "заметил интересную особенность" для своего алгоритма перемножения, а лишь использовал наработки Гаусса?
Подушню:
а любые два числа, которое, имеют в общем случае длину n бит, а результат умножения может иметь длину 2n бит.
Так и напрашивается продолжение, в виде "где n - натуральное число", потому что у вас это n на протяжении всей статьи постоянно всплывает. Но этого продолжения нет...
В этом дополнении нет необходимости, потому что мы договорились, что n — длина строки-записи числа. Отсюда можно вывести, что n не может быть нецелым или отрицательным.
Нет, вы причину со следствием путаете. Из этого можно много чего вывести. И что n может быть равно 0 (а на самом деле нет, поскольку для хранения нуля, нам все равно нужен, минимум, один бит). И что 0 можно представить в двоичном формате в виде строки нулей, длиной 1 экзабайт... Но корректно оперировать значениями n, мы можем в случае когда в условии прописаны все эти допустимые значения.
Натуральные числа используются для подсчёта количества неделимых предметов, таких, как цифры в записи числа. Понятно, что если n — длина записи числа, то n — натуральное.
Нет, вы причину со следствием путаете. Из этого можно много чего вывести. И что n может быть равно 0 (а на самом деле нет
Можно вывести (то, что n — не натуральное число) или нет? Если можно, покажите, как.
И что 0 можно представить в двоичном формате в виде строки нулей, длиной 1 экзабайт
И что с того? 2^60 тоже натуральное число.
Натуральные числа используются для подсчёта количества неделимых предметов, таких, как цифры в записи числа.
Нет. Число цифр в записи числа - не неделимая сущность. Например - средняя длина строки может быть, условно, 5.2 байта. Я же понятия не имею, в каком контексте вы собираетесь это n дальше использовать, поэтому и жду соответствующих уточнений.
Понятно, что если n — длина записи числа, то n — натуральное.
Не понятно. Вы вот уверены, скажем, что длина числа Пи (или любого другого трансцендентного, иррационального и даже некоторых рациональных дробей) выражается натуральным числом?))
Можно вывести (то, что n — не натуральное число) или нет? Если можно, покажите, как.
Я понятия не имею - я же как раз об этом. Я не понимаю в каком контексте тут "n" и "длина записи". Вот стразу всплывает вопрос с нулём. Может ли n = 0 - это уже какой-то философский вопрос получается. Длина записи равна нулю -> значит записывать по сути нечего, и числа, как такового, попросту не существует. Но у нас же статья в контексте вычислительных алгоритмов. И здесь даже для хранения null необходимо выделить ячейку памяти. Поэтому мне сразу хочется понимать этот контекст уточнением "где n..."
И что с того? 2^60 тоже натуральное число.
Да даже число Грэма - натуральное)) Но вот у меня тот же вопрос - и что с того?
К чему это уточнение про "а результат умножения может иметь длину 2n бит."? А может и не иметь)) Длина результата вообще довольно слабо коррелирует с длиной множителей.
"Длина строки" и "средняя длина строки" — разные понятия, измеряются в разных единицах, путать их — большая ошибка.
Вы вот уверены, скажем, что длина числа Пи
Автор не упомянул, что в его статье речь только о целых числах. Пожалуй, с этого и надо было начинать критику статьи. Сложно догадаться о таком допущении.
К чему это уточнение про "а результат умножения может иметь длину 2n бит."
Надо читать как "не более 2n" (в предположении, что не записываем ведущие нули).
Длина результата вообще довольно слабо коррелирует с длиной множителей
Сильно коррелирует, если договориться о записи без ведущих нулей.
Кстати, определять асимптотику для рекурсии вроде T(n) = 3T(n/2) + O(n) можно через мастер-теорему
Обычно этот алгоритм называют именем Карацубы - https://en.wikipedia.org/wiki/Karatsuba_algorithm.
Ну и есть еще более быстрые алоритмы для больших .
Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 1