A space–time or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc), and time refers to the time consumed in performing a given task (computation time or response time). The utility of a given space–time tradeoff is affected by related fixed and variable costs (of, e.g., CPU speed, storage space), and is subject to diminishing returns.

Property Value
dbo:abstract
  • In der Informatik ist ein Time-Memory Tradeoff (TMTO, deutsch Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleich) ein Kompromiss, bei dem der Speicherbedarf eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarf verkürzt wird. Ziel dabei ist es, das Programm unter aktuellen technischen Voraussetzungen möglichst effizient umzusetzen. Der Begriff wird nicht nur für den entstehenden Kompromiss und für den Vorgang des Abwägens, sondern auch zur Benennung von Problemenklassen, die eine solche Abwägung nahelegen, verwendet. Darüber hinaus werden manche Programme und Algorithmen, die von diesem Vorgehen entscheidend geprägt wurden, mit diesem Wort bezeichnet. (de)
  • A space–time or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc), and time refers to the time consumed in performing a given task (computation time or response time). The utility of a given space–time tradeoff is affected by related fixed and variable costs (of, e.g., CPU speed, storage space), and is subject to diminishing returns. (en)
  • Les compromis temps-mémoire sont utilisés en cryptanalyse pour récupérer des clés à partir de leur trace chiffrée, en s'appuyant sur des tables précalculées. Cette méthode a été formalisée par Martin Hellman dans son article « A cryptanalytic time-memory trade-off » publié en 1980. Comme son nom le suggère, cette méthode probabiliste se trouve à mi-chemin entre : * une recherche exhaustive à la demande (demandant un temps excessif) ; * et un stockage complet préalable de toutes les solutions possibles en mémoire par un annuaire inverse (demandant une capacité de stockage irréaliste). La méthode utilise des tables précalculées (souvent plusieurs jours de calcul) pour accélérer considérablement un cassage de clé « à la demande » en fonction des caractéristiques de la clé brouillée. (fr)
  • 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 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. (es)
  • In informatica il compromesso tempo-memoria (o compromesso spazio-tempo) è una situazione dove l'utilizzo della memoria può essere ridotto al prezzo di un rallentamento della velocità di esecuzione del programma o, viceversa, il tempo di calcolo può essere ridotto al prezzo di un incremento dell'utilizzo della memoria. Al variare dei relativi costi di cicli di CPU, spazio RAM e spazio su disco rigido possono cambiare radicalmente le scelte per i compromessi tempo-memoria. Spesso, approntare un compromesso tempo-memoria può portare un programma ad essere eseguito molto più velocemente. (it)
  • 計算機科学における時間と空間のトレードオフ(じかんとくうかんのトレードオフ、space-time tradeoff)または時間と記憶域のトレードオフ(じかんときおくいきのトレードオフ、time-memory tradeoff、タイム・メモリ・トレードオフ)とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。 時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。 時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。 時間と空間のトレードオフは、データストレージにも当てはまる。データを圧縮せずに保存すると、圧縮した場合と比べ、消費する容量は多く、必要な時間は短くなる。データの圧縮によって保存に必要な領域を減らすことができるが、データ圧縮処理を行う時間が必要になる。どちらが適切かは場合によって異なる。 もう一つの例として、数式をウィキペディアで表示する方法が挙げられる。LaTeXのソースだけを保存しておき、ページを表示する度にそれをレンダリングする方法をとれば、時間はかかるが、記憶装置の使用量は少なくて済み、空間を時間でまかなうことができる。ページが保存されたときに画像をレンダリングし、それを保存しておく方法をとれば、記憶装置の使用量は多くなるが、時間は短くて済み、時間を空間でまかなうことができる。 時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるbaby-step giant-stepアルゴリズムがある。 他の分野では、暗号システムに対する総当たり攻撃におけるレインボーテーブルの作成が、時間と空間のトレードオフにあたる。中間一致攻撃も時間と空間のトレードオフの応用である。 (ja)
  • Em ciência da computação, especificamente em informática teórica, se estuda o quanto de espaço em memória e tempo determinados algoritmos utilizam. Para fins didáticos e teóricos, muitos problemas são considerados solúveis, mas na prática tomariam bastante tempo para serem solucionados. Utiliza-se análise assintótica, que "estipula" o quão rápido a quantidade de uso daquele recurso (tempo ou espaço, no contexto de computação) cresce em proporção ao crescimento do tamanho da entrada, para, dessa forma, comparar as soluções de um dado problema pelo potencial de complexidade, e não apenas casos isolados do uso destas soluções. O problema é que, na teoria, as máquinas de Turing têm memória infinita, e consideramos que alguns processos genéricos são rápidos se durassem até um polinômio no tamanho da entrada, mas polinômio podem representar quantidades realmente grandes, e nossos recursos de memória em computadores são finitos. Daí a importância de se dosar a relação "espaço-tempo" de forma a se ter um trade-off entre essas duas grandezas e otimizar execução e resultado. * Espaço se refere ao armazenamento de dados consumido na execução de um dado algoritmo, seja no armazenamento primário (e.g., na memória RAM) ou no armazenamento secundário (e.g., em um disco rígido). Em informática teórica, isto é analisado pelo ponto de visto de consumo (escrita, e não leitura) das células na(s) fita(s) de uma máquina de Turing. Um exemplo de conceito proveniente deste estudo é a definição de PSPACE. * Tempo se refere à quantidade de passos ao executar um algoritmo, tema estudado em complexidade de tempo. Esta análise se dá na observação do aumento do tempo para execução de um algoritmo de acordo com o tamanho da sua entrada, i.e., quanto maior sua entrada como se comporta em função do tempo o algoritmo. Tanto na análise de complexidade de tempo e espaço existem métricas para se estudar varios casos. Essas métricas se dão pelo uso de notações como Grande-O e Complexidade do caso médio. Trade-off espaço-tempo é um caso onde um algoritmo ou software compensa o aumento no consumo de memória levando menos tempo. A utilidade de um balanço entre espaço e tempo é afetado por custos fixos e variáveis, como velocidade da unidade de processamento, espaço na memória primária e secundária. Numa analogia, é sujeito a Lei dos rendimentos decrescentes (em inglês, diminishing returns). (pt)
  • Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения объёма используемой памяти. Благодаря уменьшению относительных расходов на объём ОЗУ (RAM) и памяти на жёстком диске (в течение некоторого периода времени стоимость места на жёстком диске дешевела значительно быстрее, чем стоимость других компонент ЭВМ), постепенное распространение получали приёмы, использующие доступную память для уменьшения времени вычислений. В то же время, такие приёмы, как сжатие данных, демонстрируют альтернативный подход — экономное использование памяти за счёт дополнительных преобразований данных из одного формата в другой. (ru)
  • Просторово-часова домовленість (англ. space–time, time–memory tradeoff, TMTO) — ситуація в інформатиці, коли можна зменшити використання пам'яті ціною вповільнення швидкості виконання програми (і, навпаки, можна зменшити за рахунок використання більшого об'єму пам'яті). (uk)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 773481 (xsd:integer)
dbo:wikiPageLength
  • 4825 (xsd:integer)
dbo:wikiPageRevisionID
  • 960226605 (xsd:integer)
dbo:wikiPageWikiLink
dbp:date
  • March 2014 (en)
dbp:reason
  • casual tone, lack of detail (en)
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
  • A space–time or time–memory trade-off in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc), and time refers to the time consumed in performing a given task (computation time or response time). The utility of a given space–time tradeoff is affected by related fixed and variable costs (of, e.g., CPU speed, storage space), and is subject to diminishing returns. (en)
  • In informatica il compromesso tempo-memoria (o compromesso spazio-tempo) è una situazione dove l'utilizzo della memoria può essere ridotto al prezzo di un rallentamento della velocità di esecuzione del programma o, viceversa, il tempo di calcolo può essere ridotto al prezzo di un incremento dell'utilizzo della memoria. Al variare dei relativi costi di cicli di CPU, spazio RAM e spazio su disco rigido possono cambiare radicalmente le scelte per i compromessi tempo-memoria. Spesso, approntare un compromesso tempo-memoria può portare un programma ad essere eseguito molto più velocemente. (it)
  • Просторово-часова домовленість (англ. space–time, time–memory tradeoff, TMTO) — ситуація в інформатиці, коли можна зменшити використання пам'яті ціною вповільнення швидкості виконання програми (і, навпаки, можна зменшити за рахунок використання більшого об'єму пам'яті). (uk)
  • In der Informatik ist ein Time-Memory Tradeoff (TMTO, deutsch Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleich) ein Kompromiss, bei dem der Speicherbedarf eines Programmes auf Kosten einer längeren Laufzeit gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarf verkürzt wird. Ziel dabei ist es, das Programm unter aktuellen technischen Voraussetzungen möglichst effizient umzusetzen. (de)
  • 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. (es)
  • Les compromis temps-mémoire sont utilisés en cryptanalyse pour récupérer des clés à partir de leur trace chiffrée, en s'appuyant sur des tables précalculées. Cette méthode a été formalisée par Martin Hellman dans son article « A cryptanalytic time-memory trade-off » publié en 1980. Comme son nom le suggère, cette méthode probabiliste se trouve à mi-chemin entre : * une recherche exhaustive à la demande (demandant un temps excessif) ; * et un stockage complet préalable de toutes les solutions possibles en mémoire par un annuaire inverse (demandant une capacité de stockage irréaliste). (fr)
  • 計算機科学における時間と空間のトレードオフ(じかんとくうかんのトレードオフ、space-time tradeoff)または時間と記憶域のトレードオフ(じかんときおくいきのトレードオフ、time-memory tradeoff、タイム・メモリ・トレードオフ)とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。 時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。 時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。 時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるbaby-step giant-stepアルゴリズムがある。 (ja)
  • Em ciência da computação, especificamente em informática teórica, se estuda o quanto de espaço em memória e tempo determinados algoritmos utilizam. Para fins didáticos e teóricos, muitos problemas são considerados solúveis, mas na prática tomariam bastante tempo para serem solucionados. Utiliza-se análise assintótica, que "estipula" o quão rápido a quantidade de uso daquele recurso (tempo ou espaço, no contexto de computação) cresce em proporção ao crescimento do tamanho da entrada, para, dessa forma, comparar as soluções de um dado problema pelo potencial de complexidade, e não apenas casos isolados do uso destas soluções. O problema é que, na teoria, as máquinas de Turing têm memória infinita, e consideramos que alguns processos genéricos são rápidos se durassem até um polinômio no taman (pt)
  • Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения объёма используемой памяти. (ru)
rdfs:label
  • Time-Memory Tradeoff (de)
  • Situación de compromiso espacio-tiempo (es)
  • Space–time tradeoff (en)
  • Compromis temps-mémoire (fr)
  • Compromesso tempo-memoria (it)
  • 時間と空間のトレードオフ (ja)
  • Trade-off Espaço-Tempo (pt)
  • Компромисс времени и памяти (ru)
  • Просторово-часова домовленість (uk)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of