Die Lehre, dass ein eleganter Algorithmus jeden Supercomputer schlägt — vorausgesetzt, n ist groß genug.
Grundlagen 14 min Einsteiger 3. Mai 2026
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
Big-O-Notation
AnalogieDefinition
Stell dir vor, du suchst ein Buch in einer Bibliothek mit n Büchern. Strategie A (lineare Suche, O(n)): Du gehst Buch für Buch durch — im schlimmsten Fall n Schritte. Strategie B (binäre Suche, O(log n)): Der Katalog ist sortiert, du halbierst den Suchbereich mit jedem Schritt. Bei 1.000 Büchern: A braucht bis zu 1.000 Schritte, B etwa 10. Bei 1 Million Büchern: A braucht bis zu 1.000.000 Schritte, B etwa 20.
Analogie:
Stell dir vor, du suchst ein Buch in einer Bibliothek mit n Büchern. Strategie A (lineare Suche, O(n)): Du gehst Buch für Buch durch — im schlimmsten Fall n Schritte. Strategie B (binäre Suche, O(log n)): Der Katalog ist sortiert, du halbierst den Suchbereich mit jedem Schritt. Bei 1.000 Büchern: A braucht bis zu 1.000 Schritte, B etwa 10. Bei 1 Million Büchern: A braucht bis zu 1.000.000 Schritte, B etwa 20.
Definition:
Die Big-O-Notation klassifiziert das Wachstum des Ressourcenverbrauchs eines Algorithmus mit der Eingabegröße n. Sie ignoriert Konstanten und konzentriert sich auf den dominanten Term. O(1) heißt konstant, O(log n) logarithmisch, O(n) linear, O(n²) quadratisch, O(2ⁿ) exponentiell. Entwickelt wurde die Notation im späten 19. Jahrhundert von Bachmann und Landau; Knuth machte sie zum Standardwerkzeug der Informatik.
Die Bibliotheks-Analogie verschweigt, dass binäre Suche voraussetzt, dass der Katalog vorher sortiert wurde — die Sortierung kostet selbst O(n log n). Auch kann man in einer echten Bibliothek Regale überspringen und visuelle Hinweise nutzen.
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 gefunden (von 1 Million!)
Bei jeder Verdopplung der Bücherzahl kommt nur ein einziger Suchschritt hinzu. Das ist die Kraft logarithmischen Wachstums.
Bubble Sort (O(n²))
Bei n = 100.000: ~10 Milliarden Vergleiche. Vergleicht benachbarte Elemente und tauscht sie. Einfach, aber bei großen Datenmengen extrem langsam.
Merge Sort (O(n log n))
Bei n = 100.000: ~1,7 Millionen Vergleiche. Teilt die Liste rekursiv, sortiert und fügt zusammen. Tausendfach schneller bei großen Daten.
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.
Deep Dive: Der Supercomputer verliert
Ein Supercomputer schafft 10 Milliarden Operationen pro Sekunde. 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)
Deshalb gelten exponentielle Algorithmen ab relativ kleinen n als unbrauchbar — egal wie schnell die Hardware ist.
O(n) vs. O(n²) — Die vier Grundklassen
O(1) — Konstant Aufwand ändert sich nicht mit n. Beispiel: Zugriff auf ein Array-Element per Index.
O(log n) — Logarithmisch Wächst extrem langsam. Verdopplung von n = ein Schritt mehr. Beispiel: Binäre Suche.
O(n) — Linear Verdopplung von n = doppelter Aufwand. Beispiel: Einmal durch eine Liste laufen.
O(n²) — Quadratisch Verdopplung von n = vierfacher Aufwand. Beispiel: Alle Paare vergleichen.
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.
Verzehnfachung 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 und Gäste in Gruppen begrüßen — das entspricht besseren Algorithmen, die den quadratischen Aufwand vermeiden.
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.
Deep Dive: Hybride Sortierung in der Praxis
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) und O(n²) wachsen — besonders ab n = 100 wird der Unterschied zwischen linearem und quadratischem Wachstum dramatisch.
11000
O(log n)6.6
O(n)100
O(n log n)664
O(n²)10.000
Moderater Input
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.
Sortier-Rennen wird geladen ...
Zeit vs. Speicher — Der Trade-Off
Time-Space Trade-Off
AnalogieDefinition
Stell dir vor, du fährst zu einem neuen Ziel. Option A: An jeder Kreuzung holst du Karte und Kompass heraus und berechnest den Weg neu — O(n) Zeit, kein Speicher. Option B: Du berechnest die Route einmal vorher, schreibst sie auf einen Zettel und liest an jeder Kreuzung einfach ab — O(1) Zeit pro Kreuzung, O(n) Speicher für den Zettel. Ein kleines Speicher-Investment (der Routenzettel) spart dir bei jeder Kreuzung Rechenzeit.
Analogie:
Stell dir vor, du fährst zu einem neuen Ziel. Option A: An jeder Kreuzung holst du Karte und Kompass heraus und berechnest den Weg neu — O(n) Zeit, kein Speicher. Option B: Du berechnest die Route einmal vorher, schreibst sie auf einen Zettel und liest an jeder Kreuzung einfach ab — O(1) Zeit pro Kreuzung, O(n) Speicher für den Zettel. Ein kleines Speicher-Investment (der Routenzettel) spart dir bei jeder Kreuzung Rechenzeit.
Definition:
Algorithmen verbrauchen zwei Ressourcen: Zeit (Rechenschritte) und Speicher. Der Time-Space Trade-Off bedeutet: Man kann oft Speicher investieren, um Zeit zu sparen (Caching, Indexierung, Memoization) — oder Speicher sparen auf Kosten von Neuberechnung. Beispiel: Naive Fibonacci-Rekursion ist O(2ⁿ) Zeit; mit Memoization wird sie O(n) Zeit bei O(n) Speicher.
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.
Fibonacci: Exponentiell vs. Memoized
Naive Rekursion vs. Memoization
Naive Rekursion — O(2ⁿ) fib(50): ~2⁵⁰ ≈ 1,1 Billiarden Funktionsaufrufe. Jeder Aufruf berechnet alles neu — Stunden bis Tage Rechenzeit.
Memoization — O(n) fib(50): nur 49 echte Berechnungen + 49 gespeicherte Werte. Ergebnis sofort verfügbar — das ist die Kraft des Speicher-Investments.
Statt Billiarden Aufrufe nur 49 echte Berechnungen. Ein kleines Speicher-Investment (49 Werte) kauft einen exponentiellen Geschwindigkeitsgewinn.
In der KI: LLM-Optimierung
Große Sprachmodelle nutzen denselben Trade-Off: Volle Präzision (32 Bit) braucht viel Speicher, liefert maximale Genauigkeit. Quantisierung (8 oder 4 Bit) halbiert oder viertelt den Speicherbedarf 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.
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 O(1) zu beschleunigen.
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 90% 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.
Quiz: Big-O-Notation
Frage 1 / 4
Noch offen
Was beschreibt die Big-O-Notation?
1. Was beschreibt die Big-O-Notation?
☐ A) Wie schnell der Prozessor eines Computers ist
☐ B) Das Wachstumsmuster des Ressourcenverbrauchs eines Algorithmus bei steigender Eingabegröße
☐ C) Die exakte Anzahl Sekunden, die ein Algorithmus braucht
☐ D) Welche Programmiersprache verwendet wird
2. Du verdoppelst die Anzahl der Elemente in einer Liste. Ein Algorithmus braucht jetzt viermal so lange. Welche Big-O-Klasse ist das?
☐ A) O(1)
☐ B) O(n)
☐ C) O(n²)
☐ D) O(log n)
3. Eine naive Fibonacci-Funktion ruft sich für fib(50) milliardenfach selbst auf. Welche Technik reduziert das auf nur 49 echte Berechnungen?
☐ A) Einen schnelleren Computer verwenden
☐ B) Den Code in einer schnelleren Sprache schreiben
☐ C) Memoization — bereits berechnete Ergebnisse speichern
☐ D) Kürzere Variablennamen verwenden
4. Ein O(n²)-Sortieralgorithmus wird manchmal einem O(n log n)-Algorithmus vorgezogen. In welcher Situation ist das sinnvoll?
☐ A) Wenn der Datensatz Millionen von Einträgen hat
☐ B) Wenn n klein ist (z.B. 20 Elemente) und der einfachere Algorithmus weniger Overhead hat
☐ C) Wenn der Computer einen schnellen Prozessor hat
☐ D) Wenn unbegrenzt Speicher verfügbar ist
Auflösung: 1) B · 2) C · 3) C · 4) B
Checkpoint: Verstehst du Big-O?
Warum scheitert ein exponentieller Algorithmus selbst auf dem schnellsten Supercomputer, sobald n groß genug wird?
Du verdoppelst die Eingabedaten. Ein Algorithmus braucht jetzt viermal so lange. Um welche Big-O-Klasse handelt es sich?
Naive Fibonacci-Rekursion ist extrem langsam. Welche Technik reduziert die Laufzeit von O(2ⁿ) auf O(n), und was kostet sie?