Большая сложность основных арифметических операций

Question

Что такое сложность Big-O для распространенных алгоритмов основных арифметических операций, таких как умножение, квадратный корень, логарифм, скалярное и матричное произведение?

Существуют ли экзотические алгоритмы, которые более эффективны с точки зрения Big-О сложность, но не очень распространена в практических решениях (например, не реализована в популярных программных библиотеках)?

Answer 1

См. http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

---

Матричное произведение квадратных матриц:

• O (N ³ ) (наивный метод)
• O (N ^2,81 ) ( Алгоритм Штрассена ).

Существует также O (N ^2,38 ) Алгоритм Копперсмита-Винограда , но я не думаю, что он широко распространен из-за огромной скрытой постоянной.

Умножение Big-Int :

• Наивный: O (n ² )
• Быстрое преобразование Фурье: O (n log n log log n) ( алгоритм Шёнхаге-Штрассена ).

Есть также n log n & middot; Алгоритм 2 ^{O (log * n)} , опубликованный в 2008 году, но он был слишком новым для широкого распространения.

---

Обычно наивный метод достаточно хорош для ввода нормального размера.

Answer 2

Вы будете рассматривать большинство простых операций как O (1), потому что ваш размер ввода обычно фиксирован (то есть 32- или 64-битный).

В нормальных условиях ваша платформа будет выполнять точно такую ​​же операцию для умножения, квадратного корня, логарифма и т. Д. Независимо от «размера» вашего ввода (т. Е. Int a = 0; и int b = Int32. 32-разрядные целые числа).

Это становится интересным, когда вы начинаете смотреть на матрицы или представлять числа произвольной точности, но кто-то уже связал резюме в Википедии, поэтому я не буду вдаваться в подробности.

Только не используйте Schönhage – Strassen для умножения "нормальных" маленьких чисел. Это заставит меня плакать. Тот факт, что алгоритм равен O ( n ² ), не означает, что он плохой, особенно когда n почти всегда равен 2 ⁵ или 2 ⁶ .

Answer 3

Операции не имеют сложности, алгоритмы.Например, существуют различные алгоритмы квадратного корня, и они будут иметь разную сложность.

Answer 4

Взгляните на BigInteger , на целые числа произвольной длины. У всего теперь есть стоимость, с точки зрения размера входа, который является числом битов (обычно O(log K) бит для числа K). Я буду использовать N для количества бит ниже.

Например, сложение и вычитание теперь O( N ). Умножение либо O( N^2 ) (наивное), либо O( n (log n)^(2+epsilon) ) с БПФ.

Другие алгоритмы включают функцию «power», которая требует умножения O( N ). (кроме того, что теперь у каждого умножения есть стоимость!)

И есть дополнительные сложности для BigDecimals, который является десятичным эквивалентом произвольной длины, и помимо некоторых более базовых операций, некоторые вещи также более интересны (особенно если вы хотите выяснить, насколько хочу). Вы можете взглянуть на реализацию Java.

Answer 5

Квадратный корень и логарифм могут быть реализованы различными способами, что значительно влияет на сложность (судя по требуемой точности).

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

Более популярно, что они, кажется, реализуются своими последовательными определениями.Повторяйте или повторяйте оператор в течение нескольких раундов, пока не достигнете необходимой точности.Здесь число раундов может стать очень большим, так как требуется большая точность, а также на сами вычисления влияет повышенная точность.

Answer 6

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

Answer 7

Существует алгоритм типа Фурье, который также выполняет целочисленное умножение ( Schonhage-Strassen )

Я думал, что существует версия алгоритма Штрассена, которая работает немного лучше, чем обычно для целочисленного умножения, но теперь, когда я думаю об этом, получается, что он такой же, как и простой ...

Сложение и вычитание в значительной степени, просто сложение и вычитание. Деление и квадратный корень, вероятно, интересны, хотя ...

ТАКЖЕ: Обратите внимание, что до сих пор все говорили об арифметике INTEGER. Как только вы попали в поплавки / удвоения, все ставки сняты. Тогда вы попадаете в мир численного анализа , и это целое поле его собственного ...