Wie Code-Struktur Komplexität zeigt

Big O aus Code erkennen

Big O versteckt sich in der Form deines Codes. Vier Muster decken die meisten Fälle ab:

Einfache Schleife über N Elemente: O(N)

# O(N): ein Durchgang durch die Liste
for item in list_of_n_items:
    process(item)

Verschachtelte Schleifen, jeweils über N Elemente: O(N²)

# O(N²): jedes Element mit jedem anderen Element gepaart
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Konstant-Zeit-Nachschlag: O(1)

Array-Index-Zugriff, Hash-Tabellen-Nachschlag – ein Schritt, egal wie groß die Größe.

Divide-and-Conquer (Problem halbieren bei jedem Schritt): O(log N)

Binäre Suche: Jede Prüfung halbiert die restlichen Elemente.

---

Verstecktes O(N²): eine Liste in einer Schleife

# Das sieht wie O(N) aus, ist aber tatsächlich O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scans all of visited: O(N)
        visited.append(item)  # the whole loop: O(N²)

Die Zeile if item not in visited scannt jedes Element von visited bei jeder Iteration. Ein Listen-Scan kostet O(N). Eine Schleife, die N-mal läuft und dabei O(N) Arbeit leistet: O(N) × O(N) = O(N²).

Dieses Muster erscheint in 1.000+ Open-Source-Projekten. Die Lösung erfordert ein Zeichen: Ersetze visited = [] mit visited = set(). Set-Mitgliedschaftsprüfung kostet O(1), nicht O(N). Eine Änderung. Gleiche Ergebnisse. 1.000-mal schneller bei N=1.000.

Klassifiziere & repariere diesen Code

Lies diesen Code:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

Theorie trifft Praxis

Big O in der Realität

Big O ist keine reine Theorie. Es trennt Programme, die in Sekunden fertig sind, von Programmen, die 17 Minuten dauern – für exakt dieselbe Aufgabe.

Echtes Beispiel: Zyklenerkennung in Abhängigkeiten eines Build-Systems.

Wenn du Software installierst, löst dein Computer ein Abhängigkeitsgraph auf: Paket A braucht B, B braucht C, und so weiter. Ein Build-System prüft diesen Graph auf Zyklen.

Ein O(N²)-Zykluserkennungsalgorithmus funktioniert gut bei N=100 Paketen. Bei N=50.000 Paketen (ein echtes Projekt): es dauert 17 Minuten. Die O(N)-Lösung: 10 Sekunden.

Dieses exakte Defekt existiert in GHC (Haskell-Compiler), pip (Python-Paketmanager), Maven (Java Build-System), Cargo (Rust-Paketmanager) & 1.000+ anderen Projekten.

Nicht weil ihre Autoren unvorsichtig waren. visited = [] wurde geschrieben, als N klein war. Der Code verhärtete. N wuchs. Niemand bemerkte es, bis der Build eine halbe Stunde dauerte.

Big O ist das Vokabular, das dich benennen lässt, was geschah – & es reparieren kannst.

---

Willst du tiefer eintauchen? Unser unhamming-Kurs enthält ein vollständiges Kapitel über Big O, MOAD-0001 (ein echtes O(N²)-Defekt in 1.000+ Open-Source-Projekten) & warum das Benennen eines Musters dir hilft, es überall zu finden. Siehe The Missing Chapter: Algorithmic Complexity.

Vorhersage der Build-Zeiten

Ein Build-System verwendet O(N²)-Zyklenerkennung.

Gemessene Build-Zeiten:

- N=100 Pakete: 0,01 Sekunden

- N=1.000 Pakete: 1 Sekunde

Für O(N²): Zeit skaliert als (N_new / N_old)².

Für O(N): Zeit skaliert als (N_new / N_old).