Zurück zum Lernbereich

Algorithmische Komplexität

Die Lehre, dass ein eleganter Algorithmus jeden Supercomputer schlägt — vorausgesetzt, n ist groß genug.

  • Grundlagen
  • 14 min
  • Einsteiger

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Wie schnell ein Programm läuft

Was ist Big-O?

Ein Algorithmus ist ein Plan für den Computer. Wenn du mehr Daten hast, braucht der Computer länger. Das Wachstum der Arbeit nennt man Big-O. Big-O zeigt: Wird das Programm schnell oder langsam?

Vier Wachstumsklassen

Es gibt vier Stufen.
O(1) bedeutet: gleich schnell, egal wie viel. O(n) bedeutet: doppelt so viele Daten, doppelt so viel Arbeit. O(n²) bedeutet: doppelt so viele Daten, viermal so viel Arbeit.

Warum das wichtig ist

Schnellere Hardware hilft nicht immer. Bei einem schlechten Programm bleibt der Computer langsam. Bei vielen Daten kommt er zum Stillstand. Mit einem besseren Programm geht alles schnell.

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

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.

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. 1. Start: 1.000.000 Bücher — Mitte prüfen
  2. 2. Hälfte ausschließen → 500.000 übrig
  3. 3. Wieder halbieren → 250.000, dann 125.000 ...
  4. 4. Nach 10 Schritten: nur noch ~1.000 Bücher
  5. 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.

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. 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 Jahre

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.

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.500

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 (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.

Steuerung
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ätOperationenFaktor vs. O(n)
O(log n) 6,615x schneller
O(n) 1001x (Referenz)
O(n log n) 6646,6x langsamer
O(n²) 10.000100x 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

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 pro Kreuzung, 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.

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

Naive Rekursion — O(2ⁿ) fib(50): rund 40 Milliarden Funktionsaufrufe (Obergrenze 2⁵⁰ ≈ 1,1 Billiarden). Jeder Aufruf berechnet alles neu — je nach Sprache Minuten bis Stunden 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 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

  1. Big-O misst das Wachstumsmuster, nicht die Uhrzeit. Ein schnellerer Computer verschiebt das Problem nur — er löst eine schlechte Wachstumsrate nicht.
  2. Vier Klassen decken den Großteil des Alltags ab: O(1) konstant, O(log n) logarithmisch, O(n) linear, O(n²) quadratisch.
  3. 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

Noch offen

Was beschreibt die Big-O-Notation?

Wähle eine Antwort

Auflösung: 1) B · 2) C · 3) C · 4) B

Prüfen

Checkpoint: Verstehst du Big-O?

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen