Un equilibrio espacio-tiempo , también conocido como equilibrio tiempo-memoria o continuo espacio-tiempo algorítmico en informática, es un caso en el que un algoritmo o programa intercambia un mayor uso de espacio por 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 un determinado equilibrio espacio-tiempo se ve afectada por los costos fijos y variables relacionados (por ejemplo, velocidad de la CPU , espacio de almacenamiento) y está sujeta a rendimientos decrecientes .
El uso biológico de los equilibrios 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 a estímulos como "instintos" en el ADN evita la necesidad de "cálculos" en situaciones críticas en el tiempo. Más específicamente en el caso de las computadoras, las tablas de consulta se han implementado desde los primeros sistemas operativos. [ cita requerida ]
En 1980, Martin Hellman propuso por primera vez el uso de un equilibrio entre tiempo y 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 cálculo, pero aumenta la cantidad de memoria necesaria, o puede calcular entradas de la tabla según sea necesario, aumentando el tiempo de cálculo, pero reduciendo los requisitos de memoria.
Los sistemas de gestión de bases de datos ofrecen la posibilidad de crear estructuras de datos de índices 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 un equilibrio espacio-tiempo 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 al comprimir los datos se reduce la cantidad de espacio que ocupan, pero lleva tiempo ejecutar el algoritmo de descompresión ). Dependiendo de la instancia particular del problema, cualquiera de las dos opciones es práctica. También hay casos raros en los que es posible trabajar directamente con datos comprimidos, como en el caso de los índices de mapa de bits comprimidos , donde es más rápido trabajar con compresión que sin compresión.
Almacenar solo la fuente SVG de una imagen vectorial y renderizarla como una imagen de mapa de bits cada vez que se solicita la página sería intercambiar tiempo por espacio; se utilizaría 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 utilizaría más espacio, pero menos tiempo. Esta técnica se conoce más generalmente como almacenamiento en caché .
Se puede cambiar un código de mayor tamaño por una mayor velocidad del programa al aplicar el desenrollado de bucle . Esta técnica hace que el código sea más largo en 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 hacen uso de compensaciones espacio-tiempo incluyen:
