Un número Fibonacci, usualmente con notación f(n)
, es la suma de los dos números fibonacci que le preceden. Esta sucesión empieza con f(0) = 0
, f(1) = 1
, f(2) = f(1) + f(0)
hasta f(x) = f(x-1) + f(x-2)
.
En este artículo veremos tres formas diferentes de encontrar un el resultado de aplicar la sucesión a un determinado número.
Recursión
Si usamos un sistema de recursión para calcular resultado de fibonacci para determinado número, por ejemplo 5, lo que obtendríamos es algo parecido a esto:
Algoritmo
- Debemos revisar que el número
n
que le estamos pasando a la función es igual o menor que1
, si este es el caso tenemos que devolvern
como el resultado de la función. - En caso contrario, la función se volverá a llamar a sí misma, pasándose como argumento el cálculo de
n-1
yn-2
respectivamente, posteriormente devolverá como su resultado la suma de ambas invocaciones.
Implementación
var fib = function(n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Complejidad (Time Complexity)
No entraré en detalle sobre cómo calcular la complejidad computacional, pero les dejo acá que es: 2^n
, por lo que podemos ver que entre más grande sea el número, crece enormemente la cantidad de recurso computacional.
Programación Dinámica Top-Down con memorización
El primer enfoque de programación dinámica que quiero que veamos es de top-down
. La idea aquí es similar al enfoque recursivo, pero la diferencia es que guardaremos las soluciones a los subproblemas que encontremos.
De esta forma, si nos encontramos con el mismo subproblema más de una vez, podemos usar nuestra solución guardada en lugar de tener que volver a calcularla. Esto nos permite calcular cada subproblema exactamente una vez.
Esta técnica de programación dinámica se llama memorización. Podemos ver cómo nuestro árbol de subproblemas se reduce cuando usamos la memorización:
Algoritmo
- Debemos revisar que el número
n
que le estamos pasando a la función es igual o menor que1
, si este es el caso tenemos que devolvern
como el resultado de la función. - En caso contrario, revisaremos si el subproblema ya ha sido solucionado con anterioridad, de no ser así, entonces procederemos a realizar el mismo proceso que utilizamos en la recursividad y guardaremos el resultado
- Devolveremos el resultado que hemos guardado, ya sea porque se haya computado por primera vez o por que ya lo hayamos calculado previamente.
Implementación
var fib = function(n) {
const map = new Map(); // creamos un mapa para guardar los valores
const dp = (x) => {
if (x <= 1) return x;
if (!map.has(x)) { // si NO hemos calculado el resultado
map.set(x, dp(x-1) + dp(x-2)) // lo calculamos y guardamos el valor
}
return map.get(x);
}
return dp(n);
};
Complejidad
Para este escenario la complejidad será de O(n)
, una complejidad mucho menor comparada con la de recursividad.
Programación Dinámica Bottom-Up
En el enfoque de programación dinámica Bottom-Up, lo que buscamos es solucionar los subproblemas en un orden diferente, es decir, primero resolvemos f(2)
, luego f(3)
, luego f(4)
y así hasta llegar a f(n)
. De esta forma no tenemos que memorizar nada, puesto que únicamente calcularemos aquellos subproblemas que son necesarios.
Algoritmo
- Tendremos un array donde iremos almacenando los valores de cada subproblema, este lo inicializaremos con los resultados base
0, 1
. - Recorreremos desde la posición 2 hasta llegar a
n
(incluyéndola) para añadir la solución de cada subproblema. - Devolveremos luego nuestro array en la última posición.
Implementación
var fib = function(n) {
const sol = [0, 1];
for (let i = 2; i<= n; i++) {
sol[i] = sol[i -1] + sol[i - 2];
}
return sol[n];
};
Complejidad
En este caso la complejidad computacional sigue siendo de O(n)
.
Bonus
El cálculo de complejidad no solo se debe considerar a nivel computacional, también a nivel de uso de memoria, por lo que si vemos, por ejemplo, la solución Bottom-Up
, no es óptima puesto que hemos guardado en memoria datos predecesores que no son necesarios.
Es más fácil visualizarlo si pensamos en que queremos el fibonacci de 10, tendríamos algo como [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
, pero realmente para tener el fibonacci de 10
solo es necesario tener en memoria los últimos 2 valores 21
y 34
.
Implementación
var fib = function(n) {
if (n <= 1) return n;
let prev2 = 0;
let prev1 = 1;
let c = 0;
for (let i = 2; i<= n; i++) {
c = prev1 + prev2;
prev2 = prev1;
prev1 = c;
}
return c;
};
Conclusiones
Hemos llegado hasta el final del artículo, déjame saber qué te ha parecido las soluciones, ¿cambiarías algo?, ¿hay algo que no entiendes?