Una compensación espacio-tiempo , también conocida como compensación tiempo-memoria o continuo algorítmico espacio-tiempo en informática , es un caso en el que un algoritmo o programa intercambia un mayor uso de espacio con una disminución del tiempo. Aquí, el espacio se refiere al almacenamiento de datos consumido al realizar una tarea determinada ( RAM , HDD , etc.), y el tiempo se refiere al tiempo consumido al realizar una tarea determinada ( tiempo de cálculo o tiempo de respuesta ).
La utilidad de una determinada compensación espacio-tiempo se ve afectada por los costos fijos y variables relacionados (de, por ejemplo, la velocidad de la CPU , el espacio de almacenamiento) y está sujeta a rendimientos decrecientes .
El uso biológico de las compensaciones entre tiempo y memoria se puede observar en las primeras etapas del comportamiento animal . El uso de conocimientos almacenados o la codificación de reacciones de estímulos como "instintos" en el ADN evita la necesidad de "cálculos" en situaciones en las que el tiempo es crítico. Más específicamente para las computadoras, las tablas de búsqueda se han implementado desde los primeros sistemas operativos. [ cita necesaria ]
En 1980 , Martin Hellman propuso por primera vez utilizar una compensación tiempo-memoria para el criptoanálisis . [1]
Una situación común es un algoritmo que involucra una tabla de búsqueda : una implementación puede incluir la tabla completa, lo que reduce el tiempo de computación, pero aumenta la cantidad de memoria necesaria, o puede calcular las entradas de la tabla según sea necesario, aumentando el tiempo de computación, pero reduciendo los requisitos de memoria.
Los sistemas de gestión de bases de datos ofrecen la capacidad de crear estructuras de datos de índice de bases de datos . Los índices mejoran la velocidad de las operaciones de búsqueda a costa de espacio adicional. Sin índices, a veces se requieren operaciones de escaneo completo de tablas que consumen mucho tiempo para localizar los datos deseados.
Se puede aplicar una compensación espacio-temporal al problema del almacenamiento de datos. Si los datos se almacenan sin comprimir, ocupan más espacio pero el acceso lleva menos tiempo que si los datos se almacenaran comprimidos (ya que comprimir los datos reduce la cantidad de espacio que ocupa, pero lleva tiempo ejecutar el algoritmo de descompresión ). Dependiendo del caso particular del problema, cualquiera de las dos formas es práctica. También hay casos raros en los que es posible trabajar directamente con datos comprimidos, como en el caso de índices de mapas de bits comprimidos , donde es más rápido trabajar con compresión que sin compresión.
Almacenar sólo la fuente SVG de una imagen vectorial y representarla como una imagen de mapa de bits cada vez que se solicita la página sería intercambiar tiempo por espacio; Se utiliza más tiempo, pero menos espacio. Renderizar la imagen cuando se cambia la página y almacenar las imágenes renderizadas sería intercambiar espacio por tiempo; Se utiliza más espacio, pero menos tiempo. Esta técnica se conoce más generalmente como almacenamiento en caché .
Se puede cambiar un tamaño de código mayor por una mayor velocidad del programa al aplicar el desenrollado del bucle . Esta técnica hace que el código sea más largo para cada iteración de un bucle, pero ahorra el tiempo de cálculo necesario para volver al principio del bucle al final de cada iteración.
Los algoritmos que también utilizan compensaciones espacio-temporales incluyen:
