Большая сложность O основных арифметических операций
Какова Большая-O сложность для широко распространенных алгоритмов основных арифметических операций как умножение, квадратный корень, логарифм, скалярное и матричное произведение?
Есть ли экзотические алгоритмы, которые более эффективны, с точки зрения Большой-O сложности, но не очень широко распространены в практических решениях (например, не реализованные в популярных библиотеках программного обеспечения)?
6 ответов
См. http://en.wikipedia.org/wiki/Computational_complexity_of_mat Mathematical_operations
Матричное произведение квадратных матриц:
- O (N 3 ) (простой метод)
- O ( N 2,81 ) ( алгоритм Штрассена ).
Существует также алгоритм O (N 2.38 ) Копперсмит – Винограда , но я не думаю, что он широко распространен из-за огромной скрытой константы.
Умножение Big-int :
- Наивно: O (n 2 )
- Основанное на быстром преобразовании Фурье: O (n log n log log n) ( Schönhage –Алгоритм Штрассена ).
Существует также алгоритм n log n · 2 O (log * n) , опубликованный в 2008 году, но он был слишком новым, чтобы получить широкое распространение.
Обычно простого метода достаточно для ввода нормального размера.
У операций нет сложности, у алгоритмов есть. Например, существуют разные алгоритмы извлечения квадратного корня, и они будут иметь разную сложность.
Вы будете рассматривать самые простые операции как O (1), потому что ваш размер ввода обычно фиксированный (то есть 32- или 64-битный).
В нормальных условиях ваша платформа будет выполнять точно такую же операцию для умножения, извлечения квадратного корня, логарифма и т. Д., Независимо от «размера» вашего ввода (т.е. int a = 0; и int b = Int32.MaxValue оба 32-битные целые числа).
Это становится интересным, когда вы начинаете смотреть на матрицы или числа произвольной точности, но кто-то уже связал резюме Википедии, поэтому я не буду вдаваться в подробности.
Только не используйте Schönhage – Strassen для умножения «нормальных» маленьких чисел. Это заставит меня плакать. Тот факт, что алгоритм равен O ( n 2 ), не означает, что он плохой - особенно когда n почти всегда равно 2 5 или 2 ] 6 .
Квадратный корень и логарифм могут быть реализованы различными способами, что сильно влияет на сложность (если судить по требуемой точности).
Если они реализованы с помощью таблиц поиска (и какой-то интерполяции), требования к памяти действительно возрастают, поскольку требуется большая точность, но сложность заключается в поиске значения в массиве и, возможно, применении интерполяции.
Более популярно они, кажется, реализуются с помощью определений их серий. Повторяйте или повторяйте оператор несколько раундов, пока не достигнете требуемой точности. Здесь количество раундов может стать очень большим, поскольку требуется большая точность, а также на сами вычисления влияет повышенная точность.
Существует алгоритм типа Фурье, который также выполняет целочисленное умножение (Schonhage-Strassen)
Я думал, что существует версия алгоритма Штрассена, которая выполняет целочисленное умножение немного лучше, чем обычно, но теперь, когда я думаю об этом, этот алгоритм оказывается таким же прямым...
Сложение и вычитание - это, в общем-то, просто сложение и вычитание. Деление и квадратный корень, вероятно, интересны...
АЛСО: Обратите внимание, что до сих пор все говорили об арифметике INTEGER. Как только вы доберетесь до плавающих/двойных чисел, все ставки будут сделаны. Затем вы попадаете в мир численного анализа, а это уже целая область...
Взгляните на BigInteger для целых чисел произвольной длины. Теперь у всего есть стоимость в терминах размера входных данных, которая представляет собой количество битов (обычно O (log K) бит для числа K ). Я буду использовать N для количества битов ниже.
Например, добавление d теперь вычитание O (N) . Умножение выполняется либо O (N ^ 2) (наивный), либо O (n (log n) ^ (2 + epsilon)) с БПФ.
Другие алгоритмы включают «степенную» функцию, которая требует умножения O (N) . (за исключением того, что теперь каждое умножение имеет свою стоимость!)
И есть дополнительные сложности для BigDecimals, который является десятичным эквивалентом произвольной длины, и помимо некоторых из более простых операций, некоторые из вещей также более интересны (особенно если вы хотите выяснить, какая точность вам нужна). Вы можете взглянуть на реализацию Java.