Una compensación espacio-tiempo o tiempo-memoria en la informática es un caso en el que un algoritmo o programa intercambia un mayor uso del 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 en la realización de 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 .
Historia
El uso biológico de las compensaciones entre el tiempo y la memoria se puede ver en las primeras etapas del comportamiento animal . El uso del conocimiento almacenado o la codificación de reacciones de estímulos como "instintos" en el ADN evita la necesidad de "cálculos" en situaciones de tiempo crítico. Más específicas para las computadoras, las tablas de búsqueda se han implementado desde los primeros sistemas operativos. [ cita requerida ]
En 1980, Martin Hellman propuso por primera vez el uso de una compensación tiempo-memoria para el criptoanálisis . [1]
Tipos de compensación
Tablas de búsqueda frente a recálculo
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 las entradas de la tabla según sea necesario, aumentando el tiempo de cálculo, pero reduciendo los requisitos de memoria.
Datos comprimidos frente a datos sin comprimir
Se puede aplicar una compensación de espacio-tiempo al problema del almacenamiento de datos. Si los datos se almacenan sin comprimir, ocupa más espacio, pero el acceso toma menos tiempo que si los datos se almacenan comprimidos (ya que la compresión de los datos reduce la cantidad de espacio que ocupa, pero la ejecución del algoritmo de descompresión lleva tiempo ). Dependiendo de la instancia 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 mapa de bits comprimidos , donde es más rápido trabajar con compresión que sin compresión.
Reproducción frente a imágenes almacenadas
Almacenar solo 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 cambiar tiempo por espacio; más tiempo utilizado, pero menos espacio. Renderizar la imagen cuando se cambia la página y almacenar las imágenes renderizadas sería intercambiar espacio por tiempo; más espacio utilizado, pero menos tiempo. Esta técnica se conoce más generalmente como almacenamiento en caché .
Código más pequeño frente a desenrollado de bucle
Se puede intercambiar un tamaño de código más grande por una mayor velocidad de programa al aplicar el desenrollado de 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.
Otros ejemplos
Los algoritmos que también hacen uso de compensaciones entre el espacio y el tiempo incluyen:
- Algoritmo de pasos gigantes para calcular logaritmos discretos
- Tablas de arco iris en criptografía, donde el adversario está tratando de hacerlo mejor que el tiempo exponencial requerido para un ataque de fuerza bruta . Las tablas Rainbow utilizan valores parcialmente calculados previamente 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 del arco iris aumenta el tiempo necesario para iterar sobre el espacio hash.
- El ataque de encuentro en el medio utiliza una compensación de espacio-tiempo para encontrar la clave criptográfica en solo cifrados (y espacio) versus lo esperado cifrados (pero solo espacio) del ataque ingenuo.
- Programación dinámica , donde la complejidad temporal de un problema se puede reducir significativamente utilizando más memoria.
Ver también
Referencias
- ^ Hellman, Martin (julio de 1980). "Un intercambio criptoanalítico de tiempo-memoria". Transacciones IEEE sobre teoría de la información . 26 (4): 401–406. CiteSeerX 10.1.1.120.2463 . doi : 10.1109 / tit.1980.1056220 .