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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Formalmente hablando, los números de Fibonacci F son generados por una regla simple:
n

No existe otra secuencia de números que haya sido estudiada de forma tan extensa o aplicada a
más campos del conocimiento (biología, demografía, arte, arquitectura, música, entre otros). De he-
cho, en ciencias de la computación es una de las secuencias favoritas, junto con la potencia de dos.

Para estimar la complejidad algorítmica se utilizará el número de oro o número áureo. Este es cono-
cido desde la época de los griegos y también tiene otros nombres como proporción dorada, divina
proporción, etc. El número en cuestión se define así: teniendo un segmento recto, se divide en dos
partes que cumplan lo siguiente:
a/b = (a+b) /a = 1.6180339887… =

Otra forma de encontrar la proporción dorada es utilizando la sucesión de Fibonacci:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 37
Si uno divide a un número entre el anterior, se acerca cada vez más a la famosa proporción áurea.

144/89 = 1.617977…

233/144 = 1.61865…

377/233 = 1.618025…

Ahora bien, la tarea para el cálculo de la complejidad no es fácil, pues la función del tiempo de eje-
cución del valor n es:

T(n) = T(n-1) + T(n-2)

Podemos hacer una hipótesis e intentar corroborarla. Supongamos que T(N) responde a una función
del siguiente tipo:

T(n) = k a .
n

30