Я читал, что такие операции, как сложение/вычитание, были линейным временем, а это умножение было n^2 раза. Почему это так?Почему умножение n^2 раза?
Не добавлено floor(log n) раз, когда n является меньшим операндом? Тот же аргумент относится к вычитанию и для умножения, если мы делаем программу для длительного умножения вместо суммирования целых чисел, не должна ли быть сложна floor(log a) * floor(log b), где a и b - операнды?
Ответ зависит от того, что такое «n». Когда говорят, что добавление O (n) и умножение (с наивным алгоритмом) - O (n^2), n - длина числа, либо в битах, либо в какой-либо другой единице. Это определение используется, поскольку арифметика произвольной точности реализуется как операции над списками «цифр» (не обязательно базовая 10).
Если n - это число, добавляемое или умноженное, сложность будет log n и (log n)^2 для положительного n, если числа хранятся в лог-пространстве n.
Наивный подход к умножению (к примеру) 273 x 12 расширяется из (используя распределительную правило) в качестве (200 + 70 + 3) x (10 + 2) или:
200 x 10 + 200 x 2
+ 70 x 10 + 70 x 2
+ 3 x 10 + 3 x 2
Идея такого упрощения является снижение умножений на то, что может быть сделано легко. Для вашей начальной школы математика, которая будет работать с цифрами, предполагая, что вы знаете таблицы времени от нуля до девяти. Для библиотек bignum, где каждая «цифра» может быть значением от 0 до 9999 (для удобства десятичной печати) применяются те же правила, что позволяет умножать числа менее 10 000 относительно постоянно).
Следовательно, если n - это количество цифр, сложность действительно O(n2), так как число «постоянных» операций имеет тенденцию к росту с помощью показателя «цифры».
Это верно, даже если ваше определение цифры немного отличается (например, значение от 0 до 9999 или даже является одной из двоичных цифр 0 или 1).