La condición «memorizar«viene de la palabra latina»memorándum†recuerda), que a menudo se abrevia como «memo» en inglés americano, que significa «convertir 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.
¿Qué es la memorización?
¿Por qué se usa la Memorización?
La memorización es una forma específica de almacenamiento en caché que se usa en programación dinámica† El propósito del almacenamiento en caché es mejorar el rendimiento de nuestros programas y mantener los datos accesibles para su uso posterior. Básicamente almacena el resultado del subproblema calculado previamente y utiliza el resultado almacenado para el mismo subproblema. Esto elimina la molestia adicional de calcular una y otra vez para el mismo problema. Y ya sabemos que si el mismo problema sigue ocurriendo una y otra vez, ese problema es de naturaleza recursiva.
¿Dónde usar Memoización?
Podemos usar la técnica de memorización donde el usando los resultados calculados previamente viene a la vista. Este tipo de problema generalmente se usa en el contexto de la recursividad, especialmente para problemas con subproblemas superpuestos.
Tomemos un ejemplo donde el mismo subproblema se repite una y otra vez.
Ejemplo para mostrar dónde se debe 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 (int n sin signo)
†
si (n == 0)
devolver 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 múltiples consultas para encontrar el factorial, como encontrar factoriales de 2, 3, 9 y 5, entonces necesitamos llamar al método factorial() 4 veces:
factorial(2) factorial(3) factorial(9) factorial(5)
Método recursivo para encontrar Factorial
Entonces es seguro decir que para encontrar un factorial de números K números, la complejidad de tiempo necesaria será: O(N*K)
- A) para encontrar el factorial de un número dado, y
- OKEY) para llamar al método factorial() K varias veces.
¿Cómo la Memorización puede ayudar con tales problemas?
Si nos damos cuenta en el problema anterior, mientras que el factor de cálculo de 9:
- Calculamos el factorial de 2
- También calculamos el factorial de 3,
- y también calculamos el factorial de 5
Por lo tanto, si almacenamos el resultado de cada factorial individual en el primer cálculo, podemos devolver fácilmente el factorial de cualquier número requerido en solo O(1) tiempo. Este proceso se conoce como: memorizar†
Solución con 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 cualquier entrada en O(1).
Por lo tanto, la complejidad temporal para encontrar números factoriales utilizando la memorización será: A)
- A) para encontrar el factorial de la entrada más grande
- O(1) para imprimir el factorial de cada entrada.
Tipos de memorización
La implementación del almacenamiento en memoria depende de los parámetros cambiantes responsables de resolver el problema. Hay varias dimensiones de almacenamiento en caché utilizadas en la técnica de memo, a continuación se presentan 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 problemas de manera eficiente con 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 la necesidad de calcular el resultado repetidamente.
Hay dos enfoques para formular una solución de programación dinámica:
- Enfoque de arriba hacia abajo: Este enfoque sigue la memorizar técnica† Consiste en repetición y 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.
- Enfoque de abajo hacia arriba: Este enfoque utiliza la mesa técnica para implementar la solución de programación dinámica. Resuelve 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.
Cómo se utiliza la técnica de memorización en la programación dinámica
¿En qué se diferencia la memorización de la tabulación?
Tabulación versus memorización
Para obtener más información, consulte Tabulación frente a memorización.
Problemas con la codificación al memorizar
| Pedir | Artículo | ejercicio | Video |
|---|---|---|---|
| Cuenta las formas de llegar a la novena escalera. | Visión | Resolver | Reloj |
| Problema de ruptura de palabras | DP-32 | Visión | Resolver | Reloj |
| Programa de números de Fibonacci | Visión | Resolver | Reloj |
| enésima canción catalana | Visión | Resolver | Reloj |
| problema de la mina de oro | Visión | Resolver | Reloj |
| Problema de suma de subconjuntos | Visión | Resolver | Reloj |
| cortando una varilla | Visión | Resolver | Reloj |
| Ruta de costo mínimo | Visión | Resolver | Reloj |
| Número mínimo de saltos para llegar al final | Visión | Resolver | Reloj |
| Subcadena palindrómica más larga | Serie 1 . en | Visión | Resolver | Reloj |
| Secuencia repetitiva más larga | Visión | Resolver | Reloj |
| Cuente las formas de llegar a la enésima escalera con el paso 1, 2 o 3 | Visión | Resolver | Reloj |
| Número de formas diferentes de expresar N como la suma de 1, 3 y 4 | Visión | Resolver | Reloj |
| Contar el número de maneras de cubrir una distancia | Visión | Resolver | Reloj |
| Número de arreglos con elementos consecutivos con diferentes valores | Visión | Resolver | Reloj |
| Subarreglo contiguo de suma más grande | Visión | Resolver | Reloj |
| Subarreglo contiguo de suma más pequeña | Visión | Resolver | Reloj |
| Caminos únicos en una cuadrícula de obstáculos. | Visión | Resolver | Reloj |
| Diferentes formas de sumar n con números mayores o iguales a m | Visión | Resolver | Reloj |
Preguntas frecuentes (FAQ) sobre la memorización
1: ¿El almacenamiento en memoria es mejor que DP?
La memorización es el enfoque de arriba hacia abajo para resolver un problema con programación dinámica. Se llama formación de memo porque crearemos un memo para los valores devueltos al resolver cada problema.
2: ¿Es lo mismo Memos que almacenamiento en caché?
Memorizar 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 el almacenamiento en caché HTTP) para referencia futura, pero memorizar se refiere más específicamente a la función de almacenamiento en caché que devuelve el valor.
3: ¿Por qué el almacenamiento de memoria es de arriba hacia abajo?
El enfoque de arriba hacia abajo divide el problema principal en varios subproblemas. si el subproblema ya se resolvió, reutilice la respuesta. De lo contrario, resuelva el subproblema y almacene el resultado en una memoria.
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 tablas o notas?
Para los problemas que requieren que se resuelvan todos los subproblemas, la tabulación generalmente supera a la memorización de factores constantes. Esto se debe a que la tabla no tiene sobrecarga de recursividad, lo que reduce el tiempo para resolver la pila de llamadas de recursividad desde la pila.
Cuando es necesario resolver un subproblema para resolver el problema original, se prefiere la memorización porque un subproblema se resuelve con pereza, es decir, solo se realizan los cálculos necesarios.
6: ¿Dónde se utiliza el almacenamiento de memoria?
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 vuelve a encontrar la misma entrada.
7: ¿Por qué se llama Memoización?
El término «memorizar» proviene de la palabra latina «memorandum» («recordar»), que en inglés americano a menudo se abrevia como «memo», que significa «convertir 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 un caché o memoria en la que almacenamos el resultado del problema ya calculado para una entrada dada. Entonces, si no queremos volver a calcular el mismo problema, podemos usar el resultado almacenado en la memoria y reducir la complejidad del tiempo.
9: ¿Cuál es la diferencia entre notas y almacenamiento en caché?
La memorización es en realidad un tipo específico de almacenamiento en caché en el que el valor de retorno de una función se almacena en caché 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 un almacén de memoria.
10: ¿Por qué la tabulación es más rápida que la formación de notas?
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 las llamadas recursivas.
Conclusión
La memorización es un concepto de programación y se puede aplicar a cualquier lenguaje de programación. El objetivo absoluto es optimizar el programa. Este problema suele ocurrir cuando los programas realizan cálculos pesados. Esta técnica almacena en caché todos los resultados anteriores que se calcularon para que no tengan que volver a calcularse para el mismo problema.
Artículos relacionados:
