algorithm - nbsp - metodo simplex tabular ejercicios resueltos
Método de memoización o tabulación para la programación dinámica. (3)
Asintóticamente, una implementación de programación dinámica que es de arriba hacia abajo es lo mismo que ir de abajo hacia arriba, asumiendo que estás usando la misma relación de recurrencia. Sin embargo, de abajo hacia arriba es generalmente más eficiente debido a la sobrecarga de recursión que se utiliza en la memoria.
Hay muchos problemas que se pueden resolver utilizando la programación dinámica, por ejemplo, la subsecuencia más larga y creciente. Este problema se puede resolver utilizando 2 enfoques.
- Memoization (arriba hacia abajo): uso de la recursividad para resolver el subproblema y almacenar el resultado en alguna tabla hash.
- Tabulación (de abajo hacia arriba): utiliza el enfoque iterativo para resolver el problema resolviendo los subproblemas más pequeños primero y luego usándolo durante la ejecución del problema más grande.
Mi pregunta es ¿cuál es el mejor enfoque en términos de complejidad de tiempo y espacio?
Respuesta corta: depende del problema!
La memorización generalmente requiere más código y es menos directa, pero tiene ventajas computacionales en algunos problemas, principalmente en los que no es necesario calcular todos los valores para que toda la matriz alcance la respuesta.
La tabulación es más sencilla, pero puede calcular valores innecesarios. Si necesita calcular todos los valores, este método suele ser más rápido, debido a la sobrecarga más pequeña.
Si el problema tiene overlapping sub-problems propiedad de overlapping sub-problems Memoization , use Memoization , de lo contrario, depende del problema