Compensación espacio-tiempo

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 entre espacio y 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 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:

• Algoritmo de pasos pequeños y pasos gigantes para calcular logaritmos discretos
• Tablas arcoíris en criptografía, donde el adversario intenta hacerlo mejor que el tiempo exponencial requerido para un ataque de fuerza bruta . Las tablas arcoíris utilizan valores parcialmente precalculados en el espacio hash de una función hash criptográfica para descifrar contraseñas en minutos en lugar de semanas. Disminuir el tamaño de la tabla arcoíris aumenta el tiempo necesario para iterar sobre el espacio hash.
• El ataque de encuentro en el medio utiliza un equilibrio espacio-tiempo para encontrar la clave criptográfica solo en cifrados (y espacio) versus los cifrados esperados (pero solo espacio) del ataque ingenuo.$Estilo de visualización 2^{n+1}}$${\displaystyle O(2^{n})}$$Estilo de visualización 2^{2n}}$${\estilo de visualización O(1)}$
• Programación dinámica , donde la complejidad temporal de un problema se puede reducir significativamente utilizando más memoria.
• Ataque de compensación de tiempo/memoria/datos que utiliza la compensación de espacio-tiempo con el parámetro adicional de datos.

• Eficiencia algorítmica  – Propiedad de un algoritmo
• Teorema de aceleración de Blum  : descarta la posibilidad de asignar a funciones arbitrarias su complejidad computacional
• Complejidad computacional  : cantidad de recursos necesarios para ejecutar un algoritmo
• Recurso computacional  : algo que una computadora necesita para resolver un problema, como pasos de procesamiento o memoria.
• Teorema de Savitch  : relación entre la complejidad espacial determinista y no determinista

• Philippe Oechslin: Cómo lograr un equilibrio más rápido entre memoria y tiempo en criptoanálisis.
• Érase una vez una disyuntiva entre el tiempo y la memoria.