Límite de memoria se refiere a una situación en la que el tiempo para completar un problema computacional determinado se decide principalmente por la cantidad de memoria necesaria para almacenar los datos de trabajo . Esto contrasta con los algoritmos que están vinculados a la computación, donde el número de pasos de computación elementales es el factor decisivo.
Los límites de memoria y computación a veces pueden intercambiarse entre sí, por ejemplo, guardando y reutilizando resultados preliminares o usando tablas de búsqueda .
Las funciones vinculadas a la memoria y las funciones de la memoria están relacionadas en el sentido de que ambas implican un amplio acceso a la memoria, pero existe una distinción entre las dos.
Las funciones de memoria utilizan una técnica de programación dinámica llamada memoización para aliviar la ineficiencia de la recursividad que podría ocurrir. Se basa en la idea simple de calcular y almacenar soluciones a subproblemas para que las soluciones puedan reutilizarse más tarde sin volver a calcular los subproblemas nuevamente. El ejemplo más conocido que aprovecha la memorización es un algoritmo que calcula los números de Fibonacci . El siguiente pseudocódigo usa recursividad y memorización, y se ejecuta en tiempo de CPU lineal :
Si bien el algoritmo solo recursivo es más simple y elegante que el algoritmo que usa recursividad y memorización, este último tiene una complejidad de tiempo significativamente menor que el primero.
El término "función vinculada a la memoria" ha surgido recientemente y se usa principalmente para describir una función que usa XOR y consiste en una serie de cálculos en los que cada cálculo depende del cálculo anterior. Mientras que las funciones de memoria han sido durante mucho tiempo un actor importante en la mejora de la complejidad del tiempo, las funciones vinculadas a la memoria han visto muchas menos aplicaciones. Recientemente [ ¿cuándo? ] , sin embargo, los científicos han propuesto un método que utiliza funciones vinculadas a la memoria como un medio para disuadir a los spammers de abusar de los recursos, lo que podría ser un gran avance en esa área.