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

Question

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

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

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

Answer 1

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

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

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

• Tiny A: 2a <= b
• Tiny B: 2b <= a
• Маленький A: 2a > b, но a < b
• Малый Б: 2b > a, но b < a
• Равен: a == b

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

• Tiny A: b % (a % b) < a и 2a <= b, поэтому b уменьшается как минимум вдвое, поэтому a+b уменьшается как минимум 25%
• Tiny B: a % b < b и 2b <= a, поэтому a уменьшается как минимум вдвое, поэтому a+b уменьшается как минимум 25%
• Small A: b станет b-a, что меньше b/2, уменьшив a+b как минимум на 25%.
• Small 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)

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

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

Answer 2

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

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

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

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

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

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

Давайте решим рекуррентное соотношение:

Тогда можно сказать, что евклидово GCD может выполнить операцию log (xy) самое большее .

Answer 3

В статье в википедии .

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

Это не O(a%b),

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

Answer 4

См. здесь .

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

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

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

Answer 5

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

Сначала подумайте о том, что если бы мы попытались взять gcd двух чисел Фибоначчи 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)).

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

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

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).

Поэтому, чтобы сформировать итеративную версию евклидова ГКД в определенной форме, мы можем изобразить ее в виде «симулятора», подобного следующему:на работе (последний слайд) доктора Джохара Али цикл выше является логарифмическим.

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

Answer 9

Теорема Габриэля Ламе ограничивает число шагов логарифмом (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) </p>

Снова в Коблице число битовых операций, необходимое для деления 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 для = 0,1, ..., т-2 </p>

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

перестановка: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2 </p>

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