Laufzeit & O-Notation
Die O-Notation beschreibt das Wachstum des Aufwands in Abhängigkeit von der Eingabegröße n — für große n.
Die wichtigsten Klassen
| O() | Name | Beispiel | n=10⁶ |
|---|---|---|---|
| O(1) | konstant | Hash-Lookup | 1 op |
| O(log n) | logarithmisch | Binäre Suche | 20 ops |
| O(n) | linear | Lineare Suche | 10⁶ ops |
| O(n log n) | linear-log | Merge Sort | 2·10⁷ ops |
| O(n²) | quadratisch | Bubble Sort | 10¹² ops 💀 |
| O(2ⁿ) | exponentiell | Naive rekursive Fib | unmöglich |
Faustregeln
- Eine Schleife → meist O(n).
- Doppelt verschachtelt → O(n²).
- Halbierung in jedem Schritt → O(log n).
- Rekursion mit zwei Aufrufen → O(2ⁿ) (außer mit Memoization).
Best/Average/Worst CaseQuicksort: Best O(n log n), Worst O(n²) (bei sortiertem Array). Daher in Praxis: randomized Quicksort oder Introsort (Wechsel auf Heapsort bei schlechten Pivots).