Memoización:
* Enfoque: De arriba hacia abajo (recursivo con almacenamiento en caché). Comienza con el problema original y lo divide recursivamente en subproblemas más pequeños. Como se resuelve cada subproblema, su resultado se almacena (almacenado en caché) en una estructura de datos (generalmente un diccionario o tabla). Si se encuentra el mismo subproblema nuevamente, el resultado almacenado en caché se recupera en lugar de ser recomputado.
* Implementación: Típicamente implementado utilizando funciones recursivas y un caché. El caché generalmente se gestiona implícitamente a través de llamadas recursivas.
* Idoneabilidad del problema: Bien adecuado para problemas donde no todos los subproblemas necesariamente necesitan ser resueltos. Solo calcula y almacena los resultados de subproblemas que realmente son necesarios para resolver el problema principal.
* Orden de ejecución: El orden de resolver subproblemas está determinado por la recursión, siguiendo naturalmente la estructura del problema.
* Impacto de eficiencia:
* * Boost de rendimiento:* mejora significativamente el rendimiento cuando el algoritmo encuentra los mismos subproblemas varias veces durante la recursión. Reduce la complejidad del tiempo exponencial al tiempo polinomial en muchos casos.
* * Overhead:* incurre en una sobrecarga debido a las búsquedas de gastos generales y de caché de llamadas de función. Esta sobrecarga a veces puede ser significativa para problemas más pequeños donde el costo de cálculo ya es bajo.
* * Complejidad del espacio:* usa espacio para el caché, que almacena los resultados de los subproblemas resueltos. El espacio requerido depende de la cantidad de subproblemas únicos que realmente se resuelven.
* Legabilidad: Puede ser más intuitivo y más fácil de implementar que la programación dinámica, especialmente cuando la estructura recursiva del problema es clara.
Programación dinámica:
* Enfoque: De abajo hacia arriba (iterativo con tabulación). Resuelve todos los subproblemas posibles en un orden específico, generalmente comenzando con los subproblemas más pequeños y construyendo los más grandes. Los resultados de todos los subproblemas se almacenan en una tabla (a menudo una matriz multidimensional).
* Implementación: Típicamente implementado utilizando bucles iterativos y una tabla. El orden de cálculo está controlado explícitamente por los bucles.
* Idoneabilidad del problema: El mejor adecuado para problemas en los que se deben resolver todos los subproblemas para llegar a la solución final.
* Orden de ejecución: El orden en el que se resuelven subproblemas se define explícitamente por el algoritmo, generalmente en función de las dependencias entre subproblemas.
* Impacto de eficiencia:
* * Boost de rendimiento:* mejora significativamente el rendimiento evitando los cálculos redundantes. Reduce la complejidad del tiempo exponencial al tiempo polinomial en muchos casos. Dado que usa bucles iterativos, la sobrecarga de las llamadas de funciones generalmente se evita, lo que lo hace potencialmente más rápido que la memoización.
* * Overhead:* usa espacio para la tabla, que almacena los resultados de * todos * posibles subproblemas, incluso aquellos que podrían no usarse directamente para resolver el problema principal.
* * Complejidad del espacio:* usa espacio para la tabla, que almacena los resultados de todos los subproblemas posibles. Esto puede ser más alto que la memoización si no se necesitan algunos subproblemas.
* Legabilidad: Puede ser menos intuitivo que la memoización, especialmente para problemas complejos. Requiere una planificación cuidadosa para determinar el orden correcto de resolver subproblemas.
Diferencias clave resumidas:
| Característica | Memoización | Programación dinámica |
| ---------------- | -------------------------------------------- | ------------------------------------------- |
| Enfoque | De arriba hacia abajo (recursivo) | De abajo hacia arriba (iterativo) |
| Implementación | Funciones recursivas + caché | Bucles iterativos + mesa |
| Problema idoneidad | No todos los subproblemas pueden necesitar ser resueltos | Todos los subproblemas deben resolverse |
| Orden de ejecución | Determinado por recursión | Explícitamente definido (a menudo iterativo) |
| Uso espacial | Almacena resultados de * resuelto * subproblemas | Almacena resultados de * todos posibles * subproblemas |
| Overhead | Function Call Sobreve, Búsquedas de caché | Menos sobrecarga (sin llamadas de función) |
| Leyabilidad | A menudo más intuitivo | Puede ser menos intuitivo |
Impacto en la eficiencia (rendimiento):
* Complejidad del tiempo: Tanto la memoización como la programación dinámica pueden reducir drásticamente la complejidad del tiempo de los algoritmos que implican subproblemas superpuestos, a menudo de exponencial (por ejemplo, o (2^n)) a polinomial (por ejemplo, o (n^2), o (n)).
* Complejidad espacial: Ambas técnicas aumentan la complejidad del espacio. Memoization almacena los resultados de subproblemas resueltos, mientras que la programación dinámica almacena los resultados de todos los subproblemas posibles. La elección entre los dos puede depender de las restricciones de memoria y del problema específico.
* Rendimiento práctico:
* En muchos casos, la programación dinámica puede ser ligeramente más rápida debido a la sobrecarga más baja de los bucles iterativos en comparación con las llamadas de funciones recursivas.
* Sin embargo, si solo una pequeña fracción de los posibles subproblemas debe resolverse, la memoización puede ser más eficiente en términos de tiempo y espacio porque solo calcula y almacena los resultados necesarios.
Cuándo usar cuál:
* Use memoización:
* Cuando el problema tiene una formulación recursiva natural.
* Cuando no todos los subproblemas deben resolverse.
* Cuando se prioriza la legibilidad y la facilidad de implementación.
* Use programación dinámica:
* Cuando todos los subproblemas deben resolverse para obtener la solución final.
* Cuando el rendimiento es crítico y se debe minimizar los gastos generales de las llamadas de función.
* Cuando un enfoque de abajo hacia arriba es más natural para el problema.
Ejemplo (secuencia Fibonacci):
Memoization (Python):
`` `Python
def fib_memo (n, memo ={}):
Si n en memo:
Return Memo [N]
Si n <=1:
regresar n
Memo [n] =fib_memo (n - 1, memo) + fib_memo (n - 2, memo)
Return Memo [N]
print (fib_memo (10)) # Salida:55
`` `` ``
Programación dinámica (Python):
`` `Python
def fib_dp (n):
fib_table =[0] * (n + 1)
Si n> =0:
fib_table [0] =0
Si n> =1:
fib_table [1] =1
para i en el rango (2, n + 1):
fib_table [i] =fib_table [i - 1] + fib_table [i - 2]
return fib_table [n]
print (fib_dp (10)) # Salida:55
`` `` ``
En este ejemplo, tanto la memoización como la programación dinámica transforman la solución recursiva ingenua (que tiene complejidad de tiempo exponencial) en un algoritmo con complejidad del tiempo O (N). Sin embargo, la versión de programación dinámica evita la sobrecarga de llamadas de función y generalmente será un poco más rápida en la práctica.