Complejidad temporal del algoritmo de Euclides

Estoy teniendo dificultades para decidir cuál es la complejidad temporal del algoritmo de mayor denominador común de Euclides. Este algoritmo en pseudocódigo es:

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

Parece que depender de una y b . Mi pensamiento es que la complejidad del tiempo es O (a% b). ¿Es eso correcto? ¿Existe una mejor manera de escribir eso?

Un truco para analizar la complejidad temporal del algoritmo de Euclid es seguir lo que sucede en dos iteraciones:

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

Ahora ayb disminuirán, en lugar de solo uno, lo que facilita el análisis. Puedes dividirlo en casos:

• Pequeña A: 2a <= b
• Pequeña B: 2b <= a
• Pequeña A: 2a > bperoa < b
• Pequeña B: 2b > aperob < a
• Igual: a == b

Ahora mostraremos que cada caso reduce el total a+ben al menos un cuarto:

• Tiny A: b % (a % b) < ay 2a <= b, por blo tanto, se reduce al menos a la mitad, por lo que se a+breduce al menos25%
• Tiny B: a % b < by 2b <= a, por alo tanto, se reduce al menos a la mitad, por lo que se a+breduce al menos25%
• Pequeña A: bse convertirá b-a, que es menor que b/2, disminuyendo a+bal menos 25%.
• Pequeña B: ase convertirá a-b, que es menor que a/2, disminuyendo a+bal menos 25%.
• Igual: a+bcae a 0, que obviamente está disminuyendo a+bal menos 25%.

Por lo tanto, según el análisis de casos, cada doble paso disminuye a+bal menos 25%. Hay un número máximo de veces que esto puede suceder antes de que a+bse vea obligado a caer por debajo 1. El número total de pasos ( S) hasta que lleguemos a 0 debe satisfacer (4/3)^S <= A+B. Ahora solo trabaja:

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

Entonces, el número de iteraciones es lineal en el número de dígitos de entrada. Para los números que encajan en los registros de la CPU, es razonable modelar las iteraciones como si tuvieran un tiempo constante y pretender que el tiempo total de ejecución del gcd es lineal.

Por supuesto, si se trata de números enteros grandes, debe tener en cuenta el hecho de que las operaciones de módulo dentro de cada iteración no tienen un costo constante. En términos generales, el tiempo de ejecución asintótico total será n ^ 2 veces un factor polilogarítmico. Algo como n^2 lg(n) 2^O(log* n) . El factor polilogarítmico se puede evitar utilizando en su lugar un mcd binario .

La forma adecuada de analizar un algoritmo es determinando sus peores escenarios. El peor caso de Euclidean GCD ocurre cuando están involucrados los pares de Fibonacci. void EGCD(fib[i], fib[i - 1]), donde i> 0.

Por ejemplo, optemos por el caso en el que el dividendo es 55 y el divisor es 34 (recuerde que todavía estamos tratando con números de Fibonacci).

Como puede notar, esta operación costó 8 iteraciones (o llamadas recursivas).

Probemos con números de Fibonacci más grandes, a saber, 121393 y 75025. También podemos notar aquí que tomó 24 iteraciones (o llamadas recursivas).

También puede notar que cada iteración produce un número de Fibonacci. Por eso tenemos tantas operaciones. De hecho, no podemos obtener resultados similares solo con los números de Fibonacci.

Por lo tanto, la complejidad del tiempo estará representada por un pequeño Oh (límite superior), esta vez. El límite inferior es intuitivamente Omega (1): caso de 500 dividido por 2, por ejemplo.

Resolvamos la relación de recurrencia:

Podemos decir entonces que Euclidean GCD puede realizar una operación log (xy) como máximo .

Hay una gran mirada a esto en el artículo de wikipedia .

Incluso tiene una bonita trama de complejidad para pares de valores.

No lo es O(a%b).

Se sabe (ver artículo) que nunca dará más de cinco veces el número de dígitos del número menor. Entonces, el número máximo de pasos crece a medida que el número de dígitos (ln b). El costo de cada paso también crece a medida que aumenta el número de dígitos, por lo que la complejidad está limitada por O(ln^2 b)donde b es el número menor. Ese es un límite superior y el tiempo real suele ser menor.

Vea aquí .

En particular esta parte:

Lamé mostró que el número de pasos necesarios para llegar al máximo común divisor para dos números menores que n es

También lo O(log min(a, b))es un buen límite superior.

Aquí está la comprensión intuitiva de la complejidad del tiempo de ejecución del algoritmo de Euclid. Las pruebas formales se cubren en varios textos como Introducción a los algoritmos y TAOCP Vol 2.

Primero, piense en qué pasaría si intentáramos tomar el mcd de dos números de Fibonacci F (k + 1) y F (k). Puede observar rápidamente que el algoritmo de Euclides se repite en F (k) y F (k-1). Es decir, con cada iteración bajamos un número en la serie de Fibonacci. Como los números de Fibonacci son O (Phi ^ k) donde Phi es la proporción áurea, podemos ver que el tiempo de ejecución de GCD fue O (log n) donde n = max (a, b) y log tiene una base de Phi. A continuación, podemos demostrar que este sería el peor de los casos al observar que los números de Fibonacci producen pares de manera consistente donde los residuos permanecen lo suficientemente grandes en cada iteración y nunca se vuelven cero hasta que se llega al comienzo de la serie.

Podemos hacer O (log n) donde n = max (a, b) límite aún más estrecho. Suponga que b> = a para que podamos escribir un límite en O (log b). Primero, observe que MCD (ka, kb) = MCD (a, b). Como los valores más grandes de k son mcd (a, c), podemos reemplazar b con b / mcd (a, b) en nuestro tiempo de ejecución, lo que lleva a un límite más estrecho de O (log b / mcd (a, b)).

El peor caso del algoritmo de Euclides es cuando los restos son los más grandes posibles en cada paso, es decir. durante dos términos consecutivos de la secuencia de Fibonacci.

Cuando nym son el número de dígitos de ayb, suponiendo que n> = m, el algoritmo usa divisiones O (m).

Tenga en cuenta que las complejidades siempre se dan en términos del tamaño de las entradas, en este caso, el número de dígitos.

El peor de los casos surgirá cuando tanto n como m son números de Fibonacci consecutivos.

mcd (Fn, Fn − 1) = mcd (Fn − 1, Fn − 2) = ⋯ = mcd (F1, F0) = 1 y el n-ésimo número de Fibonacci es 1.618 ^ n, donde 1.618 es la proporción áurea.

Entonces, para encontrar gcd (n, m), el número de llamadas recursivas será Θ (logn).

Aquí está el análisis en el libro Data Structures and Algorithm Analysis in C de Mark Allen Weiss (segunda edición, 2.4.4):

El algoritmo de Euclid funciona calculando continuamente los residuos hasta que se alcanza 0. El último resto distinto de cero es la respuesta.

Aquí está el código:

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

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

Aquí hay un TEOREMA que vamos a utilizar:

Si M> N, entonces M mod N <M / 2.

PRUEBA:

Hay dos casos. Si N <= M / 2, dado que el resto es menor que N, el teorema es cierto para este caso. El otro caso es N> M / 2. Pero luego N entra en M una vez con un resto M - N <M / 2, lo que demuestra el teorema.

Entonces, podemos hacer la siguiente inferencia:

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

Entonces, después de dos iteraciones, el resto es como máximo la mitad de su valor original. Esto mostraría que el número de iteraciones es como máximo 2logN = O(logN).

Tenga en cuenta que el algoritmo calcula Gcd (M, N), asumiendo M> = N. (Si N> M, la primera iteración del bucle los intercambia).

El teorema de Gabriel Lame limita el número de pasos por log (1 / sqrt (5) * (a + 1/2)) - 2, donde la base del log es (1 + sqrt (5)) / 2. Esto es para el peor escenario del algoritmo y ocurre cuando las entradas son números de Fibanocci consecutivos.

Un límite ligeramente más liberal es: log a, donde la base del logaritmo es (sqrt (2)) está implícita en Koblitz.

Para fines criptográficos, solemos considerar la complejidad bit a bit de los algoritmos, teniendo en cuenta que el tamaño de bit viene dado aproximadamente por k = loga.

Aquí hay un análisis detallado de la complejidad bit a bit del algoritmo Euclid:

Aunque en la mayoría de las referencias la complejidad bit a bit del algoritmo de Euclides viene dada por O (loga) ^ 3, existe un límite más estricto que es O (loga) ^ 2.

Considerar; 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

observe que: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

y rm es el máximo común divisor de ay b.

Mediante una afirmación en el libro de Koblitz (Un curso de Teoría de números y Criptografía) se puede probar que: ri + 1 <(ri-1) / 2 ................. ( 2)

Nuevamente en Koblitz, el número de operaciones de bits requeridas para dividir un entero positivo de k bits por un entero positivo de 1 bit (suponiendo que k> = l) se da como: (k-l + 1) .l ...... ............. (3)

Por (1) y (2) el número de divisiones es O (loga) y así por (3) la complejidad total es O (loga) ^ 3.

Ahora bien, esto puede reducirse a O (loga) ^ 2 mediante una observación en Koblitz.

considere ki = logri +1

por (1) y (2) tenemos: ki + 1 <= ki para i = 0,1, ..., m-2, m-1 y ki + 2 <= (ki) -1 para i = 0 , 1, ..., m-2

y por (3) el costo total de las m divisiones está acotado por: SUM [(ki-1) - ((ki) -1))] * ki para i = 0,1,2, .., m

reorganizando esto: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Entonces, la complejidad bit a bit del algoritmo de Euclides es O (loga) ^ 2.

Para el algoritmo iterativo, sin embargo, tenemos:

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

Con los pares de Fibonacci, no hay diferencia entre iterativeEGCD()y iterativeEGCDForWorstCase()donde este último se ve así:

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

Sí, con Fibonacci Pairs, n = a % ny n = a - nes exactamente lo mismo.

También sabemos que, en una respuesta anterior para la misma pregunta, hay un factor de disminución prevaleciente: factor = m / (n % m).

Por lo tanto, para dar forma a la versión iterativa del GCD euclidiano en una forma definida, podemos representarlo como un "simulador" como este:

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

Basado en el trabajo (última diapositiva) del Dr. Jauhar Ali, el bucle anterior es logarítmico.

Sí, pequeño Oh porque el simulador indica el número de iteraciones como máximo . Los pares que no son de Fibonacci tomarían un número menor de iteraciones que los de Fibonacci, cuando se prueban en Euclidean GCD.

En cada paso, hay dos casos

b> = a / 2, entonces a, b = b, a% b hará b como máximo la mitad de su valor anterior

b <a / 2, entonces a, b = b, a% b hará a como máximo la mitad de su valor anterior, ya que b es menor que a / 2

Entonces, en cada paso, el algoritmo reducirá al menos un número a al menos la mitad menos.

En el paso O (log a) + O (log b) como máximo , esto se reducirá a los casos simples. Lo que produce un algoritmo O (log n), donde n es el límite superior de ay b.

Lo he encontrado aqui