Time-Memory Tradeoff

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Beispiele für Kompromissformen[Bearbeiten]

Bei der Verwendung von Lookup-Tabellen kann in der Implementierung die gesamte Tabelle vorberechnet werden, wodurch die Laufzeit verringert, aber den Speicherbedarf erhöht wird.
  • Komprimierte Daten gegenüber unkomprimierten Daten
Ein Ausgleich zwischen Speicher und Laufzeit erfolgt bei der Datenkompression, wobei der Speicherbedarf von Daten verringert wird, aber mehr Zeit zum Dekomprimieren benötigt wird.
Werden auf einem Server (beispielsweise der Wikipedia) LaTeX-Formeln als Quelltext und nicht als Bilddatei gespeichert, so wird der Speicherbedarf gesenkt, aber durch das wiederholte Rendern die Laufzeit erhöht.
Durch Auflösen von Schleifen kann die Laufzeit verkürzt werden, während sich der Programmcode vergrößert.

Beispiele für Algorithmen[Bearbeiten]

Bei den Rainbow-Tabellen hat die konsequente Anwendung dieses Prinzips zu einer kompletten Zweiteilung der Lösung geführt. In einem völlig eigenständigen Vorbereitungsprogramm werden mit ganz erheblichem Rechenaufwand große Tabellen vorbereitet. Andere Programme nutzen die vorbereiteten Tabellen, um damit in relativ geringer Zeit Verschlüsselungen oder Passwörter zu brechen.

Weblinks[Bearbeiten]