Page 39 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

iniciamos el cómputo hoy, estaría trabajando después de que el sol se tornara en una estrella roja
gigante.

Pero la tecnología ha mejorado de tal forma que los pasos de cómputo se han duplicado aproxima-
damente cada 18 meses, fenómeno al cual se le conoce como ley de Moore. Con este extraordinario
crecimiento, posiblemente la función fib se ejecutará más rápido para el próximo año. Verifiquemos
este dato: el tiempo de ejecución de fib(n) ≈ 2 0.694n ≈ (1.6) , por lo que toma 1.6 veces más tiempo
n
para computar F que F . Y desde la ley de Moore, el poder de cómputo crece aproximadamente
n+1 n
1.6 veces cada año.

Si nosotros podemos computar de forma razonable F con el crecimiento de la tecnología, el si-
100
guiente año se podrá calcular F , el próximo año F y así sucesivamente; es decir, solo un número
101 102
de Fibonacci más cada año. Así, es el comportamiento de un tiempo exponencial. El algoritmo se
vuelve ineficiente por la razón de que una llamada a fib(n) se tiene una cascada de llamadas recursi-
vas en las cuales la mayoría de ellas son repetitivas (figura 1.5).

Figura 1.5. Árbol recursivo con la función de Fibonacci

Opción B: En forma lineal

En corto, nuestro algoritmo recursivo es correcto, pero sumamente ineficiente. ¿Podemos hacerlo
mejor? El algoritmo 1.9 muestra en lenguaje C algo más sencillo:

33