Complejidad Temporal
O(n)
La secuencia de Fibonacci es un ejemplo clásico de programación dinámica. Cada número es la suma de los dos anteriores: F(n) = F(n-1) + F(n-2).
Cómo funciona (Tabulación Bottom-Up):
1. Crear una tabla para almacenar valores calculados
2. Establecer casos base: F(0) = 0, F(1) = 1
3. Llenar la tabla iterativamente: F(i) = F(i-1) + F(i-2)
4. Retornar F(n)
Complejidad Temporal: O(n)
Complejidad Espacial: O(n) — optimizable a O(1)
Comparación:
- Recursión ingenua: O(2^n) — exponencial
- Memoización (top-down): O(n)
- Tabulación (bottom-up): O(n)
La Programación Dinámica evita cálculos redundantes almacenando resultados previamente computados. Fibonacci es la ilustración más simple de esta técnica.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Fibonacci (Programación Dinámica)?
- La secuencia de Fibonacci es un ejemplo clásico de programación dinámica. Cada número es la suma de los dos anteriores: F(n) = F(n-1) + F(n-2).
- ¿Cuál es la complejidad de Fibonacci (Programación Dinámica)?
- Tiempo (promedio): O(n) · Espacio: O(n)
- ¿Para quién es este visualizador de Fibonacci (Programación Dinámica)?
- La visualización de Fibonacci (Programación Dinámica) está pensada para nivel intermedio, dentro de la categoría Programación Dinámica. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Fibonacci (Programación Dinámica)?
- En la misma categoría (Programación Dinámica) puedes explorar: Knapsack 0/1, Longest Common Subsequence. Todos tienen visualización interactiva.