Complejidad del tiempo del algoritmo de Euclides

Question

Tengo dificultades para decidir cuál es la complejidad temporal del algoritmo de denominador común más grande 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 un y b. Mi pensamiento es que la complejidad del tiempo es O (a% b). ¿Es eso correcto? ¿Hay una mejor manera de escribir eso?

Answer 1

Un truco para analizar la complejidad del tiempo del algoritmo de Euclides es seguir lo que ocurre más de dos iteraciones:

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

Ahora A y B tanto en disminución, en lugar de sólo uno, lo que hace que el análisis sea más fácil.Puede dividirlo en casos:

• un diminuto: 2a <= b
• Tiny B: 2b <= a
• Pequeño R: 2a > b pero a < b
• Pequeño B: 2b > a pero b < a
• Igualdad: a == b

Ahora mostraremos que cada si caso ngle disminuye el total de a+b por al menos un cuarto:

• A Tiny: b % (a % b) < a y 2a <= b, por lo b se reduce en al menos la mitad, por lo a+b disminuido al menos 25%
• B Tiny: a % b < b y 2b <= a , por lo a se reduce en al menos la mitad, por lo a+b disminuido al menos 25%
• Pequeño a: b se convertirá en b-a, que es menor que b/2, decreasin g a+b por al menos 25%.
• B Small: a se convertirá en a-b, que es menor que a/2, disminuyendo a+b por al menos 25%.
• Igual: a+b cae a 0, lo que obviamente está disminuyendo a+b por al menos 25%.

Por lo tanto, por análisis de caso, cada paso doble disminuye a+b por lo menos 25%. Hay una cantidad máxima de veces que esto puede suceder antes de que a+b se vea obligado a caer por debajo de 1. El número total de pasos (S) hasta que lleguemos a 0 debe cumplir (4/3)^S <= A+B. Ahora acaba de trabajarla:

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

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

Por supuesto, si se trata de 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 va a ser n^2 veces un factor poliglotámico. Something liken^2 lg(n) 2^O(log* n). El factor poliglotámico se puede evitar utilizando en su lugar un binary gcd.

Answer 2

Hay un gran vistazo a esto en el wikipedia article.

Incluso tiene una parcela de complejidad para los pares de valores.

No es O (un% b).

Se sabe (ver artículo) que nunca tomará más pasos que cinco veces el número de dígitos en el número más pequeño. Por lo tanto, 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 como el número de dígitos, por lo que la complejidad está limitada por O (ln^2 b) donde b es el nubmer más pequeño. Ese es un límite superior, y el tiempo real suele ser menor.

Answer 3

Ver here.

En particular esta parte:

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

Así O(log min(a, b)) es un buen límite superior.

Answer 4

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

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

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

Answer 5

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

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

Como se puede observar, esta operación calcularía 8 iteraciones (o llamadas recursivas).

Probemos los números de Fibonacci más grandes, concretamente 121393 y 75025. Aquí también podemos observar que se necesitaron 24 iteraciones (o llamadas recursivas).

También puede notar que cada iteraciones se obtiene un número de Fibonacci. Es por eso que tenemos tantas operaciones. No podemos obtener resultados similares solo con los números de Fibonacci de hecho.

Por lo tanto, la complejidad del tiempo se representará con 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.

Vamos a resolver la relación de recurrencia:

Podemos decir entonces que euclidiana GCD puede hacer log (xy) operación como máximo.

Answer 6

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 pares de Fibonacci, no hay ninguna diferencia entre iterativeEGCD() y iterativeEGCDForWorstCase() cuando este último tiene el siguiente aspecto:

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 % n y n = a - n, es exactamente lo mismo.

También sabemos que, en una respuesta anterior para la misma pregunta, existe un factor decreciente que prevalece: factor = m/(n % m).

Por lo tanto, para dar forma a la versión iterativa de la euclidiana GCD en una forma definida, podemos describir como un "simulador" como esto:

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 la work (última diapositiva) del Dr. Jauhar Ali, el ciclo de arriba es logarítmico.

Sí, Oh pequeña ya que el simulador indica el número de iteraciones como máximo. Los pares que no son de Fibonacci tomarían una menor cantidad de iteraciones que Fibonacci, cuando se sondearon en Euclides GCD.

Answer 7

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

Primero piense qué pasaría si tratamos de tomar el gcd de dos números de Fibonacci F (k + 1) y F (k). Puede observar rápidamente que el algoritmo de Euclides itera a 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 era O (log n) donde n = max (a, b) y log tiene 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 consistentemente donde los restos permanecen lo suficientemente grandes en cada iteración y nunca se vuelven cero hasta que hayas llegado al comienzo de la serie.

Podemos hacer que O (log n) donde n = max (a, b) se vincule aún más. Supongamos que b> = a para que podamos escribir enlazado a O (log b). Primero, observe que GCD (ka, kb) = GCD (a, b). Como los mayores valores de k son gcd (a, c), podemos reemplazar b con b/gcd (a, b) en nuestro tiempo de ejecución, lo que lleva a un límite más estricto de O (log b/gcd (a, b)).

Answer 8

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

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

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

Aquí es un análisis detallado de la complejidad bit a bit de Euclides algorith:

Aunque en la mayoría de las referencias de la complejidad bit a bit de Euclides Algoritmo está 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 mayor divisor común de ay b.

Por un reclamo en el libro de Koblitz (Un curso en teoría de números y criptografía) se puede demostrar que: ri + 1 < (ri-1)/2 .............. ... (2)

De nuevo 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í sucesivamente (3) la complejidad total es O (loga)^3.

Ahora esto se puede reducir a O (loga)^2 por una observación en Koblitz.

consideran 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á limitado 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 Euclid m es O (loga)^2.

Answer 9

El peor caso surgirá cuando tanto n como m sean números Fibonacci consecutivos.

gcd (Fn, Fn-1) = gcd (Fn-1, Fn-2) = ⋯ = gcd (F1, F0) = 1 y el n. º número de Fibonacci es 1.618^n, donde 1.618 es la Proporción áurea.

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