Situación de compromiso espacio-tiempo

Situación de compromiso espacio-tiempo

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.

En otras áreas, el compromiso espacio-tiempo puede darse cuando se llevan a cabo ataques de fuerza bruta contra criptosistemas mediante la creación de tablas arcoiris. El ataque Meet-in-the-middle es una aplicación de situaciones de compromiso espacio-tiempo.

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Espacio — Saltar a navegación, búsqueda Espacio (del latín spatium) se refiere: Especialmente al espacio físico, en el que se ubican los objetos sensibles; y la extensión que contiene toda la materia existente; la distancia entre dos cuerpos; la distancia… …   Wikipedia Español

  • Ataque de cumpleaños — Saltar a navegación, búsqueda Un ataque de cumpleaños (o, en inglés, birthday attack) es un tipo de ataque criptográfico que se basa en la matemática detrás de la paradoja del cumpleaños, haciendo uso de una situación de compromiso espacio tiempo …   Wikipedia Español

  • Historia del Partido Nacionalista Vasco — Artículo principal: Partido Nacionalista Vasco El Partido Nacionalista Vasco, fundado por Sabino Arana, fue constituido oficialmente el 31 de julio de 1895. Desde la instauración de la democracia hasta mayo de 2009 formó parte del Gobierno Vasco …   Wikipedia Español

  • Fernando IV de Castilla y León — Saltar a navegación, búsqueda Fernando IV de Castilla y León Rey de Castilla y León Reinado …   Wikipedia Español

  • Historia del cristianismo en España — Cristo crucificado, de Velázquez. El cristianismo en España tiene una larga historia: casi dos mil años, según la leyenda que remonta sus orígene …   Wikipedia Español

  • Wikipedia:Tablón de anuncios de los bibliotecarios/Portal/Archivo/3RR/Actual — Alertas sobre guerras de ediciones Esta sección del tablón de anuncios de los bibliotecarios sirve para alertar sobre guerras de ediciones en curso. Antes de alertar sobre una guerra de ediciones, debes tener en cuenta qué es una guerra de… …   Wikipedia Español

  • Expresionismo — Saltar a navegación, búsqueda …   Wikipedia Español

  • Historia contemporánea de España — La promulgación de la Constitución de 1812, obra de Salvador Viniegra (Museo de las Cortes de Cádiz). Historia contemporánea de España es la disciplina historiográfica y el periodo histórico de la historia de España que corresponde a la Edad… …   Wikipedia Español

  • BDSM — Saltar a navegación, búsqueda Para el término BDSM referente a quemaduras, véase Branding (quemadura) …   Wikipedia Español

  • Madrid de los Austrias — Cubiertas de la Casa de la Villa en la Calle Mayor de Madrid …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”