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