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

Мне трудно решить, какова временная сложность алгоритма наибольшего общего знаменателя Евклида. Этот алгоритм в псевдокоде:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Кажется, это зависит от a и b . Я думаю, что временная сложность равна O (a% b). Это правильно? Есть ли лучший способ написать это?

Один из приемов анализа временной сложности алгоритма Евклида - проследить, что происходит на двух итерациях:

a', b' := a % b, b % (a % b)

Теперь a и b уменьшатся, а не только один, что упрощает анализ. Вы можете разделить это на случаи:

• Крошечный A: 2a <= b
• Крошечный B: 2b <= a
• Маленький A: 2a > bноa < b
• Маленький B: 2b > aноb < a
• Равно: a == b

Теперь мы покажем, что в каждом отдельном случае общая сумма уменьшается a+bминимум на четверть:

• Tiny A: b % (a % b) < aи 2a <= b, значит b, уменьшается как минимум наполовину, поэтому a+bуменьшается как минимум на25%
• Крошечный B: a % b < bи 2b <= a, значит a, уменьшается как минимум наполовину, поэтому a+bуменьшается как минимум на25%
• Маленький A: bстанет b-a, что меньше b/2, уменьшится a+bкак минимум на 25%.
• Маленький B: aстанет a-b, что меньше a/2, уменьшится a+bкак минимум на 25%.
• Равно: a+bснижается до 0, что, очевидно, уменьшается a+bкак минимум на 25%.

Следовательно, при анализе случая каждый двойной шаг уменьшается a+bкак минимум на 25%. Это может произойти максимальное количество раз, прежде чем он a+bбудет вынужден опуститься ниже 1. Общее количество шагов ( S) до тех пор, пока мы не достигнем 0, должно удовлетворять (4/3)^S <= A+B. Теперь просто работайте:

(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)

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

Конечно, если вы имеете дело с большими целыми числами, вы должны учитывать тот факт, что операции модуля в каждой итерации не имеют постоянной стоимости. Грубо говоря, общее асимптотическое время выполнения будет в n ^ 2 раз больше полилогарифмического фактора. Что-то вроде n^2 lg(n) 2^O(log* n) . Полилогарифмического фактора можно избежать, если вместо этого использовать двоичный gcd .

Подходящий способ анализа алгоритма - определение его наихудшего сценария. Худший случай евклидова НОД возникает, когда задействованы пары Фибоначчи. void EGCD(fib[i], fib[i - 1]), где i> 0.

Например, давайте выберем случай, когда дивиденд равен 55, а делитель равен 34 (напомним, что мы все еще имеем дело с числами Фибоначчи).

Как вы могли заметить, эта операция потребовала 8 итераций (или рекурсивных вызовов).

Давайте попробуем более крупные числа Фибоначчи, а именно 121393 и 75025. Здесь мы также можем заметить, что потребовалось 24 итерации (или рекурсивных вызовов).

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

Следовательно, на этот раз временная сложность будет представлена ​​маленьким Oh (верхняя граница). Нижняя граница интуитивно обозначается Омега (1): например, 500 делится на 2.

Решим рекуррентное соотношение:

Можно сказать , то , что евклидовой НОД может сделать лог (х) операции в большинстве .

На это есть отличный взгляд на статью в Википедии .

У него даже есть красивый график сложности для пар значений.

Это не так O(a%b).

Известно (см. Статью), что он никогда не сделает больше шагов, чем в пять раз больше цифр в меньшем числе. Таким образом, максимальное количество шагов растет пропорционально количеству цифр (ln b). Стоимость каждого шага также растет с увеличением количества цифр, поэтому сложность ограничивается O(ln^2 b)где b - меньшее число. Это верхний предел, а фактическое время обычно меньше.

Смотрите здесь .

В частности эта часть:

Ламе показал, что количество шагов, необходимых для получения наибольшего общего делителя для двух чисел меньше n, равно

Так O(log min(a, b))что это хорошая верхняя граница.

Вот интуитивное понимание сложности выполнения алгоритма Евклида. Формальные доказательства описаны в различных текстах, таких как Введение в алгоритмы и TAOCP Vol 2.

Сначала подумайте, что, если бы мы попытались взять НОД двух чисел Фибоначчи F (k + 1) и F (k). Вы можете быстро заметить, что алгоритм Евклида повторяется до F (k) и F (k-1). То есть с каждой итерацией мы опускаемся на одно число в ряду Фибоначчи. Поскольку числа Фибоначчи равны O (Phi ^ k), где Phi - золотое сечение, мы можем видеть, что время выполнения GCD было O (log n), где n = max (a, b), а log имеет основание Phi. Затем мы можем доказать, что это был бы наихудший случай, наблюдая, что числа Фибоначчи последовательно создают пары, в которых остатки остаются достаточно большими на каждой итерации и никогда не становятся нулевыми, пока вы не дойдете до начала ряда.

Мы можем сделать O (log n), где n = max (a, b), еще более жестким. Предположим, что b> = a, поэтому мы можем записать границу в O (log b). Сначала заметим, что GCD (ka, kb) = GCD (a, b). Поскольку наибольшее значение k равно gcd (a, c), мы можем заменить b на b / gcd (a, b) в нашей среде выполнения, что приведет к более жесткой границе O (log b / gcd (a, b)).

Наихудший случай алгоритма Евклида - это когда остатки являются наибольшими возможными на каждом шаге, т.е. для двух последовательных членов последовательности Фибоначчи.

Когда n и m - количество цифр a и b, предполагая, что n> = m, алгоритм использует O (m) делений.

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

В худшем случае возникнет, когда и n, и m являются последовательными числами Фибоначчи.

gcd (Fn, Fn − 1) = gcd (Fn − 1, Fn − 2) = ⋯ = gcd (F1, F0) = 1 и n-е число Фибоначчи равно 1,618 ^ n, где 1,618 - золотое сечение.

Итак, чтобы найти gcd (n, m), количество рекурсивных вызовов будет (logn).

Вот анализ из книги Марка Аллена Вейсса « Структуры данных и анализ алгоритмов в языке С » (второе издание, 2.4.4):

Алгоритм Евклида работает, непрерывно вычисляя остатки, пока не будет достигнут 0. Последний ненулевой остаток и есть ответ.

Вот код:

unsigned int Gcd(unsigned int M, unsigned int N)
{

    unsigned int Rem;
    while (N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    Return M;
}

Вот ТЕОРЕМА, которую мы собираемся использовать:

Если M> N, то M mod N <M / 2.

ДОКАЗАТЕЛЬСТВО:

Есть два случая. Если N <= M / 2, то, поскольку остаток меньше N, теорема верна для этого случая. Другой случай - N> M / 2. Но тогда N переходит в M один раз с остатком M - N <M / 2, доказывая теорему.

Итак, мы можем сделать следующий вывод:

Variables    M      N      Rem

initial      M      N      M%N

1 iteration  N     M%N    N%(M%N)

2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

Таким образом, после двух итераций остаток составляет не более половины от исходного значения. Это покажет, что количество итераций не больше 2logN = O(logN).

Обратите внимание, что алгоритм вычисляет Gcd (M, N), предполагая, что M> = N. (Если N> M, первая итерация цикла меняет их местами.)

Теорема Габриэля Ламе ограничивает количество шагов величиной log (1 / sqrt (5) * (a + 1/2)) - 2, где основание журнала равно (1 + sqrt (5)) / 2. Это для наихудшего сценария алгоритма, и это происходит, когда входные данные являются последовательными числами Фибаноччи.

Несколько более либеральная граница: log a, где основание журнала (sqrt (2)) подразумевается Коблицем.

В криптографических целях мы обычно рассматриваем поразрядную сложность алгоритмов, принимая во внимание, что размер битов приблизительно определяется как k = loga.

Вот подробный анализ поразрядной сложности алгоритма Евклида:

Хотя в большинстве ссылок поразрядная сложность алгоритма Евклида задается как O (loga) ^ 3, существует более жесткая граница, которая равна O (loga) ^ 2.

Рассматривать; r0 = a, r1 = b, r0 = q1.r1 + r2. . . , ri-1 = qi.ri + ri + 1,. . . , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

обратите внимание, что: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

а rm - наибольший общий делитель a и b.

Утверждением в книге Коблица (курс теории чисел и криптографии) можно доказать, что: ri + 1 <(ri-1) / 2 ................. ( 2)

Снова в Коблице количество битовых операций, необходимых для деления k-разрядного положительного целого числа на l-разрядное положительное целое число (при условии, что k> = l), дается как: (k-l + 1) .l ...... ............. (3)

Согласно (1) и (2) количество делений равно O (loga), поэтому согласно (3) общая сложность O (loga) ^ 3.

Теперь это можно свести к O (loga) ^ 2 с помощью замечания Коблица.

рассмотрим ki = logri +1

согласно (1) и (2) имеем: ki + 1 <= ki для i = 0,1, ..., m-2, m-1 и ki + 2 <= (ki) -1 для i = 0 , 1, ..., м-2

и по (3) общая стоимость m делений ограничена: SUM [(ki-1) - ((ki) -1))] * ki для i = 0,1,2, .., m

переставив это: СУММ [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Таким образом, поразрядная сложность алгоритма Евклида равна O (loga) ^ 2.

Однако для итеративного алгоритма мы имеем:

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

С парами Фибоначчи нет разницы между iterativeEGCD()и iterativeEGCDForWorstCase()где последнее выглядит следующим образом:

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Да, с парами Фибоначчи, n = a % nи n = a - nэто то же самое.

Мы также знаем , что в более раннем ответ на тот же вопрос, есть преобладающий фактор уменьшения: factor = m / (n % m).

Следовательно, чтобы сформировать итеративную версию евклидова НОД в определенной форме, мы можем изобразить "симулятор" следующим образом:

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Основываясь на работе (последний слайд) доктора Джаухара Али, приведенный выше цикл является логарифмическим.

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

На каждом этапе есть два случая

b> = a / 2, тогда a, b = b, a% b сделает b не более половины его предыдущего значения

b <a / 2, тогда a, b = b, a% b составит не более половины своего предыдущего значения, так как b меньше a / 2

Таким образом, на каждом этапе алгоритм будет уменьшать хотя бы одно число как минимум наполовину.

За шаг не более O (log a) + O (log b) это будет сведено к простым случаям. Что дает алгоритм O (log n), где n - верхний предел a и b.

Я нашел это здесь