Большой O анализ функции вычисления GCD [дубликат]

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

Когда 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).

Теорема Габриэля Ламе ограничивает число шагов по 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 & lt; (ri-1) / 2 ................. (2)

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

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

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

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

в силу (1) и (2) имеем: ki + 1 & lt; = ki для i = 0,1, ..., m-2, m-1 и ki + 2 & lt; = (ki) -1 для i = 0,1, ..., m-2

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

, переставляя это: SUM [(ki-1) - ((ki) -1))] * ki = 4 * k0 ^ 2

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

См. здесь .

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

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

[/g1]

Таким образом, O(log min(a, b)) является хорошей верхней границей.

Замечательно посмотрите на статью wikipedia .

Он даже имеет приятный сюжет сложности для пар значений.

Это не О (а% б).

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

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

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 в определенном виде, мы можем изобразить как «симулятор» следующим образом:

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

Основываясь на работе (последний слайд) д-ра Jauhar Ali, вышеописанный цикл является логарифмическим.

[/g1]

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

Вот интуитивное понимание сложности выполнения алгоритма Евклида. Формальные доказательства рассматриваются в различных текстах, таких как Введение в алгоритмы и 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)).