Abhängigkeit zwischen Rechenzeit und Speicherbedarf in einen Algorithmus

[John17.54]

Hallo zusammen,

ich möchte gerne wissen in wie weit der Speicherbedarf von der Rechenzeit abhängig ist und wie er variiert? Dazu gerne Beispiele mit Java.

 

[Joose]

Warum glaubst du dass hier eine Abhängigkeit besteht?
Was für Beispiele erwartest du dir?

 

[John17.54]

Eventuell, dass ein Algorithmus, der schnell durchgeführt wird, mehr Speicher verbraucht, als ein Algorithmus, der den selben Endzustand erreicht mit einer längeren Rechenlaufzeit, jedoch weniger Speicher dabei verbraucht.

 

[Joose]

Du musst bei der Laufzeit aufpassen und unterscheiden:

Wenn es um reine Prozessorlaufzeit geht, dann hat der Speicher (wenn überhaupt) wenig Einfluss auf die Dauer. Hier kommt es dann darauf an wie effizient der Algorithmus entworfen/programmiert wurde.

Wenn es um die Programmlaufzeit geht, dann hat mehr Speicher sicher seine Vorteile. Man kann dann eben alle möglichen Daten im Speicher behalten und muss diese nicht immer wieder in ein File (oder eine DB) speichern und wieder einlesen.

 

[Neumi5694]

Dafür gibt es pauschal keine Antwort, das hängt ganz vom Algorithmus ab.
Du kannst einen Algorithmus auch langsamer machen, wenn du viel Speicher verbrauchst, z.B. für jede Operation jeweils einen Klon der Operanden erstellst. Das braucht Zeit und vervielfacht den verwendeten Speicher.

 

[John17.54]

Danke Joose und Neumi5694, dass mit dem Einlesen und den Klonen bringt mich in meinen Überlegungen weiter

 

[stg]

Der Kerngedanke bei der Fragestellung ist ein anderer (und einfacherer):
Wir gehen davon aus, dass alle benötigten Eingabedaten im Speicher sind.
Zwischenergebnisse deines Algorithmus, die später erneut benötigt werden, kannst du
- entweder zwischenspeichern -> Du benötigst zur Laufzeit mehr Speicherplatz
- oder neu berechnen -> Du benötigst mehr Rechenzeit.

 

[Neumi5694]

Für einen aufwendigen Algorithmus cache so viel wie möglich, Speicher ist vergleichsweise billig. Für eine UI und Textausgaben ist das weniger tragisch, da kannst du gerne auch jedesmal bei Anzeige die Texte neu zusammenstellen.