Wie schnell? Die O-Notation

Bei einer Milliarde Schritten pro Sekunde braucht ein n²-Verfahren für eine Million Werte etwa 17 Minuten, ein n-log-n-Verfahren 0.02 Sekunden.

Das Wachstum zählt mehr als die genaue Zahl

Bisher haben wir Schritte genau gezählt: 45 Vergleiche, 4 Vertauschungen, 20 Prüfungen. Genaue Zahlen sind bei kleinen Beispielen nützlich, hängen aber von Details ab, etwa davon, ob Bubblesort früher aufhört oder wie ein Pivot gewählt wird. Wird die Eingabe groß, überwiegt eine Sache alles andere: wie die Zahl wächst, wenn n wächst. Ein Algorithmus, dessen Schritte wie n² wachsen, verliert irgendwann gegen einen, dessen Schritte wie n log n wachsen, egal wie sorgfältig der erste optimiert ist.

Die O-Notation (Landau-Notation) ist die Kurzschrift für dieses Wachstum. Schreibt man, ein Algorithmus sei O(n²), gesprochen „O von n Quadrat“, heißt das: Für großes n ist seine Schrittzahl höchstens eine Konstante mal n². Zwei Regeln machen den Umgang leicht. Konstante Faktoren fallen weg: 3n und n/2 sind beide O(n). Nur der am schnellsten wachsende Term bleibt: n²/2 − n/2, die Vergleiche von Selectionsort, ist O(n²), weil der n²-Teil für großes n fast alles ausmacht. Der MIT-Kurs 6.006 nutzt dieselbe Idee, wenn er Datenstrukturen und Sortierverfahren nach ihrer asymptotischen Laufzeit vergleicht.

Die üblichen Wachstumsraten

• O(1), konstant. Die Arbeit hängt nicht von n ab: den ersten Wert einer Liste lesen oder einen Wert an bekannter Position.
• O(log n), logarithmisch. Jeder Schritt halbiert das Problem: binäre Suche. Eine Million Werte, etwa 20 Schritte.
• O(n), linear. Jeder Wert wird einmal behandelt: lineare Suche, den größten Wert finden, eine Liste aufsummieren.
• O(n log n). Mergesort und Quicksort im Mittel. Das Beste, was vergleichsbasiertes Sortieren schafft.
• O(n²), quadratisch. Jedes Paar wird angeschaut: Bubblesort, Selectionsort und Insertionsort im schlechtesten Fall oder zwei ineinander verschachtelte Schleifen.
• O(2ⁿ), exponentiell. Die Arbeit verdoppelt sich mit jedem zusätzlichen Wert: jede Teilmenge von n Dingen ausprobieren oder n Scheiben bei den Türmen von Hanoi bewegen.

Was die Zahlen in Sekunden bedeuten

Angenommen, ein Computer schafft eine Milliarde (10⁹) Grundschritte pro Sekunde, ein vernünftiger runder Wert für einen Prozessorkern. So viel bedeutet jede Wachstumsrate bei einer Million Werten. O(log n) sind etwa 20 Schritte, weit unter einer Mikrosekunde. O(n) ist eine Million Schritte, eine Millisekunde. O(n log n) sind etwa 20 Millionen Schritte, 0.02 Sekunden. O(n²) sind 10¹² Schritte, tausend Sekunden, etwa 17 Minuten. O(2ⁿ) wird nie fertig: 2 hoch eine Million ist eine Zahl mit mehr als 300 000 Stellen. Deshalb zählt die Wahl des richtigen Algorithmus meist viel mehr als ein schnellerer Computer. Eine zehnmal schnellere Maschine macht aus 17 Minuten 1.7 Minuten. Der Wechsel von O(n²) zu O(n log n) macht daraus eine fünfzigstel Sekunde.

Die O-Notation aus dem Code ablesen

Oft lässt sich die Wachstumsrate direkt an der Form des Codes ablesen. Eine einzelne Schleife über die Liste ist O(n). Zwei Schleifen, eine in der anderen, beide über die Liste, sind O(n²): Für jede der n äußeren Runden macht die innere Schleife bis zu n Runden. Eine Schleife, die eine Zahl jedes Mal halbiert, etwa while (n > 1) n = Math.floor(n / 2), ist O(log n): Von 1000 aus läuft sie 9-mal, von einer Million aus 19-mal. Schritte, die nacheinander passieren, addieren sich, und der größere Term gewinnt: Eine O(n)-Schleife gefolgt von einer O(n²)-Schleife ist insgesamt O(n²).

// O(n): ein Durchlauf
let total = 0;
for (const x of list) total += x;

// O(n²): jedes Paar
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): halbieren
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Bester, mittlerer und schlechtester Fall

Ein Algorithmus kann sich bei verschiedenen Eingaben sehr verschieden verhalten. Insertionsort ist bei einer schon sortierten Liste O(n) und bei einer umgekehrten O(n²). Quicksort ist im Mittel O(n log n) und bei durchweg schlechten Pivots O(n²). Wer eine einzelne O-Angabe nennt, ohne den Fall zu sagen, meint meist den schlechtesten Fall, weil er eine Garantie ist: Schlechter wird der Algorithmus nie. Die O-Notation lässt auch Dinge weg. Sie ignoriert konstante Faktoren, deshalb kann bei kleinen Eingaben ein O(n²)-Verfahren mit sehr einfachen Schritten ein O(n log n)-Verfahren schlagen. Darum wechseln viele echte Sortierroutinen bei kurzen Listenstücken zu Insertionsort.