Page 37 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 37
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Entonces, se debe satisfacer que
k a = k a n-1 + k a .
n
n-2
Realizando una simplificación, se tiene:
a = a + 1,
2
de donde se despeja
a – a -1 = 0,
2
siendo esta una ecuación característica y una de sus raíces se conoce como:
a = (1+√5) / 2 ~ 1,6180339887…
o sea,
T(n) ~ 1,6180339887 .
n
En otras palabras,
T(n) O(1,618 ).
n
En realidad, la secuencia de Fibonacci crece tan rápido como la potencia de dos: por ejemplo, F
30
rebasa el millón, y la secuencia F tiene aproximadamente veintiún dígitos de largo. Para colocar la
100
complejidad en potencia de dos se realiza la siguiente trasformación:
1.618 = 2 x n
n
Log (1.618) = log (2) x n
n
n Log (1.618) = x n log (2)
x = n Log (1.618) / (n log (2)) = 0.694.
En general, F ≈ 2 0.694n .
n
Pero ¿cuál es el valor exacto de F o de F ? Fibonacci nunca supo la respuesta. Para saberlo,
100 200
necesitamos un algoritmo para computar el n-ésimo número de Fibonacci.
Una idea es utilizar la definición recursiva de F El pseudocódigo se muestra enseguida:
n.
Función fib(n){
Si n = 0 retorna 0
Si n = 1 retorna 1
Retorna fib(n-1) + fib(n-2)
}
31
