Este algoritmo trata de la construcción de la sucesión de los números de Fibonacci hasta un entero \(n\), que es un parámetro de entrada del algoritmo. La sucesión de Fibonacci es una sucesión infinita de números naturales como la siguiente:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....
Que se representa mediante la siguiente ecuación:
\[ Fibonacci(n) = \begin{cases} 1 & \text{si } x = 0,1 \\ Fibonacci(n-1)+Fibonacci(n-2) & \text{si } n > 1 \end{cases} \]
Como se puede observar en la ecuación, se podría resolver mediante un algoritmo recursivo, pero tendría un tiempo de ejecución que crece exponencialmente con \(n\). Por esta razón, planteamos una solución alternativa mediante la aplicación de un algoritmo basado en programación dinámica que tiene un coste lineal. El fundamento de dicho algoritmo está en que se van almacenando los resultados parciales en una tabla. Por ejemplo, si queremos calcular \(Fibonacci(5)\), según la ecuación necesitamos conocer los valores de \(Fibonacci(4)\) y \(Fibonacci(3)\). Dichos valores ya los tendremos almacenados previamente, al haber empezado a calcular los términos desde los casos triviales, \(Fibonacci(0)\) y \(Fibonacci(1)\), y desde ahí ir calculando los sucesivos términos aumentando el valor de \(n\). Además, si observamos el algoritmo observaremos que sólo necesitamos tener almacenados los dos últimos términos de la sucesión, por lo que se reducirá la complejidad espacial del algoritmo.
En la sección de visualización puedes aprender este algoritmo basado en la programación dinámica y observar su funcionamiento y evolución de las estructuras de datos implicadas para un valor concreto de \(n\), que será el parámetro de entrada del algoritmo. Puedes controlar la evolución del algoritmo mediante los botones de control de la parte superior de la página.