Wie die Struktur des Codes die Komplexität offenbart

Wie man Big O aus dem Code identifiziert

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

Schleife über N Elemente: O(N)

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

Doppelte Schleifen, jede über N Elemente: O(N²)

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

Konstantzeit-Suche: O(1)

Zugriff auf ein Array-Index, Suche in einem Hash-Tabelle — unabhängig von der Größe ein Schritt.

Teilungs-und-konquere-Strategie (teile das Problem jedes Schritts): O(log N)

Binäre Suche: Jeder Check halbiert die verbleibenden Elemente.

---

Versteckte O(N²): eine Liste innerhalb einer Schleife

# Das sieht wie O(N) aus, aber es ist tatsächlich O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scannt alle Elemente von visited: O(N)
        visited.append(item)  # die gesamte Schleife: O(N²)

Die Zeile if item not in visited scannt jedes Element von visited in jeder Iteration. Ein Skannen einer Liste kostet O(N). Eine Schleife, die N Male läuft, wobei jeder Schleifendurchgang O(N) Arbeit erfordert: O(N) × O(N) = O(N²).

Dieses Muster tritt in über 1.000 Open-Source-Projekten auf. Der Fix benötigt einen Zeichen: Ersetzen Sie visited = [] durch visited = set(). Die Prüfung der Mitgliedschaft in einem Satz kostet O(1), nicht O(N). Ein Änderungsantrag. Die gleichen Ergebnisse. 1.000× schneller bei N=1.000

Klasse und behebe diesen Code

Lesen Sie diesen Code:

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

Theorie trifft Praxis

Big O in der Wildnis

Big O ist nicht nur Theorie. Sie trennt Programme, die in Sekunden abgeschlossen werden von Programmen, die bei der gleichen Aufgabe 17 Minuten dauern.

Echter Fall: Abhängigkeitskreis-Detektion in einem Build-System.

Wenn Sie Software installieren, löst Ihre Computer ein Graph der Abhängigkeiten: Paket A benötigt B, B benötigt C und so weiter. Ein Build-System prüft diesen Graph auf Kreise.

Ein O(N²)-Algorithmus zur Kreis-Detektion funktioniert bei N=100 Paketen gut. Bei N=50.000 Paketen (ein echter Projekt): es dauert 17 Minuten. Der O(N)-Fix: 10 Sekunden.

Dieser genaue Fehler existiert in GHC (Haskell-Compiler), pip (Python-Pakete-Manager), Maven (Java-Build-System), Cargo (Rust-Pakete-Manager) und 1.000+ anderen Projekten.

Nicht, weil ihre Autoren sorglos waren. visited = [] wurde geschrieben, als N klein war. Der Code verfestigte sich. N wuchs. Niemand bemerkte, bis der Build 30 Minuten dauerte.

Big O ist die Sprache, die Ihnen erlaubt, das zu benennen, was passiert ist - und es zu beheben.

---

Möchten Sie tiefer gehen? Unser unverzerrter Kurs enthält einen ganzen Kapitel über Big O, MOAD-0001 (ein echter O(N²)-Defekt, der in 1.000+ Open-Source-Projekten gefunden wurde), und warum das Benennen eines Musters Ihnen das Finden überall ermöglicht. Siehe [Das fehlende Kapitel: Algoritmische Komplexität](/de/un/unhamming_algorithmic_complexity).

Vorhersage der Build-Zeiten

Ein Build-System verwendet O(N²)-Kreis-Detektion.

Messbare Build-Zeiten:

- N=100 Pakete: 0,01 Sekunden

- N=1.000 Pakete: 1 Sekunde

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

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