Die O-Notation für Einsteiger: O(1), O(n), O(n hoch 2) und O(log n) erklärt

Wachstum, nicht Stoppuhrzeit

Die O-Notation handelt nicht davon, wie viele Sekunden etwas auf deinem Laptop dauert. Es geht darum, wie die Arbeit skaliert, wenn die Eingabe wächst. Zwei Algorithmen können beide O(n) sein, und doch läuft einer auf realer Hardware doppelt so schnell wegen eines kleineren konstanten Faktors. Die O-Notation wirft diese Konstante bewusst weg, weil bei genügend großem n die Form der Wachstumskurve jeden festen Multiplikator dominiert.

Die Notation behält zudem nur den am schnellsten wachsenden Term. Ein Algorithmus mit 3n hoch 2 plus 5n plus 200 Operationen ist einfach O(n hoch 2), denn sobald n groß ist, überragt der quadratische Term den Rest. Deshalb ist die O-Notation eine grobe, aber mächtige Linse: Sie nennt die Verhaltensklasse, genau das, was man braucht, um zu entscheiden, ob eine Lösung das Hundertfache an Daten übersteht.

Die vier häufigen Klassen

O(1) ist konstante Zeit: ein Array-Element per Index zu lesen oder einen Hash-Map-Schlüssel zu prüfen kostet denselben Aufwand, ob die Sammlung zehn oder zehn Millionen Elemente hält. O(log n) ist logarithmisch: die binäre Suche halbiert die verbleibenden Daten bei jedem Schritt, sodass die Suche in einer sortierten Liste von einer Milliarde Elementen nur etwa dreißig Vergleiche braucht. Das Halbieren ist das Spiegelbild des Verdoppelns, das man beim Umrechnen von Zahlen zwischen Basen sieht.

O(n) ist linear: jedes Element zu summieren oder eine Liste einmal zu durchlaufen berührt jedes Element genau einmal, sodass die Arbeit geradlinig mit n steigt. O(n hoch 2) ist quadratisch und stammt meist aus verschachtelten Schleifen, etwa dem Vergleich jedes Paars von Elementen. Bei n von 1.000 sind das eine Million Operationen; bei n von 1.000.000 eine Billion, und dort wird naiver quadratischer Code leise unbrauchbar.

Warum die gewählte Klasse zählt

Komplexität trennt einen Prototyp, der auf deiner Testdatei läuft, von Software, die Produktionsdaten übersteht. Sortieren mit einem O(n hoch 2)-Algorithmus wirkt bei hundert Zeilen sofort und friert bei einer Million ein. Der Wechsel zu einer O(n log n)-Sortierung hält dieselbe Aufgabe unter einer Sekunde. Der gewählte Algorithmus, nicht die Geschwindigkeit der Maschine, setzt die Obergrenze, wie viele Daten du bewältigst.

Allerdings ist die O-Notation asymptotisch: Sie beschreibt das Verhalten, wenn n gegen unendlich geht. Für kleine Eingaben kann eine einfachere O(n hoch 2)-Routine eine ausgefeilte O(n log n)-Routine mit hohem Overhead schlagen. Die praktische Regel lautet, die Klasse jeder Kernoperation zu kennen und dann die Teile zu optimieren, die wirklich großes n sehen, statt Konstanten in Code zu jagen, der nur winzige Eingaben verarbeitet.

Häufige Fragen

Ist ein niedrigeres Big O immer schneller?

Nicht bei kleinen Eingaben. Die O-Notation ignoriert konstante Faktoren, sodass eine O(n log n)-Methode mit hohem Aufwand gegen eine schlichte O(n hoch 2)-Schleife verlieren kann, wenn n winzig ist. Die niedrigere Klasse gewinnt, sobald die Eingabe groß genug ist.

Was ist der Unterschied zwischen O(log n) und O(n log n)?

O(log n) macht einen einzigen logarithmischen Durchgang, wie eine einzelne binäre Suche. O(n log n) leistet für jedes der n Elemente eine logarithmische Menge Arbeit, was die Kosten effizienter Sortieralgorithmen wie Merge Sort sind.

Deckt die O-Notation auch den Speicher ab?

Ja. Dieselbe Notation beschreibt die Speicherkomplexität, wie viel Zusatzspeicher ein Algorithmus mit wachsendem n braucht. Ein In-Place-Sort kann O(1) Zusatzspeicher nutzen, während einer, der die Daten kopiert, O(n) verwendet.

Warum ignorieren wir Konstanten und niedrigere Terme?

Weil bei großem n der am schnellsten wachsende Term alles andere dominiert und Konstanten von Hardware abhängen, die du nicht steuerst. Sie wegzulassen ergibt einen übertragbaren Vergleich, wie Algorithmen skalieren, unabhängig von einer einzelnen Maschine.