Puede pensar que la programación dinámica se basa en una solución parcial hasta que tenga una solución completa. La recurrencia de una secuencia de DP fibonacci se ve así:
fib (i) = fib (i – 1) + fib (i – 2)
Donde fib (i) es el i-ésimo número de fibonacci.
- ¿Cómo puedo ser bueno en algoritmos si soy débil en matemáticas?
- ¿Qué tan difícil es aprender por sí mismo cómo codificar algoritmos eficientes?
- ¿Hay algún modelo físico o fenómeno que permita resolver rápidamente los problemas NP-hard?
- Cómo mejorar en la implementación de algoritmos
- Cómo probar la diferencia significativa entre dos algoritmos de clasificación
Para calcular el i-ésimo número de Fibonacci sumas los dos números de Fibonacci anteriores. Estas soluciones parciales para el i-ésimo número de fibonacci se almacenan en fib (i-1) y fib (i-2). Recuerde que fib (i-1) y fib (i-2) son ambos números de Fibonacci. El algoritmo recursivo recalcula los números de Fibonacci que ya resuelve, pero el algoritmo DP simplemente almacena estos resultados para que pueda reutilizarlos más tarde.
El algoritmo de programación dinámica (DP) se parece a esto:
func (enésimo):
fib = [] // fib [i] == ith número en secuencia
fib [1] = 1
fib [2] = 1
para i en el rango 3 -> enésimo:
// recurrencia
fib [i] = fib [i – 1] + fib [i – 2]
volver fib [nth]
Calcular fib [i] es O (1) y lo haces n veces. Claramente esto es O (n). El algoritmo es fácil de escribir, fácil de demostrar que es correcto y se ejecuta rápidamente. Incluso puede llevar esto al espacio constante con bastante facilidad.
Creo que 1.6 ^ n es el tiempo de ejecución ajustado del límite inferior para el ingenuo algoritmo recursivo. El análisis O (2 ^ n) para el algoritmo recursivo es el mismo sin un pequeño salto.
