¿Qué es la memorización? Un tutorial completo

El término “ Memoización ” proviene de la palabra latina “ memorandum ” ( recordar ), que comúnmente se abrevia como “memo” en inglés americano, y que significa “transformar los resultados de una función en algo para recordar”.

En informática, la memorización se utiliza para acelerar los programas informáticos al eliminar el cálculo repetitivo de los resultados y al evitar llamadas repetidas a funciones que procesan la misma entrada.

Tabla de contenido

   

¿Por qué se usa Memoización?

La memorización es una forma específica de almacenamiento en caché que se utiliza en la programación dinámica . El propósito del almacenamiento en caché es mejorar el rendimiento de nuestros programas y mantener los datos accesibles que se pueden usar más adelante. Básicamente almacena el resultado previamente calculado del subproblema y usa el resultado almacenado para el mismo subproblema. Esto elimina el esfuerzo adicional de calcular una y otra vez para el mismo problema. Y ya sabemos que si el mismo problema ocurre una y otra vez, entonces ese problema es de naturaleza recursiva.

¿Dónde usar Memoización?

Podemos utilizar la técnica de memorización donde entra en juego el uso de los resultados calculados previamente . Este tipo de problema se usa principalmente en el contexto de la recursividad , especialmente con problemas que involucran subproblemas superpuestos .

Tomemos un ejemplo donde el mismo subproblema se repite una y otra vez. 

Ejemplo para mostrar dónde usar la memorización: 

Let us try to find the factorial of a number.

A continuación se muestra un método recursivo para encontrar el factorial de un número:

int factorial(sin signo int n)
{
   if (n == 0)
       devuelve 1;
   devuelve n * factorial(n – 1);
}

¿Qué pasa si usamos este método recursivo?

Si escribe el código completo para el fragmento anterior, notará que habrá 2 métodos en el código:

1. factorial(n)
2. main()

Ahora, si tenemos varias consultas para encontrar el factorial, como encontrar el factorial de 2, 3, 9 y 5, entonces necesitaremos llamar al método factorial() 4 veces:

factorial(2)
factorial(3)
factorial(9)
factorial(5)

Entonces es seguro decir que para encontrar el factorial de números K números, la complejidad de tiempo necesaria será O(N*K)

• O(N) para encontrar el factorial de un número particular, y
• O(K) para llamar al método factorial() K diferentes veces.

¿Cómo la Memorización puede ayudar con tales problemas?

Si nos fijamos en el problema anterior, mientras calculamos el factorial de 9: 

• Estamos calculando el factorial de 2
• También estamos calculando el factorial de 3,
• y estamos calculando el factorial de 5 también

Por lo tanto, si almacenamos el resultado de cada factorial individual en el primer momento del cálculo, podemos devolver fácilmente el factorial de cualquier número requerido en solo O(1) tiempo. Este proceso se conoce como Memoización . 

Solución usando Memoización (¿Cómo funciona la memorización?):

Si primero encontramos el factorial de 9 y almacenamos los resultados de los subproblemas individuales, podemos imprimir fácilmente el factorial de cada entrada en O(1).

Por lo tanto, la complejidad temporal para encontrar números factoriales utilizando la memorización será O(N)

• O(N) para encontrar el factorial de la entrada más grande
• O(1) para imprimir el factorial de cada entrada.

Tipos de Memoización

La implementación de la memorización depende de los parámetros cambiantes que son responsables de resolver el problema. Hay varias dimensiones de almacenamiento en caché que se utilizan en la técnica de memorización, a continuación se muestran algunas de ellas:

• Memoización 1D: la función recursiva que tiene solo un argumento cuyo valor no era constante después de cada llamada de función.
• Memoización 2D: la función recursiva que tiene solo dos argumentos cuyo valor no era constante después de cada llamada de función.
• Memoización 3D : la función recursiva que tiene solo tres argumentos cuyos valores no eran constantes después de cada llamada de función.

¿Cómo se utiliza la técnica de Memoización en la Programación Dinámica?

La programación dinámica ayuda a resolver eficientemente problemas que tienen subproblemas superpuestos y propiedades de subestructura óptimas. La idea detrás de la programación dinámica es dividir el problema en subproblemas más pequeños y guardar el resultado para uso futuro, eliminando así la necesidad de calcular el resultado repetidamente.

Hay dos enfoques para formular una solución de programación dinámica:

1. Enfoque de arriba hacia abajo:  este enfoque sigue la técnica de memorización . Consiste en la recursividad y el almacenamiento en caché . En computación, la recursividad representa el proceso de llamar funciones repetidamente, mientras que el caché se refiere al proceso de almacenar resultados intermedios.
2. Enfoque ascendente: este enfoque utiliza la técnica de tabulación para implementar la solución de programación dinámica. Aborda los mismos problemas que antes, pero sin recursividad. En este enfoque, la iteración reemplaza a la recursividad. Por lo tanto, no hay error de desbordamiento de pila ni sobrecarga de procedimientos recursivos.

/a<>¿En qué se diferencia la memorización de la tabulación?

Para obtener más detalles, consulte: Tabulación frente a Memoización

Problemas de práctica de codificación sobre memorización

Pregunta	Artículo	Práctica	Video
Cuente las formas de llegar al escalón n.	Vista	Resolver	Reloj
Problema de separación de palabras | DP-32	Vista	Resolver	Reloj
Programa para números de Fibonacci	Vista	Resolver	Reloj
enésimo número catalán	Vista	Resolver	Reloj
Problema de la mina de oro	Vista	Resolver	Reloj
Problema de suma de subconjuntos	Vista	Resolver	Reloj
cortar una varilla	Vista	Resolver	Reloj
Ruta de costo mínimo	Vista	Resolver	Reloj
Número mínimo de saltos para llegar al final	Vista	Resolver	Reloj
Substring palindrómica más larga | Serie 1	Vista	Resolver	Reloj
Subsecuencia de repetición más larga	Vista	Resolver	Reloj
Cuente las formas de llegar al enésimo escalón usando el paso 1, 2 o 3	Vista	Resolver	Reloj
Cuente las diferentes formas de expresar N como la suma de 1, 3 y 4	Vista	Resolver	Reloj
Contar el número de formas de cubrir una distancia	Vista	Resolver	Reloj
Recuento de arrays que tienen elementos consecutivos con diferentes valores	Vista	Resolver	Reloj
Subarreglo contiguo de suma más grande	Vista	Resolver	Reloj
Subarreglo contiguo de suma más pequeña	Vista	Resolver	Reloj
Caminos únicos en una cuadrícula con obstáculos	Vista	Resolver	Reloj
Diferentes formas de sumar n usando números mayores o iguales que m	Vista	Resolver	Reloj

Preguntas frecuentes (FAQ) sobre Memoización

1: ¿Es la memoización mejor que la DP?

La memorización es el enfoque de arriba hacia abajo para resolver un problema con programación dinámica. Se llama memoización porque crearemos un memo para los valores devueltos al resolver cada problema.

2: ¿Es lo mismo memoización que almacenamiento en caché?

La memorización es en realidad un tipo específico de almacenamiento en caché. El término almacenamiento en caché generalmente puede referirse a cualquier técnica de almacenamiento (como almacenamiento en caché HTTP) para uso futuro, pero la memorización se refiere más específicamente a la función de almacenamiento en caché que devuelve el valor.

3: ¿Por qué la memorización es de arriba hacia abajo?

4: ¿La memorización usa recursividad?

La memorización sigue un enfoque de arriba hacia abajo para resolver el problema. Consiste en la recursividad y el almacenamiento en caché. En computación, la recursividad representa el proceso de llamar funciones repetidamente, mientras que el caché se refiere al proceso de almacenar resultados intermedios.

5: ¿Debo usar tabulación o memorización?

Para los problemas que requieren que se resuelvan todos los subproblemas, la tabulación generalmente supera a la memorización por un factor constante. Esto se debe a que la tabulación no tiene sobrecarga de recursividad, lo que reduce el tiempo para resolver la pila de llamadas de recursividad desde la memoria de la pila.
Siempre que sea necesario resolver un subproblema para resolver el problema original, es preferible la memorización, ya que un subproblema se resuelve de forma perezosa, es decir, sólo se realizan los cálculos necesarios.

6: ¿Dónde se usa la memorización?

La memorización es una técnica de optimización que se utiliza para acelerar los programas informáticos mediante el almacenamiento en caché de los resultados de llamadas a funciones caras y devolverlos cuando se encuentran de nuevo las mismas entradas.

7: ¿Por qué se llama memorización?

El término «memoización» proviene de la palabra latina «memorandum» («recordar»), que comúnmente se abrevia como «memo» en inglés americano, y que significa «transformar los resultados de una función en algo para recordar».

8: ¿Cómo reduce la memorización la complejidad del tiempo?

Resolver el mismo problema una y otra vez lleva tiempo y aumenta la complejidad del tiempo de ejecución del programa en general. Este problema se puede resolver manteniendo algo de caché o memoria donde almacenaremos el resultado ya calculado del problema para alguna entrada en particular. De modo que si no queremos volver a calcular el mismo problema, simplemente podemos usar el resultado que está almacenado en la memoria y reducir la complejidad del tiempo.

9: ¿Cuál es la diferencia entre memorización y almacenamiento en caché?

La memorización es en realidad un tipo específico de almacenamiento en caché que implica almacenar en caché el valor de retorno de una función en función de la entrada. El almacenamiento en caché es un término más general. Por ejemplo, el almacenamiento en caché de HTTP es almacenamiento en caché pero no es memorización.

10: ¿Por qué la tabulación es más rápida que la memorización?

La tabulación suele ser más rápida que la memorización, porque es iterativa y la resolución de subproblemas no requiere la sobrecarga de llamadas recursivas.

Conclusión

La memorización es un concepto de programación y se puede aplicar a cualquier lenguaje de programación. Su objetivo absoluto es optimizar el programa. Por lo general, este problema se ve cuando los programas realizan cálculos pesados. Esta técnica almacena en caché todo el resultado anterior que se calcula para que no tenga que volver a calcular para el mismo problema. 

Artículos relacionados: 

• Memoización usando decoradores en Python
• Memoización de JavaScript