Что такое сложность Big-O для широко распространенных алгоритмов основных арифметических операций, таких как умножение, квадратный корень, логарифм, скалярный и матричный продукт?Большая сложность базовых арифметических операций
Существуют ли экзотические алгоритмы, которые более эффективны с точки зрения сложности Big-O, но не очень распространены в практических решениях (например, не реализованы в популярных библиотеках программного обеспечения)?
См http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
матричного произведения квадратных матриц:
Существует также O (N 2,38) Coppersmith–Winograd algorithm, но я не думаю, что это широко распространено в связи с огромной скрытой константой.
Big-ИНТ умножение:
Существует также n log n & middot; 2 O (log * n) алгоритм, опубликованный в 2008 году, но это было слишком новым, чтобы быть широко распространенным.
Обычно наивный метод достаточно хорош для ввода нормального размера.
Интересно, насколько быстрее O (N 2,38), чем O (N³). – psihodelia
К сожалению, ответ на этот вопрос «это зависит». Как упоминается в статье в википедии, алгоритм широко не используется, поскольку на самом деле это приводит к сокращению времени выполнения для непрактично больших входов. –
На практике алгоритм O (N^2,38) не является вообще более быстрым, потому что есть больше скорости, чем алгоритмическая сложность. – Pillsy
Операции не имеют сложности, алгоритмы делают. Например, существуют различные алгоритмы с квадратным корнем, и они будут иметь разную сложность.
Умножение - это алгоритм между двумя массивами бит. Со сложностью O (n²), если я не ошибаюсь. – Tronic
@Skilldrick: OP говорит о наиболее часто используемых алгоритмах, поэтому в некотором смысле этот ответ не имеет значения. – 2010-03-05 14:17:09
@Moron: Я думаю, что вопрос был слегка отредактирован, так как я ответил. – Skilldrick
Вы будете рассматривать самые простые операции как O (1), потому что ваш размер ввода обычно фиксируется (то есть 32- или 64-разрядный).
В нормальных условиях ваша платформа будет выполнять точно такую же операцию для умножения, квадратного корня, логарифма и т. Д., Независимо от «размера» вашего ввода (т. Е. Int a = 0 и int b = Int32.MaxValue оба 32-битных целых числа).
Это становится интересным, когда вы начинаете смотреть на матрицы или представлять цифры произвольной точности, но кто-то уже связал резюме википедии, поэтому я не буду вдаваться в это.
Просто не используйте Schönhage–Strassen, чтобы умножить «нормальные» маленькие числа. Это заставит меня плакать. Просто потому, что алгоритм O (п) не означает, что это плохо - особенно, когда п почти всегда 2 или 2 .
Это очень хороший момент для операций с 32-битными ints. – Skilldrick
На практике вы правы в отношении простых операций. Однако, как теоретик, я хочу сказать, что вы все еще можете говорить о сложности с точки зрения количества бит в числе. Один и тот же алгоритм подходит для 32b, но медленнее для 64b, или когда мы в конечном итоге добираемся до 1024b или что-то еще ... Опять же, реалистично вы правы, но это все еще интересный вопрос. –
* nods *, это абсолютно интересный вопрос, как только вы выходите из безопасного мира входов фиксированной длины. –
Квадратный корень и логарифм могут быть реализованы различными способами, что существенно влияет на сложность (судя по требуемой точности).
Если они реализованы с помощью таблиц поиска (и некоторая интерполяция), потребность в памяти действительно взрывается, так как требуется больше точности, но сложность заключается в поиске значения в массиве и, возможно, применении интерполяции.
Более популярен, по-видимому, они воплощены в своих определениях серий. Повторите или повторите утверждение для нескольких раундов, пока не достигнете требуемой точности. Здесь количество раундов может стать очень высоким, так как требуется более высокая точность, а также на самих вычислениях влияет повышенная точность.
+1 Интересно. Означает ли это, что N становится точностью? – Skilldrick
@skilldrick, вы можете определенно сделать это именно так. Существуют алгоритмы, которые измеряются в размере их OUTPUT вместо их ввода. У них есть имя, но это пятница, поэтому я не могу его запомнить. B-) –
Там же тип алгоритма Фурье, который делает целое умножение и (Schonhage-Strassen)
Я думал, что существует вариант алгоритма Штрассена, что делает немного лучше, чем обычно для умножения целых чисел, но теперь, когда я думаю об этом, что один заканчивается тем же, что и простой ...
Сложение и вычитание в значительной степени, просто сложение и вычитание. Разделение и квадратный корень, вероятно, интересны, хотя ...
ТАКЖЕ: Обратите внимание, что до сих пор все говорили об арифметике INTEGER. Как только вы доберетесь до плит/удваивает все ставки. Затем вы попадаете в мир numerical analysis, и это целое поле собственного ...
Посмотрите на BigInteger на целые числа произвольной длины. Все теперь имеет стоимость с точки зрения размера ввода, которое представляет собой количество бит (обычно O(log K) бит для номера K). Я буду использовать N для количества бит ниже.
Например, сложение и вычитание теперь O(N). Умножение равно O(N^2) (наивное) или O(n (log n)^(2+epsilon) ) с FFT.
Другие алгоритмы включают функцию «мощность», которая принимает умножение O(N). (за исключением того, что теперь каждое умножение имеет стоимость!)
Есть и дополнительные сложности для BigDecimals, который представляет собой десятичный эквивалент произвольной длины и помимо некоторых более основных операций, некоторые из вещей интереснее (особенно если вы хотите выяснить, какую точность вы хотите). Вы можете взглянуть на реализацию Java.
Наивная реализация функции мощности требует O (n) умножений, но интеллектуальными реализациями являются O (log n): http://en.wikipedia.org/wiki/Exponentiation_by_squaring – Juliet
Как я уже говорил, «N» - это количество бит. На самом деле питание - это «O (log K)» для некоторого числа 'K'. – Larry
Разделение и квадратные корни для огромного количества бит не намного сложнее, чем умножение. Для обеих операций простая старая итерация Ньютона может быть организована таким образом, что итерация Ньютона имеет только умножения. Поскольку количество правильных цифр удваивается на каждом шаге, мы можем просто удвоить точность вычислений на каждом шаге.
+1 Интересный вопрос. Для пояснения предположительно он означает сложность с увеличением числа бит. – Tronic
@Tronic: вы считаете бит? Матричный продукт, вероятно, будет иметь размер матрицы, предположительно ... – Skilldrick
Community Wiki? – 2010-03-05 14:16:28