En Informática, el compromiso espacio-tiempo o tiempo-memoria es una situación en la que la memoria puede reducirse a costa de la ejecución más lenta de los programas, o viceversa, el tiempo de ejecución puede reducirse a costa de incrementar el uso de memoria. En la medida en que cambian los costos relativos de los ciclos de CPU, espacio en RAM y espacio en disco duro —durante algún tiempo el espacio en disco duro se ha estado abaratando a un ritmo mucho más rápido que otros componentes de los ordenadores [cita requerida]— la elección apropiada en soluciones de compromiso espacio-tiempo ha cambiado radicalmente. A menudo, aprovechando una situación de compromiso tiempo-memoria, la clase de complejidad de un problema puede cambiar por completo.
La situación más común es un algoritmo que utiliza una tabla de búsqueda: una implementación puede incluir la tabla al completo, lo que reduce el tiempo de ejecución, pero incrementa la cantidad de memoria necesitada, o puede calcular entradas de la tabla a medida que se necesiten, incrementando el tiempo de ejecución, pero reduciendo los requisitos de memoria.
El compromiso espacio-tiempo se puede aplicar al simple problema de almacenamiento de datos. Si los datos se almacenan de forma no comprimida se necesita más espacio pero menos tiempo que si los datos se almacenan de forma comprimida (ya que la compresión reduce la cantidad de espacio utilizado, pero utiliza tiempo de ejecución para procesar el algoritmo de compresión). Dependiendo del caso concreto de problema será o no práctico.
Otro ejemplo es la presentación de fórmulas matemáticas en sitios Web basados principalmente en texto, como la Wikipedia. Almacenar únicamente el código fuente LaTeX y transformarlo a una imagen cada vez que se solicita la página sería una solución de compromiso de tiempo frente a memoria —se utiliza más tiempo pero menos memoria. Transformar la imagen cuando se guarda la página de manera que queden almacenadas sería una solución de compromiso de memoria frente al tiempo - se utiliza más memoria pero menos tiempo.
Entre los algoritmos que usan soluciones de compromiso espacio-tiempo para conseguir mejores tiempos de ejecución se incluye el algoritmo de paso-de-niño paso-de-gigante para calcular logaritmos discretos.
Making a Faster Cryptanalytic Time-Memory Trade-Off - Philippe Oechslin (en inglés)
Once Upon a Time-Memory Tradeoff (en inglés)
(en inglés)
A cryptanalytic time-memory trade-off - Martin Hellman (en inglés)
Les compromis temps-mémoire et leur utilisation pour casser les mots de passe Windows - Philippe Oechlin (conférence SSTIC 2004) (en francés)
Datos:Q283310
Mayo 24, 2022
situación, compromiso, espacio, tiempo, informática, compromiso, espacio, tiempo, tiempo, memoria, situación, memoria, puede, reducirse, costa, ejecución, más, lenta, programas, viceversa, tiempo, ejecución, puede, reducirse, costa, incrementar, memoria, medid. En Informatica el compromiso espacio tiempo o tiempo memoria es una situacion en la que la memoria puede reducirse a costa de la ejecucion mas lenta de los programas o viceversa el tiempo de ejecucion puede reducirse a costa de incrementar el uso de memoria En la medida en que cambian los costos relativos de los ciclos de CPU espacio en RAM y espacio en disco duro durante algun tiempo el espacio en disco duro se ha estado abaratando a un ritmo mucho mas rapido que otros componentes de los ordenadores cita requerida la eleccion apropiada en soluciones de compromiso espacio tiempo ha cambiado radicalmente A menudo aprovechando una situacion de compromiso tiempo memoria la clase de complejidad de un problema puede cambiar por completo La situacion mas comun es un algoritmo que utiliza una tabla de busqueda una implementacion puede incluir la tabla al completo lo que reduce el tiempo de ejecucion pero incrementa la cantidad de memoria necesitada o puede calcular entradas de la tabla a medida que se necesiten incrementando el tiempo de ejecucion pero reduciendo los requisitos de memoria El compromiso espacio tiempo se puede aplicar al simple problema de almacenamiento de datos Si los datos se almacenan de forma no comprimida se necesita mas espacio pero menos tiempo que si los datos se almacenan de forma comprimida ya que la compresion reduce la cantidad de espacio utilizado pero utiliza tiempo de ejecucion para procesar el algoritmo de compresion Dependiendo del caso concreto de problema sera o no practico Otro ejemplo es la presentacion de formulas matematicas en sitios Web basados principalmente en texto como la Wikipedia Almacenar unicamente el codigo fuente LaTeX y transformarlo a una imagen cada vez que se solicita la pagina seria una solucion de compromiso de tiempo frente a memoria se utiliza mas tiempo pero menos memoria Transformar la imagen cuando se guarda la pagina de manera que queden almacenadas seria una solucion de compromiso de memoria frente al tiempo se utiliza mas memoria pero menos tiempo Entre los algoritmos que usan soluciones de compromiso espacio tiempo para conseguir mejores tiempos de ejecucion se incluye el algoritmo de paso de nino paso de gigante para calcular logaritmos discretos En otras areas el compromiso espacio tiempo puede darse cuando se llevan a cabo ataques de fuerza bruta contra criptosistemas mediante la creacion de tablas arcoiris El ataque Meet in the middle es una aplicacion de situaciones de compromiso espacio tiempo Enlaces externos EditarMaking a Faster Cryptanalytic Time Memory Trade Off Philippe Oechslin en ingles Once Upon a Time Memory Tradeoff en ingles Password Cracking and Time Memory Trade Off en ingles A cryptanalytic time memory trade off Martin Hellman en ingles Les compromis temps memoire et leur utilisation pour casser les mots de passe Windows Philippe Oechlin conference SSTIC 2004 en frances Datos Q283310 Obtenido de https es wikipedia org w index php title Situacion de compromiso espacio tiempo amp oldid 117316547, wikipedia, wiki, leyendo, leer, libro, biblioteca,
