Complejidad Temporal
Mejor: O(1)
Prom: O(log min(a, b))
Peor: O(log min(a, b))
El Algoritmo de Euclides calcula el máximo común divisor (MCD) de dos enteros: el número más grande que divide a ambos sin dejar residuo. Es uno de los algoritmos más antiguos que se siguen usando.
La idea clave: cualquier número que divide a a y a b también divide su residuo a mod b. Por eso gcd(a, b) = gcd(b, a mod b), y repetirlo encoge el par hasta que el residuo es 0.
Cómo funciona:
1. Divide a entre b para obtener el residuo r = a mod b
2. Si r es 0, entonces b es la respuesta
3. Si no, reemplaza el par por (b, r) y repite
Por qué es rápido:
El residuo se reduce al menos a la mitad cada dos pasos, así que el número de divisiones es O(log min(a, b)) — muchísimo menos que probar cada divisor candidato.
Complejidad Temporal:
Mejor: O(1)
Promedio: O(log min(a, b))
Peor: O(log min(a, b))
Complejidad Espacial: O(1) en la versión iterativa
Propiedades:
- Determinista, sin aleatoriedad
- Usa solo la operación módulo — no requiere factorización
- Base del Algoritmo de Euclides Extendido, los inversos modulares y la simplificación de fracciones
Descrito por el matemático griego Euclides en sus Elementos (~300 a.C.), este algoritmo aún sustenta la aritmética moderna, la criptografía (matemática de claves RSA) y los sistemas de álgebra computacional.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Algoritmo de Euclides?
- El Algoritmo de Euclides calcula el máximo común divisor (MCD) de dos enteros: el número más grande que divide a ambos sin dejar residuo. Es uno de los algoritmos más antiguos que se siguen usando.
- ¿Cuál es la complejidad de Algoritmo de Euclides?
- Tiempo (promedio): O(log min(a, b)) · Espacio: O(1)
- ¿Para quién es este visualizador de Algoritmo de Euclides?
- La visualización de Algoritmo de Euclides está pensada para nivel principiante, dentro de la categoría Matemáticas. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Algoritmo de Euclides?
- En la misma categoría (Matemáticas) puedes explorar: Sieve of Eratosthenes. Todos tienen visualización interactiva.