Big-O-Notation beschreibt, wie schnell der Zeit- oder Speicherbedarf eines Algorithmus wächst, wenn die Eingabegröße n zunimmt. Sie liefert eine asymptotische obere Schranke — also die Größenordnung im schlechtesten Fall, ohne konstante Faktoren. Damit lassen sich Algorithmen unabhängig von der Hardware vergleichen.
Die wichtigsten Größenordnungen
- O(1) — konstant: Zugriff auf ein Array-Element, Operationen auf einer Hash-Tabelle.
- O(log n) — logarithmisch: Binäre Suche im binären Suchbaum.
- O(n) — linear: Einmaliger Durchlauf einer Liste (z.B. lineare Suche, einfache Verarbeitung).
- O(n log n): Effizientes Sortieren (Merge Sort, Heap Sort über einen Heap, Quick Sort im Schnitt).
- O(n²) — quadratisch: Verschachtelte Schleifen, einfache Sortierverfahren wie Bubble Sort.
- O(2ⁿ) — exponentiell: Viele Backtracking-Probleme im schlechtesten Fall.
- O(n!) — faktoriell: Problemstellungen wie das Handelsreisenden-Problem bei naiver Suche.
Wie man Big-O richtig liest
Konstante Faktoren und kleinere Terme werden ignoriert: O(3n + 10) ist O(n), O(n² + n) ist O(n²). Maßgeblich ist der am schnellsten wachsende Term. Neben der Zeitkomplexität gibt es die Speicherkomplexität (Space Complexity) — z.B. braucht Merge Sort zusätzlichen Speicher, während In-Place-Sortierer mit konstantem Zusatzspeicher auskommen. Auf Graphen hängt die Komplexität oft von Knoten V und Kanten E ab, etwa O(V + E) für die Traversierung mit Adjazenzliste oder Adjazenzmatrix.
Warum Big-O zählt
Ein O(n log n)-Sortieralgorithmus schlägt einen O(n²)-Algorithmus bei einer Million Elementen um Größenordnungen — egal wie schnell die Maschine ist. Die Notation hilft außerdem, Greedy, dynamische Programmierung und Divide and Conquer fair zu vergleichen. Verwandte Grundlagen: Verkettete Liste, Hash-Tabelle, Array, Datentyp.