Complejidad temporal del algoritmo euclidiano

En este artículo, discutiremos la complejidad temporal del Algoritmo Euclidiano que es O(log(min(a, b)) y se logra.

Algoritmo de Euclides : es un método eficiente para encontrar el MCD (máximo común divisor) de dos números enteros. La complejidad temporal de este algoritmo es O(log(min(a, b)) . Recursivamente se puede expresar como:

gcd(a, b) = gcd(b, a%b) , 
donde a y b son dos números enteros.

Prueba: supongamos que a y b son dos números enteros tales que a > b , entonces de acuerdo con el algoritmo de Euclides:

mcd(a, b) = mcd(b, a%b)

Utilice la fórmula anterior de forma repetitiva hasta llegar a un paso donde b es 0 . En este paso, el resultado será el MCD de los dos enteros , que será igual a a . Entonces, después de observar detenidamente, se puede decir que la complejidad temporal de este algoritmo sería proporcional al número de pasos necesarios para reducir b a 0 .

Supongamos que el número de pasos necesarios para reducir b a 0 usando este algoritmo es N .

gcd(a, b) ------> N steps

Ahora, si el Algoritmo Euclidiano para dos números a y b se reduce en N pasos entonces, a debe ser al menos f _{(N + 2)} y b debe ser al menos f _{(N + 1)} .

mcd(a, b) ——> N pasos
Entonces, a >= f _{(N + 2)} y b >= f _{(N + 1)}
donde, f _N es el N ^-ésimo término en la serie de Fibonacci (0, 1, 1, 2, 3, …) y N >= 0.

Para probar la declaración anterior usando el Principio de Inducción Matemática (PMI) :

• Caso base:
  • Supongamos a = 2 y b = 1 . Entonces, mcd(2, 1) se reducirá a mcd(1, 0) en 1 paso, es decir, N = 1 .
  • Esto significa que 2 debe ser al menos f ₃ y 1 debe ser al menos f ₂ y f ₃ = 2 y f ₂ = 1 .
  • Esto implica que a es al menos f _{(N + 2)} yb es al menos f ( _{N + 1)} .
  •  
  • Se puede concluir que la afirmación es cierta para el Caso Base.
     
• Paso inductivo: Suponga que la afirmación es válida para el (N – 1) ^Paso . Entonces, a continuación se muestran los pasos para probarlo para el ^Paso N :

mcd(b, a%b) ——> (N – 1) pasos
Entonces,  
b >= f _{(N – 1 + 2)} es decir, b >= f _{(N + 1)}
a%b >= f _{(N – 1 + 1)} es decir, a%b >= f _N

• También se puede escribir como:

a = piso(a/b)*b + a%b

floor(a/b)*b significa el múltiplo más alto que está más cerca de b.

ex – piso (5/2) * 2 = 4. Si luego agregamos 5% 2 = 1, obtendremos a (= 5) de regreso.
 

• Ahora bien, (a/b) siempre sería mayor que 1 (como a >= b). Entonces, del resultado anterior, se concluye que:

a >= b + (a%b)
Esto implica, a >= f _{(N + 1)} + f _N

• Se sabe que cada número es la suma de los dos términos anteriores en una serie de Fibonacci . Esto implica f _{(N + 2)} = f _{(N + 1)} + f _N .

a >= f _{(N + 2)} y b >= f _{(N + 1)}

• Dado que la declaración anterior también es válida para el paso inductivo. Esto prueba que la afirmación es correcta.
• Antes de continuar, mire la fórmula de Binet :

Fórmula Binet:

f _norte = {((1 + √5)/2) ^norte – ((1 – √5)/2) ^norte }/√5
          o
f _norte ≈ ∅ ^norte

• donde, ∅ se conoce como la proporción áurea (∅≈1.618) , y f _N es el ^número N de Fibonacci .
• Ahora bien, ya se ha dicho que la complejidad temporal será proporcional a N, es decir, el número de pasos necesarios para reducir b a 0 .
• Entonces, para probar la complejidad del tiempo, se sabe que:

F _norte ≈ ∅ ^norte
norte ≈ Iniciar sesión _∅ (f _norte )

Ahora, a partir de la declaración anterior, se demuestra que usando el Principio de Inducción Matemática , se puede decir que si el algoritmo euclidiano para dos números a y b se reduce en N pasos , entonces a debería ser al menos f _{(N + 2)} y b debe ser al menos f _{(N + 1)} .

De los dos resultados anteriores se puede concluir que:

=> f _N+1 ≈ min(a, b)
=> N+1 ≈ log _∅ min(a, b)

=> O(N) = O(N+1) = log(mín(a, b))