O-Notation: Zeitkomplexität
In den vorigen Lektionen haben wir bei Such- und Sortier-Algorithmen immer wieder Begriffe gehört wie „O(n)", „O(log n)" und „O(n²)". Höchste Zeit, diese Notation gründlich zu verstehen. Sie ist das wichtigste Werkzeug der Informatik, um Laufzeit-Effizienz von Algorithmen zu beschreiben.
Die O-Notation (auch Landau-Notation oder Big-O genannt) beantwortet die zentrale Frage: Wie wächst der Aufwand eines Algorithmus, wenn die Eingabe wächst? Sie ist abstrakt genug, um über verschiedene Computer hinweg gleich zu sein – konkret genug, um Algorithmen zuverlässig zu vergleichen.
1) Warum O-Notation und nicht einfach Sekunden?
Naiv könnte man fragen: warum messen wir nicht einfach, wie lange ein Algorithmus läuft? Antwort: weil das von zu vielen Faktoren abhängt – Hardware, Programmiersprache, Compiler, andere laufende Programme, sogar Zufall. Ein Algorithmus, der auf deinem Laptop 2 Sekunden braucht, kann auf einem Server 0,5 Sekunden brauchen.
Was sich nicht ändert: das Wachstumsverhalten. Wenn du die Eingabe verdoppelst, wie ändert sich der Aufwand? Verdoppelt er sich auch? Vervierfacht? Bleibt er gleich? Das ist eine Eigenschaft des Algorithmus selbst – unabhängig von Hardware. Diese Eigenschaft beschreibt die O-Notation.
Ein bisschen wie Auto-Verbrauch: „mein Auto verbraucht 6 l auf 100 km" ist eine Eigenschaft des Autos, unabhängig davon, ob du gerade in Hamburg oder München fährst. Genauso ist „Bubble Sort ist O(n²)" eine Eigenschaft des Algorithmus, unabhängig vom konkreten Computer.
2) Die Idee: nur das Wachstum zählt
Die O-Notation interessiert sich nicht für genaue Schritt-Anzahlen, sondern nur für das asymptotische Verhalten – das Verhalten bei großen Eingaben. Konstanten und niedrigere Terme werden weggelassen. Beispiel: ein Algorithmus, der 3n² + 5n + 100 Schritte braucht, ist in O-Notation einfach O(n²).
Warum diese Vereinfachung? Bei großen n dominiert der höchste Term alles andere. Beispiel mit n = 1 Million: 3n² = 3 Billionen, 5n = 5 Millionen, + 100. Die niedrigeren Terme sind praktisch unsichtbar. Nur das n² spielt eine Rolle. Auch der Faktor 3 ist nur eine Konstante – verdreifacht zwar den Aufwand, ändert aber nicht das Wachstumsverhalten.
3) Die wichtigsten Komplexitätsklassen
Es gibt unendlich viele mögliche Wachstumsraten, aber in der Praxis sieht man immer wieder dieselben sechs oder sieben Klassen. Diese musst du kennen – von schnellster bis langsamster Wachstumsrate:
4) Das Wachstum visuell
Zahlen alleine sind abstrakt. Schau dir die Wachstumskurven der wichtigsten Klassen im direkten Vergleich an. Die Y-Achse ist logarithmisch skaliert – sonst würden die schnell wachsenden Funktionen alle anderen optisch zermalmen:
5) Konkrete Laufzeiten
Die abstrakten Wachstumsraten werden greifbarer, wenn man sie in konkrete Laufzeiten übersetzt. Angenommen, ein Schritt dauert 1 Nanosekunde (10⁻⁹ Sekunden – typisch für moderne CPUs):
| Klasse | n = 10 | n = 100 | n = 1 000 | n = 1 Mio | n = 1 Mrd |
|---|---|---|---|---|---|
| O(1) | 1 ns | 1 ns | 1 ns | 1 ns | 1 ns |
| O(log n) | 3 ns | 7 ns | 10 ns | 20 ns | 30 ns |
| O(n) | 10 ns | 100 ns | 1 µs | 1 ms | 1 s |
| O(n log n) | 33 ns | 700 ns | 10 µs | 20 ms | 30 s |
| O(n²) | 100 ns | 10 µs | 1 ms | 16 Min | 31 Jahre |
| O(2ⁿ) | 1 µs | 10²² Jahre | ∞ | ∞ | ∞ |
| O(n!) | 3,6 ms | ∞ | ∞ | ∞ | ∞ |
6) Komplexität analysieren – wie macht man das?
Wie ermittelt man die Komplexität eines konkreten Algorithmus? Die Grundregel: zähle, wie oft die innerste Operation ausgeführt wird, in Abhängigkeit von der Eingabegröße n. Schauen wir uns konkrete Beispiele an:
7) Regeln für die Komplexitätsanalyse
Mit diesen vier Regeln kannst du fast jede Algorithmen-Komplexität ableiten:
O(5n) = O(n). Konstante Faktoren verändern das Wachstumsverhalten nicht – nur die Steigung. In O-Notation egal.O(n² + n) = O(n²). Bei großen n dominiert immer der höchste Term. Niedrigere Anteile fallen weg.O(n) + O(n²) = O(n²). Der größere gewinnt.O(n) · O(log n) = O(n log n).log₂(n) = log₁₀(n) / log₁₀(2)). Also: O(log n) umfasst alle Basen.8) Best / Average / Worst Case
Bei vielen Algorithmen hängt die Laufzeit von der konkreten Eingabe ab, nicht nur von der Größe. Lineare Suche findet das Element vielleicht sofort (erste Position) – oder erst am Ende. Daher unterscheidet man drei Fälle:
9) Verwandte Notationen: Big-O, Big-Omega, Big-Theta
Streng mathematisch gibt es nicht nur Big-O, sondern drei Notationen, die das Wachstumsverhalten von verschiedenen Seiten beschreiben:
- O(f(n)) – obere Schranke: der Algorithmus wächst höchstens so schnell wie f(n). „Nicht schlechter als". Das ist die häufigste Notation.
- Ω(f(n)) – Big-Omega, untere Schranke: der Algorithmus wächst mindestens so schnell wie f(n). „Nicht besser als".
- Θ(f(n)) – Big-Theta, scharfe Schranke: der Algorithmus wächst genau wie f(n). Sowohl obere als auch untere Schranke.
In der Praxis (und in IHK-Klausuren) wird fast immer nur Big-O verwendet, oft sogar wenn eigentlich Theta gemeint ist. Bei Bubble Sort schreibt man „O(n²)", obwohl es mathematisch korrekt Θ(n²) wäre. Diese Unschärfe ist akzeptiert, weil aus dem Kontext klar ist, was gemeint ist.
10) Speicherkomplexität (Space Complexity)
Bisher haben wir über Zeitkomplexität gesprochen – wie lange ein Algorithmus läuft. Genauso wichtig ist die Speicherkomplexität: wie viel Arbeitsspeicher braucht er? Auch hier verwendet man O-Notation.
- O(1) Speicher: der Algorithmus braucht nur wenige Variablen, unabhängig von der Eingabe. In-place-Sortierungen wie Bubble Sort.
- O(n) Speicher: der Algorithmus braucht Speicher proportional zur Eingabe. Merge Sort mit Hilfsarray, eine Kopie der Liste anlegen.
- O(log n) Speicher: typisch bei Rekursion mit logarithmischer Tiefe (z.B. binäre Suche rekursiv – jeder Aufruf braucht Stack-Platz).
Es gibt oft einen Tradeoff zwischen Zeit und Speicher: ein Algorithmus kann schneller laufen, indem er Ergebnisse zwischenspeichert (Memoization). Klassisches Beispiel: rekursive Fibonacci-Berechnung. Naiv O(2ⁿ) Zeit, mit Memoization O(n) Zeit – aber dafür O(n) Speicher.
11) Typische Klausurfragen
So wird O-Notation in IHK-Klausuren abgefragt – die häufigsten Aufgabentypen:
- „Welche Zeitkomplexität hat folgender Algorithmus?" Schleifenstruktur analysieren, oberste Klasse identifizieren. Verschachtelung → multiplizieren, Folge → addieren (höhere gewinnt).
- „Vergleichen Sie Algorithmus A und B bei n = X." Konkrete Werte einsetzen und vergleichen. Achtung bei großen n: O(n²) übertrumpft O(n log n) drastisch.
- „Welcher Algorithmus ist für große Mengen besser geeignet?" Der mit der besseren Big-O-Klasse. Bei gleicher Klasse → konkrete Konstanten und Best/Average Case betrachten.
- „Was bedeutet O(log n) anschaulich?" Bei Verdopplung der Eingabe nur ein zusätzlicher Schritt. Halbierungs-Algorithmen. Bei 1 Million Elementen ~20 Schritte.
- „Erklären Sie den Unterschied zwischen Best und Worst Case." Bester Fall = optimistisch (z.B. schon sortiert). Schlechtester Fall = pessimistisch (z.B. umgekehrt sortiert). Garantien beziehen sich auf Worst Case.
Zusammenfassung
Die O-Notation (auch Landau-Notation oder Big-O) beschreibt das asymptotische Wachstumsverhalten eines Algorithmus – wie der Aufwand bei wachsender Eingabe zunimmt. Konstanten und niedrigere Terme werden weggelassen, nur der dominierende Term zählt. Wichtige Klassen (von schnell nach langsam): O(1) konstant (Array-Zugriff, Hash-Map), O(log n) logarithmisch (binäre Suche), O(n) linear (lineare Suche, Iteration), O(n log n) (Merge Sort), O(n²) quadratisch (Bubble Sort), O(2ⁿ) exponentiell (naive Fibonacci-Rekursion), O(n!) faktoriell. Praktische Bedeutung: O(n²)-Algorithmen sind ab Millionen Elementen unbrauchbar (Minuten/Stunden statt Millisekunden), O(2ⁿ) schon ab wenigen Dutzend. Analyse-Regeln: Konstanten weglassen, niedere Terme weglassen, bei Folge addieren (höchster gewinnt), bei Verschachtelung multiplizieren. Drei Fälle pro Algorithmus: Best Case (optimistisch), Average Case (realistisch), Worst Case (pessimistisch, wichtigste Größe). Verwandt: Big-Omega Ω (untere Schranke), Big-Theta Θ (scharfe Schranke). Neben Zeit- gibt es auch Speicherkomplexität – häufiger Tradeoff: weniger Zeit = mehr Speicher (Memoization). In der Praxis: O-Notation hilft bei der Auswahl der richtigen Datenstruktur (Lektion 9) und bei der Beurteilung, ob ein Algorithmus für die gegebene Datenmenge geeignet ist. Die nächste Lektion zeigt, wie verschiedene Datenstrukturen unterschiedliche O-Eigenschaften für die typischen Operationen haben.