Почему умножение O (n^2)?

Question

Привет, я узнал о Big-O и задавался вопросом, почему умножение O (n^2). Кажется, я знаю, почему, но я просто не уверен. Это из-за того, как долго работает умножение? Я знаю, что добавление - это линейное время O (n), и если мы выполняем двоичное умножение, мы сначала умножим все биты и сдвинем его. После того, как мы закончим смещение и умножение всех бит, мы сделаем дополнение. Поэтому я предполагаю, что рекурсивный вызов умножения равен O (n), и добавление результата будет O (n). Поэтому расчесывание двух времени выполнения даст нам O (n^2). Это правильно или я ошибаюсь? Edit: Так что я думаю, что я спрашиваю, почему это класс школы умножения O (N^2)

Благодаря

Answer 1

Прежде всего, умножая , что? Вы умножаете, матрицы? Вы умножаете, полиномы? Вы умножаете целые числа? Вы умножаете числа с плавающей запятой? Вы умножаете, целые числа по модулю простого?

Предполагая, что вы говорите о умножении целых чисел, как вы узнали в начальной школе -

The (наивный) алгоритм начальной школы является O(n^2), потому что, когда вы Умножая n -значный номер с помощью m значного числа, используя его, вы в итоге получаете сумму m сдвинутых копий цифры n, которую вы должны добавить. Это включает в себя запись примерно n+m на m сетку цифр, а затем сложение всех этих чисел, поэтому вам нужно около n^2 времени и пространства над всеми в этом методе.

Однако существует много методов лучшего умножения, таких как размножение русского крестьянства, а для чрезвычайно больших чисел самые быстрые методы достигают примерно O(n log n) времени. Эти методы основаны на быстром преобразовании Фурье и довольно сложны.

Никто не знает, как доказать, что умножение невозможно сделать в O(n) времени, теоретически возможно, что это может быть.

Так что, когда вы спросите

Почему умножение O (N^2)?

ответ, его нет, и что именно это, мы не знаем, его где-то между O(n) и O(n log n). Для него есть только определенные алгоритмы: O(n^2).