Bei n = 100 sind das 10.000 Operationen. Bei n = 1000 sind es 1.000.000 Operationen: Zehnfache Eingabe bedeutet hundertfache Arbeit (10² = 100).
Warum das wichtig ist
Bubblesort braucht O(n²). Mergesort garantiert O(n log n). Quicksort liefert im Average Case O(n log n), im Worst Case O(n²) (bei ungünstiger Pivot-Wahl).
Bei 1.000 Einträgen (grobe Modellrechnung):
- Bubblesort: ~1.000.000 Operationen
- Mergesort: ~10.000 Operationen
Das ist Faktor 100 schneller und zwar allein durch die richtige Algorithmuswahl, nicht durch besseren Code.
Klausur-Trace: Komplexität ablesen
Die klassische Klausurfrage lautet: "Welche Big-O-Klasse hat dieser Code?". Wir gehen vier typische Muster durch, die in fast jeder Algorithmen-Klausur in irgendeiner Form auftauchen.
Beispiel 1: Eine Schleife über n
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
Eine Schleife läuft n mal, Schleifenrumpf ist O(1). Gesamt: O(n). Verdoppelst du n, verdoppelt sich die Laufzeit.
Beispiel 2: Zwei unabhängige Eingabegrößen
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// O(1) Arbeit
}
}
Hier ist die Komplexität O(m · n), nicht O(n²). Nur wenn m = n garantiert ist, darfst du O(n²) schreiben. Sonst verlierst du Information: bei m=10 und n=1 000 000 ist das Verhalten linear in n, nicht quadratisch.
Beispiel 3: Innere Schleife mit Halbierung
for (int i = 0; i < n; i++) {
int k = n;
while (k > 1) k = k / 2;
}
Äußere Schleife läuft n mal. Die innere halbiert k in jeder Iteration, das sind log₂ n Schritte. Gesamt: O(n log n). Genau dieselbe Komplexitätsklasse wie Mergesort.
Beispiel 4: Innere Schleife abhängig vom äußeren Index
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// O(1) Arbeit
}
}
Hier läuft die innere Schleife n-i mal. Summe über i = 0..n-1: n + (n-1) + ... + 1 = n(n+1)/2, also O(n²). Die "Dreiecksschleife" sieht harmloser aus als die volle verschachtelte Schleife, ist asymptotisch aber identisch (nur halb so viele Operationen, gleiche Klasse).
Entscheidungstabelle für die Klausur:
| Muster im Code | Komplexität |
|---|
Eine Schleife über n | O(n) |
Zwei verschachtelte Schleifen, beide über n | O(n²) |
Zwei verschachtelte über m und n | O(m · n) |
| Schleife mit Halbierung des Restbereichs | O(log n) |
| Rekursion mit zwei Aufrufen pro Schritt | meist O(2ⁿ) |
| Rekursion: Problem halbieren + lineare Arbeit | O(n log n) |
Merksatz: Big-O ignoriert konstante Faktoren und schaut nur auf die dominante Wachstumsrate für sehr große Eingaben. Bei kleinen n kann eine theoretisch schlechtere Klasse schneller sein, das ist der nächste Abschnitt.
