Así es como funciona:
1. Estructura recursiva: Los problemas de programación dinámica a menudo se prestan a soluciones recursivas. Una implementación recursiva ingenua calcularía repetidamente las soluciones a los mismos subproblemas, lo que conduce a la complejidad del tiempo exponencial.
2. Resultados de almacenamiento: La memoria introduce una estructura de datos (generalmente una tabla de hash o una matriz) para almacenar las soluciones a subproblemas ya calculados. Esta estructura a menudo se llama "memorando" o "caché".
3. Comprobando la nota: Antes de resolver recursivamente un subproblema, el algoritmo primero verifica la nota. Si la solución ya está presente (lo que significa que el subproblema se ha resuelto antes), se recupera directamente de la nota, evitando la recomputación.
4. Almacenando el resultado: Si la solución no se encuentra en la nota, el algoritmo resuelve recursivamente el subproblema, y luego * almacena * el resultado en la nota antes de devolverlo.
Ejemplo:
Considere el cálculo de la secuencia Fibonacci. Un enfoque recursivo ingenuo tiene una complejidad exponencial porque recalcula muchos números de Fibonacci varias veces. Con memoización:
`` `Python
memo ={} # inicializar la nota
Def fibonacci_memo (n):
Si n en memo:
return Memo [n] # recuperar de la nota si ya está calculado
Si n <=1:
regresar n
demás:
resultado =Fibonacci_Memo (N-1) + Fibonacci_Memo (N-2)
Memo [n] =resultado # almacene el resultado en la nota
Resultado de retorno
print (fibonacci_memo (5)) # Salida:5
`` `` ``
En este ejemplo, `Memo` almacena los números de fibonacci calculados. Cuando se llama `fibonacci_memo (5)`, llama recursivamente `fibonacci_memo (4)` y `fibonacci_memo (3)`. `fibonacci_memo (3)` llamarán recursivamente `fibonacci_memo (2)` y `fibonacci_memo (1)`. Sin embargo, una vez `fibonacci_memo (1)` o `fibonacci_memo (2)` se calcula y se almacena en `memo`, las llamadas posteriores a estos mismos subproblemas devolverán directamente los resultados almacenados, evitando el cálculo redundante. Esto reduce la complejidad del tiempo de exponencial a lineal.
En esencia, la memoización transforma un algoritmo recursivo de tiempo potencialmente exponencial en un algoritmo de tiempo lineal (o tiempo polinomial en otros casos) al aprovechar la potencia del almacenamiento en caché de resultados previamente calculados. Es una poderosa técnica de optimización utilizada con frecuencia junto con la programación dinámica para mejorar la eficiencia.