В чем сложность алгоритма расширенного Евклида?

Question

Что такое битовая сложность, используемая при вычислении наибольшего общего делителя двух n-битных значений x и y с использованием расширенного алгоритма Евклида, т.е. сложности в терминах n

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

Сложность с точки зрения величины двух значений x и y близка к значению:

Источник

Как прийти к теоретической сложности битов для проверки моих наблюдений?

Answer 1

Я надеюсь, что вы подходите к пикам, поскольку вы ищете сложность наихудшего случая.

В любом случае ...

Если a и b имеют длину N бит, тогда в худшем случае (пары Фибоначчи) расширенный евклидов алгоритм будет принимать O (N) итераций.

Пусть f (N) будет стоимостью одной итерации.Конечно, f (N) будет по крайней мере линейным, но все еще полиномиальным, и почти половина итераций в каждом случае будет включать аргументы длиной не менее N / 2 битов, поэтому общеесложность будет в O (f (N) log N)

Теперь, что именно f (N) , будет зависеть от того, насколько большое целое числоОперации реализованы в вашей библиотеке.Операция деления / остатка будет доминирующей, хотя в википедии сказано, что если вы используете деление Ньютона-Рафсона, то сложность такая же, как умножение (хотя, безусловно, будет постоянный множитель!).

Затраты на умножение O (N * log N * log log N) в пределе с Шёнхаге-Штрассеном, и, надеюсь, ваша библиотека в конечном итоге воспользуется этим ... поэтому, когда числа станут действительно большими,расширенный евклидов алгоритм должен принимать O (N * log ^ 2 N * log log N) в худшем случае.