varios

Algoritmo de Euclides

El teorema de Lamé afirma que el caso peor para este algoritmo es cuando se le pide calcular el máximo común divisor de dos números consecutivos dela sucesión de Fibonacci. Por ejemplo, si se desea calcular el máximo común divisor de  y  se obtiene la siguiente secuencia de operaciones:
Paso
Operación
Significado
1
89 divididoentre 55 es 1 y sobran 34

2
55 dividido entre 34 es 1 y sobran 21

3
34 dividido entre 21 es 1 y sobran 13

4
21 dividido entre 13 es 1 y sobran 8

5
13 divididoentre 8 es 1 y sobran 5

6
8 dividido entre 5 es 1 y sobran 3

7
5 dividido entre 3 es 1 y sobran 2

8
3 dividido entre 2 es 1 y sobran 1

9
2 dividido entre 1 es 2 y sobra0

En este ejemplo se observa que con estos dos números de dos dígitos decimales, se necesita hacer 9 divisiones. En general, el número de divisiones efectuadas por el algoritmonunca supera 5 veces el número de dígitos que tienen estos números. En términos de complejidad computacional, esto significa que se requieren  divisiones para calcular el máximocomún divisor de  y  donde.
El número promedio de divisiones efectuadas por el algoritmo se estuvo investigando desde 1968, pero sólo hasta apenas el año 2002, Brigitte Valléedemostró que si los dos números se pueden representar con  bits, entonces el número promedio de divisiones necesarias es .
Sin embargo, no basta con saber el número de divisiones. Hayque recordar que el algoritmo de Euclides funciona tanto para polinomios como para números enteros, y en general, cualquier dominio Euclídeo. En cada caso, la complejidad delalgoritmo depende del número de divisiones efectuadas y del costo de cada división. En el caso de los polinomios, el número de divisiones es  donde  es el grado de los polinomios.