Du weißt bereits, dass Algorithmen unterschiedlich viel Zeit benötigen. Aber Algorithmen belegen auch unterschiedlich viel Arbeitsspeicher (RAM). Die Speicherkomplexität (englisch: space complexity) beschreibt, wie der Speicherbedarf eines Algorithmus mit der Eingabegröße wächst.
Warum ist Speicherkomplexität wichtig?
- Mobilgeräte und eingebettete Systeme haben begrenzten Speicher
- Bei sehr großen Datensätzen kann der Speicher zum Engpass werden
- Manche Algorithmen tauschen Zeit gegen Speicher — und umgekehrt
- Ein schneller Algorithmus mit riesigem Speicherbedarf kann auf manchen Geräten nicht laufen
Die Big-O-Notation für Speicher
Die gleiche Big-O-Notation, die wir für Zeitkomplexität verwenden, beschreibt auch den Speicherbedarf. Dabei betrachten wir meist den zusätzlichen Speicher, den der Algorithmus über die Eingabedaten hinaus benötigt.
O(1) — Konstanter Zusatzspeicher
Der Algorithmus benötigt immer gleich viel Speicher, unabhängig von n:
def maximum_in_place(liste):
max_wert = liste[0] # eine einzelne Variable
for element in liste:
if element > max_wert:
max_wert = element
return max_wert
Egal ob die Liste 10 oder 10.000 Elemente hat — wir brauchen nur eine einzige Hilfsvariable max_wert. Das ist O(1) Zusatzspeicher.
O(1) Speicher bedeutet, dass der Algorithmus "in place" (am Ort) arbeitet — er verändert die Eingabe direkt oder verwendet nur eine konstante Anzahl zusätzlicher Variablen. Das ist ideal für speicherbeschränkte Umgebungen.
O(n) — Linearer Speicher
Der Speicherbedarf wächst proportional zur Eingabegröße:
def liste_kopieren(original):
kopie = [] # neue Liste wächst mit n
for element in original:
kopie.append(element)
return kopie
Für eine Liste mit n Elementen erstellen wir eine neue Liste mit ebenfalls n Elementen → O(n) Zusatzspeicher.
def alle_quadrate(liste):
return [x * x for x in liste] # neue Liste mit n Elementen: O(n)
O(n²) — Quadratischer Speicher
Der Speicherbedarf wächst quadratisch — typisch für zweidimensionale Strukturen:
def erstelle_tabelle(n):
tabelle = []
for i in range(n):
zeile = [0] * n # n Elemente pro Zeile
tabelle.append(zeile)
return tabelle # n × n = n² Elemente insgesamt
Manchmal kann man Speicher gegen Zeit eintauschen. Eine Funktion, die Ergebnisse in einer Tabelle speichert (sog. Memoization), ist schneller, braucht aber mehr Speicher. Die Wahl hängt von den verfügbaren Ressourcen ab.
Sortieralgorithmen im Vergleich
Ein praktischer Vergleich zeigt, wie Algorithmen Zeit und Speicher abwägen:
| Algorithmus | Zeitkomplexität | Speicherkomplexität | Anmerkung |
|---|---|---|---|
| Bubble-Sort | O(n²) | O(1) | Sortiert in place |
| Auswahlsortierung | O(n²) | O(1) | Sortiert in place |
| Einfügesortierung | O(n²) | O(1) | Sortiert in place |
| Mergesort | O(n log n) | O(n) | Braucht Hilfsspeicher |
| Quicksort | O(n log n) | O(log n) | In place, aber rekursiv |
Bubble-Sort ist langsam (O(n²) Zeit), aber sehr sparsam mit Speicher (O(1)). Mergesort ist schneller (O(n log n)), braucht aber O(n) zusätzlichen Speicher.
Rekursive Algorithmen haben oft versteckten Speicherbedarf. Jeder Rekursionsaufruf legt einen neuen "Stapelrahmen" im Speicher an. Eine Funktion, die sich n Mal selbst aufruft, verbraucht O(n) Stackspeicher — auch wenn sie keine expliziten Hilfsdaten erstellt.
Zeit-Speicher-Kompromisse in der Praxis
# Langsam, aber speichersparsam: berechne jedes Mal neu
def ist_prim_langsam(n):
for i in range(2, n):
if n % i == 0:
return False
return True
# Schnell, aber speicherintensiv: Ergebnisse vorberechnen und speichern
prim_tabelle = {}
def ist_prim_schnell(n):
if n in prim_tabelle:
return prim_tabelle[n] # sofort aus dem Speicher holen
for i in range(2, n):
if n % i == 0:
prim_tabelle[n] = False
return False
prim_tabelle[n] = True
return True
Zusammenfassung
| Big-O Speicher | Beschreibung | Beispiel |
|---|---|---|
| O(1) | Konstant — nur wenige Variablen | Bubble-Sort, lineare Suche |
| O(log n) | Logarithmisch — kleiner Hilfsspeicher | Rekursive binäre Suche |
| O(n) | Linear — Kopie der Daten | Mergesort, Liste kopieren |
| O(n²) | Quadratisch — zweidim. Struktur | Adjazenzmatrix für Graphen |
Übungsaufgaben
Welche Speicherkomplexität hat ein Algorithmus, der eine Liste mit n Zahlen erhält und eine neue Liste erstellt, die nur die geraden Zahlen daraus enthält? Erkläre deine Antwort.
Antwort anzeigen
Ein Schüler schreibt einen Algorithmus, der für jedes Element in einer Liste eine neue Liste erstellt. Was ist die Speicherkomplexität? Warum könnte das ein Problem sein?