Как деление в столбик учебника является O (n^2) алгоритм?
Предпосылка:
Эта страница Wikipedia предполагает, что вычислительная сложность деления в столбик "Учебника" является O (n^2).
Вычет:
Вместо того, чтобы брать два N-разрядных числа, если бы я беру одно N-разрядное число и одно m-digit число, затем сложность была бы O (n*m).
Противоречие:
Предположим, что Вы делитесь 100000000 (n цифры) 1 000 (m цифры), Вы добираетесь 100000, который делает шесть шагов для прибытия в.
Теперь, если Вы делитесь 100000000 (n цифры) 10 000 (m цифры), Вы добираетесь 10000. Теперь это делает только пять шагов.
Заключение:
Так, кажется, что порядок вычисления должен быть чем-то как O (n/m).
Вопрос:
Кто неправ, меня или Википедию, и где?
5 ответов
Вы ошибаетесь, потому что вы не считаете операции по каждой цифре. Вместо этого вы считаете, как если бы вы могли вычесть N-значное число в O (1). В общем, нельзя; требуется O (N).
Я думаю (не доказал, поэтому не уверен), что ваш вывод является истинным утверждением, но на самом деле он не следует из вашей посылки. Если все, что вы знаете, это то, что разделение двух n-значных чисел составляет O (n ^ 2), все, что вы можете вывести о n- и m-значном числе, это то, что это O (max (n, m) ^ 2), не то чтобы это O (n * m). Это потому, что n-значное число также может считаться n + 1-значным числом с ведущим 0, заменяя операцию той, сложность которой нам известна.
Например, который не равен O (n m): при использовании длинного умножения вычисление A ^ 2 + B ^ 2 равно O (n ^ 2), если A и B являются n-значными числами. Однако это не O (n m), если A - n цифр, а B - m цифр. Чтобы убедиться в этом, зафиксируем B = 1, следовательно, m = 1 и заметим, что вычисление A ^ 2 + 1 с помощью длинного умножения определенно не является O (log (A)) [*].
Ваше «противоречие» не противоречит ни вашей посылке, ни вашему выводу. Обозначение Big-O касается асимптотического поведения, когда что-то стремится к бесконечности. Тот факт, что f (3) = 12 для некоторой функции f, абсолютно ничего не говорит вам о пределах большого O для f. Даже если f (n) = 12 для всех нечетных n, это все равно ничего не говорит вам об оценках большого O, потому что вы не знаете, насколько быстро функция растет на четных числах. Наличие быстрых особых случаев не означает, что функция работает быстро.
[] На самом деле, я сам злоупотребил обозначениями. Если функция с двумя переменными f (n, m) равна O (n m), из этого не следует (как я предположил), что f (n, 1) равно O (n). Но из этого следует, что для достаточно большого m f (n, m) равно O (n), поэтому замените 1 на «некоторую большую константу или другое».
Попробуйте снова с числами вроде 12341234 и 43214321.
Big O - это предельная сложность для всех случаев, а не для особо простого.
Рассмотрим этот случай:
Сортировка массива
[1, 2, 3, 4, ....., 10000000]занимает ровно один шаг . Вряд ли~ nlognшагов, как можно было бы ожидать от оптимального алгоритма сортировки.
Недостаток вашей логики в том, что Big-O - это асимптотическая оценка всех входных данных. Вы не можете взять один простой ввод и вывести из него противоречие.
В книге Кормена говорится следующее: Рассмотрим обычный алгоритм "бумага и карандаш" для длинного деления: деление a на b, что дает коэффициент q и остаток r. Покажите, что этот метод требует O((1 + lg q) lg b) битовых операций.