Page 38 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 38
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
El código del algoritmo 1.8 en C es el siguiente:
Algoritmo 1.8. La función Fibonacci escrita en forma recursiva
Cada vez que se tiene un algoritmo surgen preguntas que se deben responder:
1. ¿Es correcto?
2. ¿Cuánto tiempo tarda en dar el resultado?
3. ¿Se puede mejorar?
La primera pregunta no se discute aquí, ya que el algoritmo es precisamente la definición de Fibon-
acci para F . Pero la segunda pregunta demanda una respuesta.
n
Sea T(n) el número de pasos computacionales necesarios para computar fib(n), ¿qué podemos decir
sobre esta función? Si n < 2, el procedimiento termina casi de forma inmediata, justo después de
un par de pasos. Para números mayores existen invocaciones recursivas de fib( ), así tenemos lo
siguiente:
El tiempo de ejecución del algoritmo crece tan rápido como los números de Fibonacci: T(n) es expo-
nencial en n, lo cual implica que el algoritmo es impráctico, excepto para valores muy pequeños de n.
Por ejemplo, para calcular F , la función fib( ) se ejecuta T(200) ≥ F ≥ 2 pasos elementales de
138
200 200
cómputo. ¿Cuánto tiempo se requiere? Eso depende de la computadora usada. En este momen-
to, una de las más veloces en el mundo es la NEC Earth Simulator, con 400 trillones de pasos por
segundo. Pero aun para esta máquina, fib(200) tardará al menos 2 segundos. Esto significa que si
92
32
