Algorithmische Komplexität
Die Lehre, dass ein eleganter Algorithmus jeden Supercomputer schlägt — vorausgesetzt, n ist groß genug.
Dein Computer schafft Milliarden Operationen pro Sekunde. Trotzdem kann ein einfacher verschachtelter Schleifencode bei 100.000 Einträgen zum Stillstand kommen. Der Flaschenhals ist nicht die Hardware, sondern das Wachstumsmuster des Algorithmus. Die Big-O-Notation gibt dir ein Werkzeug, um dieses Muster auf einen Blick zu erkennen und Engpässe vorherzusagen.
Keine formale Mathematik nötig — nur ein Perspektivwechsel in der Art, wie du über "schnell" und "langsam" denkst.
Skalierung — Warum Hardware schlechte Algorithmen nicht rettet
Definition
Big-O-Notation
Analogie
Definition
Die Bibliotheks-Analogie verschweigt, dass binäre Suche voraussetzt, dass der Katalog vorher sortiert wurde — die Sortierung kostet selbst O(n log n) („n mal log n“: etwas mehr als linear, die typische Klasse guter Sortierverfahren). Auch kann man in einer echten Bibliothek Regale überspringen und visuelle Hinweise nutzen.
Merke
Binäre Suche: Schritt für Schritt
- 1. Start: 1.000.000 Bücher — Mitte prüfen
- 2. Hälfte ausschließen → 500.000 übrig
- 3. Wieder halbieren → 250.000, dann 125.000 ...
- 4. Nach 10 Schritten: nur noch ~1.000 Bücher
- 5. Nach ~20 Schritten: Buch gefundenvon 1 Million!
Bei jeder Verdopplung der Bücherzahl kommt nur ein einziger Suchschritt hinzu. Das ist die Kraft logarithmischen Wachstums.
Bei n = 100.000: ~10 Milliarden Vergleiche. Vergleicht benachbarte Elemente und tauscht sie. Einfach, aber bei großen Datenmengen extrem langsam.
Bei n = 100.000: ~1,7 Millionen Vergleiche. Teilt die Liste rekursiv, sortiert und fügt zusammen. Tausende Male schneller bei großen Daten.
Achtung
Irrtum: Ein schnellerer Prozessor löst das Problem
Schnellere Hardware ist nur ein konstanter Faktor. Bei exponentiellem Wachstum lässt dich ein doppelt so schneller Computer nur eine einzige Einheit mehr von n verarbeiten. Die Wachstumsrate dominiert jede Konstante.
Nimm einen Rechner mit 10 Milliarden Operationen pro Sekunde (heutige Supercomputer schaffen über 10¹⁸). Bei einem linearen Algorithmus O(n) mit n = 1 Milliarde: fertig in 0,1 Sekunden. Bei einem exponentiellen Algorithmus O(2ⁿ)? Eine ganz andere Geschichte.
n = 50: 2⁵⁰ ≈ 1,1 × 10¹⁵ Operationen → Stunden
n = 100: 2¹⁰⁰ ≈ 1,27 × 10³⁰ Operationen
→ Länger als das Alter des Universums (~4,3 × 10¹⁷ Sekunden)
→ Selbst mit 10¹⁸ Operationen/s: rund 40.000 JahreDeshalb gelten exponentielle Algorithmen ab relativ kleinen n als unbrauchbar — egal wie schnell die Hardware ist.
O(n) vs. O(n²) — Die vier Grundklassen
Merke
Kartoffeln vs. Händeschütteln
Stell dir ein Abendessen vor. Kartoffeln schälen (O(n)): eine pro Gast — doppelt so viele Gäste, doppelt so viele Kartoffeln. Händeschütteln (O(n²)): jeder Gast schüttelt jedem anderen die Hand.
Gäste Kartoffeln Handshakes
4 4 6
10 10 45
100 100 4.950
1.000 1.000 499.500Verzehnfachung der Gäste: 10× mehr Kartoffeln, aber ~100× mehr Handshakes. Das ist der Unterschied zwischen linearem und quadratischem Wachstum.
In der Realität kann man Kartoffeln parallel schälen (mehr Hände, nur ein konstanter Faktor) und Gäste in Gruppen begrüßen — Letzteres entspricht besseren Algorithmen, die den quadratischen Aufwand vermeiden.
Achtung
Irrtum: O(n²) ist immer schlecht
Für kleine n (z.B. 20 Einträge) ist ein einfacher O(n²)-Algorithmus oft schneller als ein komplexer O(n log n)-Algorithmus mit hohem Overhead. Big-O wird kritisch, wenn n unkontrolliert wachsen kann — Nutzerdaten, Netzwerkverkehr, Datenbanktabellen.
Echte Standardbibliotheken verwenden hybride Strategien: Für kleine Arrays kommt ein einfacher O(n²)-Algorithmus wie Insertion Sort zum Einsatz (weniger Overhead). Erst bei größeren Datenmengen wird auf einen asymptotisch besseren O(n log n)-Algorithmus wie Merge Sort umgeschaltet. Das Beste aus beiden Welten.
Interaktiv: Wachstumsmuster vergleichen
Bewege den Slider, um die Eingabegröße n von 1 bis 1.000 zu variieren. Beobachte, wie unterschiedlich O(log n), O(n), O(n log n) und O(n²) wachsen — besonders ab n = 100 wird der Unterschied zwischen linearem und quadratischem Wachstum dramatisch.
Bei n=100 wird der Unterschied sichtbar: O(n²) braucht 10.000 Operationen, während O(n) nur 100 braucht. O(log n) braucht nur 6,6 — das ist 15x weniger als O(n).
Verhältnis zu O(n)
| Komplexität | Operationen | Faktor vs. O(n) |
|---|---|---|
| O(log n) | 6,6 | 15x schneller |
| O(n) | 100 | 1x (Referenz) |
| O(n log n) | 664 | 6,6x langsamer |
| O(n²) | 10.000 | 100x langsamer |
Interaktiv: Das Sortier-Rennen
Zwei Sortier-Verfahren treten mit denselben Daten gegeneinander an. Tippe, wer zuerst fertig ist, und erlebe, warum O(n log n) mit wachsendem n immer deutlicher davonzieht.
Zeit vs. Speicher — Der Trade-Off
Definition
Time-Space Trade-Off
Analogie
Definition
In der Realität sind Trade-Offs oft nichtlinear: Ein kleiner Cache kann Zugriffe um den Faktor 1.000 beschleunigen. Manche Probleme haben aber exponentiellen Platzbedarf, wo mehr Speicher nicht hilft.
Merke
Fibonacci: Exponentiell vs. Memoized
Naive Rekursion vs. Memoization
Statt Milliarden Aufrufe nur 49 echte Berechnungen. Ein kleines Speicher-Investment (49 Werte) kauft einen exponentiellen Geschwindigkeitsgewinn.
Merke
In der KI: LLM-Optimierung
Große Sprachmodelle nutzen denselben Trade-Off: Volle Präzision (32 Bit) braucht viel Speicher; ausgeliefert werden Modelle heute meist in 16 Bit, manche schon in 8 oder 4 Bit. Quantisierung (8 oder 4 Bit) senkt den Speicherbedarf gegenüber 16 Bit auf die Hälfte oder ein Viertel und beschleunigt die Inferenz — bei kontrolliertem Qualitätsverlust. Hier wird Speicherplatz gegen mathematische Präzision getauscht — die Big-O-Klasse ändert sich nicht, aber die Hardware wird massiv entlastet.
Achtung
Irrtum: Weniger Speicher ist immer besser
Gezielter Speichereinsatz (Caches, Indizes, Vorberechnungstabellen) ist eine der mächtigsten Optimierungstechniken. Das Ziel ist nicht minimaler Speicher, sondern die richtige Balance — Speicher investieren, wo er überproportional Rechenzeit spart.
Wenn du in späteren Artikeln Python-Dictionaries kennenlernst, wirst du genau diesen Trade-Off wiedersehen: Dictionaries investieren Speicher in Hash-Tabellen, um Zugriffe von O(n) auf durchschnittlich O(1) zu beschleunigen.
Merke
Das Wichtigste
- Big-O misst das Wachstumsmuster, nicht die Uhrzeit. Ein schnellerer Computer verschiebt das Problem nur — er löst eine schlechte Wachstumsrate nicht.
- Vier Klassen decken den Großteil des Alltags ab: O(1) konstant, O(log n) logarithmisch, O(n) linear, O(n²) quadratisch.
- Zeit und Speicher sind zwei Währungen, die du gegeneinander tauschst. Caching, Memoization und Indexierung sind bewusste Speicher-Investitionen, um Geschwindigkeit zu kaufen.
Prüfen
Quiz: Big-O-Notation
Was beschreibt die Big-O-Notation?
Wähle eine Antwort
1. Was beschreibt die Big-O-Notation?
2. Du verdoppelst die Anzahl der Elemente in einer Liste. Ein Algorithmus braucht jetzt viermal so lange. Welche Big-O-Klasse ist das?
3. Eine naive Fibonacci-Funktion ruft sich für fib(50) milliardenfach selbst auf. Welche Technik reduziert das auf nur 49 echte Berechnungen?
4. Ein O(n²)-Sortieralgorithmus wird manchmal einem O(n log n)-Algorithmus vorgezogen. In welcher Situation ist das sinnvoll?
Prüfen
Checkpoint: Verstehst du Big-O?
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen