Page 40 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 40
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Algoritmo 1.9. Programación de la función de Fibonacci en forma iterativa
¿Cuánto tiempo toma el algoritmo? El loop tiene solo un paso y se ejecuta n-1 veces, por lo que el
algoritmo se considera lineal en n. De un tiempo exponencial, hemos pasado a un tiempo lineal: un
gran progreso en tiempo de ejecución. Es ahora razonable calcular F o aun F .
200 200000
Opción C: En forma directa
Ahora bien, se puede realizar un algoritmo en forma directa, en este caso, la fórmula Binet (1786-
1856) especifica que Fib(n) = ((1+√5) – (1-√5) ) / (2 √5), lo que el algoritmo 1.10 se puede progra-
n
n
n
mar de este modo:
Algoritmo 1.10. Programación de la función de Fibonacci utilizando la fórmula Binet
34
