Big-O-Notation – Zeitkomplexität einfach erklärt

Die Big-O-Notation zeigt, wie schnell die Laufzeit oder der Speicherverbrauch eines Algorithmus wachsen kann, wenn die Eingabegröße zunimmt. Wenn du fragst: „Was passiert, wenn das Problem viel größer wird?“, ist Big O die übliche Art, darauf zu antworten.

Deshalb sagt man, dass lineare Suche $O(n)$ und binäre Suche $O(\log n)$ ist. Das Ziel ist nicht, exakte Millisekunden auf einem bestimmten Rechner vorherzusagen. Das Ziel ist, Wachstumsmuster zu vergleichen.

Was Big O bedeutet

Wenn ein Algorithmus für eine Eingabe der Größe $n$ die Zeit $T(n)$ benötigt, dann bedeutet

$$T(n) = O(f(n))$$

dass es Konstanten $C > 0$ und $n_0$ gibt, sodass

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

Das bedeutet: Big O ist eine Aussage über eine obere Schranke des Wachstums für hinreichend große Eingaben.

Einfach gesagt: Sobald $n$ groß genug ist, wächst die Laufzeit nicht schneller als ein konstanter Vielfaches von $f(n)$.

Warum Big O nützlich ist

Big O bietet eine rechnerunabhängige Möglichkeit, Algorithmen zu vergleichen. Ein Programm kann auf einem Laptop schneller laufen als auf einem anderen, aber der Wachstumstrend bleibt trotzdem wichtig.

Dieser Trend ist besonders wichtig, wenn sich die Eingabegröße stark verändert. Ein Algorithmus, der für $100$ Elemente gut funktioniert, kann bei $10^6$ Elementen unpraktisch werden, wenn seine Wachstumsrate schlecht ist.

Häufige Zeitkomplexitäten im Überblick

• $O(1)$: Der Aufwand bleibt beschränkt, auch wenn $n$ wächst.
• $O(\log n)$: Der Aufwand wächst langsam, oft wenn die Problemgröße wiederholt verkleinert wird.
• $O(n)$: Der Aufwand wächst ungefähr proportional zur Eingabegröße.
• $O(n \log n)$: Etwas mehr als linear, häufig bei effizienten Sortierverfahren.
• $O(n^2)$: Der Aufwand wächst wie das Quadrat der Eingabegröße, oft durch verschachtelte Schleifen über dieselben Daten.

Diese Bezeichnungen vergleichen Wachstum, nicht die exakte Geschwindigkeit. Ein $O(n)$-Algorithmus kann für kleine Eingaben trotzdem langsamer sein als ein $O(n^2)$-Algorithmus, wenn seine konstanten Faktoren groß sind.

Durchgerechnetes Beispiel: Warum lineare Suche $O(n)$ ist

Angenommen, du gehst eine Liste von links nach rechts durch und suchst nach einem Zielwert. Im schlechtesten Fall fehlt der Wert oder steht ganz am Ende, also musst du möglicherweise jedes Element genau einmal prüfen.

Wenn die Liste $n$ Elemente hat, kann die Anzahl der Prüfungen höchstens $n$ sein. Deshalb ist die Laufzeit im schlechtesten Fall

$$O(n)$$

Die wichtige Erkenntnis ist einfach: Wenn sich die Listengröße verdoppelt, kann sich auch die maximale Anzahl der Prüfungen ungefähr verdoppeln. Genau dieses Muster beschreibt Big O.

Was Big O ausblendet

Big O ignoriert beim Vergleich des Wachstums für große Eingaben absichtlich konstante Faktoren und Terme niedrigerer Ordnung.

Zum Beispiel gilt: Wenn

$$T(n) = 3n + 2$$

dann ist $T(n)$ trotzdem $O(n)$. Die Konstante $3$ und das zusätzliche $2$ sind für exakte Laufzeiten wichtig, aber sie ändern das grundlegende Wachstumsmuster nicht.

Das bedeutet nicht, dass Konstanten in der Praxis nie wichtig sind. Es bedeutet, dass Big O eine engere Frage beantwortet: wie die Kosten skalieren, wenn $n$ groß wird.

Häufige Fehler bei Big O

Fehler 1: Big O als exakte Laufzeit verstehen

$O(n)$ bedeutet nicht, dass die Laufzeit genau $n$ Schritte beträgt. Es bedeutet, dass das Wachstum nach oben durch ein konstantes Vielfaches von $n$ beschränkt ist, sobald $n$ groß genug ist.

Fehler 2: Die Bedingung für großes $n$ vergessen

Die formale Definition muss nur für alle $n \ge n_0$ gelten. Big O beschreibt asymptotisches Verhalten, nicht jede noch so kleine Eingabe.

Fehler 3: Annehmen, Big O meine immer die typische Laufzeit

In Diskussionen über Algorithmen beschreibt Big O oft die Laufzeit im schlechtesten Fall, aber das ist eine kontextabhängige Konvention. Durchschnittsfall und Best-Case-Komplexität sind andere Fragen und sollten klar bezeichnet werden.

Fehler 4: Algorithmen nur nach Big O vergleichen

Big O ist wichtig, aber Speicherverbrauch, Implementierungsaufwand und konstante Faktoren können in realen Systemen ebenfalls sehr wichtig sein.

Wo dir die Big-O-Notation begegnet

Big O kommt in der Informatik, der diskreten Mathematik und der Leistungsanalyse vor. Besonders nützlich ist sie beim Vergleichen von Algorithmen für Suche, Sortierung, Graphdurchläufe und dynamische Programmierung.

Allgemeiner wird sie immer dann verwendet, wenn dich interessiert, wie ein Prozess skaliert, und nicht nur, wie er sich bei einer festen Größe verhält.

Probiere ein ähnliches Beispiel

Nimm eine einfache verschachtelte Schleife, die ein $n \times n$-Gitter durchläuft. Zähle, wie oft die innere Aktion ausgeführt wird. Wenn der Gesamtaufwand wie $n^2$ wächst, hast du ein konkretes Beispiel dafür, warum wiederholte Schleifen über dieselben Daten oft zu $O(n^2)$-Verhalten führen.