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

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

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

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

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

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

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

тогда мы можем сказать, что евклидов GCD может сделать log (xy) operation максимум.

там большой взгляд на это на статья в Википедии.

Он даже имеет хороший график сложности для пар значений.

Это не O (A%b).

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

посмотреть здесь.

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

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

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

вот интуитивное понимание сложности выполнения алгоритма Евклида. Формальные доказательства рассматриваются в различных текстах, таких как введение в алгоритмы и 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 является НОД(A,C), мы можем заменить B с помощью кнопок B/НОД(A,B) в нашем времени выполнения приводит к более жесткие границы o(зарегистрируйте б/нод(а,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).

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

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);
}

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

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

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

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

для криптографических целей мы обычно рассматриваем побитовую сложность алгоритмов, принимая во внимание учтите, что размер бита задается приблизительно 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

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

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

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

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

по (1) и (2) имеем: ki+1

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

переставляя это: SUM [(ki-1)-((ki) -1))]*ki

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