Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Big-O beschreibt das Wachstum der Laufzeit eines Algorithmus relativ zur Eingabegröße n. Statt absolute Zeiten zu messen, klassifizierst du Algorithmen in Komplexitätsklassen, die ignorieren wie schnell deine CPU ist.
Die wichtigsten Klassen, sortiert nach Geschwindigkeit:
In Klausuren wirst du oft gefragt: "Welche Big-O-Klasse hat dieser Code?". Zähl die verschachtelten Schleifen über n: eine ist O(n), zwei verschachtelte sind O(n²). Halbieren in jeder Iteration (z.B. Binäre Suche) ist O(log n).
Big-O ignoriert konstante Faktoren und schaut nur auf die dominante Wachstumsrate für sehr große Eingaben.
Beispiel: Eine Funktion, die Operationen braucht, ist O(n²). Bei großem dominiert das , alles andere ist Rauschen.
| Big-O | Name | Verhalten |
|---|---|---|
| O(1) | konstant | Egal wie groß n: gleiche Zeit |
| O(log n) | logarithmisch | Verdoppelung von n addiert nur eine Operation |
| O(n) | linear | Doppelte Eingabe = doppelte Zeit |
| O(n log n) | linearithmisch | Linear plus ein bisschen mehr |
| O(n²) | quadratisch | Doppelte Eingabe = vierfache Zeit |
| O(2ⁿ) | exponentiell | Jedes zusätzliche Element verdoppelt die Zeit |
O(1) — Array-Zugriff per Index:
int wert = arr[5];Egal ob das Array 10 oder 10 Millionen Einträge hat: der Zugriff ist immer gleich schnell.
O(n) — Linear durch ein Array suchen:
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;Im schlimmsten Fall (Element nicht vorhanden) wirst du jedes Element einmal anfassen.
O(n²) — Verschachtelte Schleife:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// ... etwas tun
}
}Bei sind das 10.000 Operationen. Bei sind es 1.000.000: Faktor 100 mehr Eingabe gibt Faktor 10.000 mehr Arbeit.
Eine Bubblesort-Implementierung braucht O(n²) Zeit. Mergesort braucht O(n log n).
Bei 1.000 Einträgen:
Das ist Faktor 100 schneller: durch die richtige Algorithmuswahl, nicht durch besseren Code.
Big-O ist eine Worst-Case-Abschätzung für sehr große . Bei kleinen Eingaben kann eine theoretisch schlechtere Komplexität schneller sein, weil sie weniger Overhead hat.
Beispiel: Für ist eine simple Insertion-Sort oft schneller als Mergesort, obwohl Insertion-Sort O(n²) und Mergesort O(n log n) ist. Java's Arrays.sort() und Python's sorted() nutzen deshalb Timsort, das bei kleinen Subarrays auf Insertion-Sort wechselt.
Merksatz: Big-O sagt dir was passiert wenn n gross wird, nicht was bei einer konkreten Eingabe wirklich am schnellsten ist.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Big-O beschreibt das Wachstum der Laufzeit eines Algorithmus relativ zur Eingabegröße n. Statt absolute Zeiten zu messen, klassifizierst du Algorithmen in Komplexitätsklassen, die ignorieren wie schnell deine CPU ist.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Bubblesort, Mergesort und Quicksort live nebeneinander. Übersichtstabelle, interaktiver Visualizer und Klausur-Quiz, das die Unterschiede festigt.
Halbiere den Suchraum bei jedem Schritt. O(log n) statt O(n): bei einer Milliarde Einträgen reichen 30 Vergleiche. Voraussetzung: sortiertes Array.
Die wichtigsten Klassen, sortiert nach Geschwindigkeit:
In Klausuren wirst du oft gefragt: "Welche Big-O-Klasse hat dieser Code?". Zähl die verschachtelten Schleifen über n: eine ist O(n), zwei verschachtelte sind O(n²). Halbieren in jeder Iteration (z.B. Binäre Suche) ist O(log n).
Big-O ignoriert konstante Faktoren und schaut nur auf die dominante Wachstumsrate für sehr große Eingaben.
Beispiel: Eine Funktion, die 3n² + 50n + 1000 Operationen braucht, ist O(n²). Bei großem n dominiert das n², alles andere ist Rauschen.
| Big-O | Name | Verhalten |
|---|---|---|
| O(1) | konstant | Egal wie groß n: gleiche Zeit |
| O(log n) | logarithmisch | Verdoppelung von n addiert nur eine Operation |
| O(n) | linear | Doppelte Eingabe = doppelte Zeit |
| O(n log n) | linearithmisch | Linear plus ein bisschen mehr |
| O(n²) | quadratisch | Doppelte Eingabe = vierfache Zeit |
| O(2ⁿ) | exponentiell | Jedes zusätzliche Element verdoppelt die Zeit |
O(1) — Array-Zugriff per Index:
int wert = arr[5];Index-Zugriff in Java: konstante Zeit, egal wie groß das Array ist.
wert = arr[5]Listen-Zugriff in Python: ebenfalls O(1).
Egal ob das Array 10 oder 10 Millionen Einträge hat: der Zugriff ist immer gleich schnell.
O(n) — Linear durch ein Array suchen:
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;Im schlimmsten Fall musst du jedes Element prüfen.
for i, wert in enumerate(arr):
if wert == target:
return i
return -1Pythonisch mit enumerate, aber das Worst-Case-Verhalten ist gleich.
Im schlimmsten Fall (Element nicht vorhanden) wirst du jedes Element einmal anfassen.
O(n²) — Verschachtelte Schleife:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// ... etwas tun
}
}Bei n = 100: 10.000 Iterationen. Bei n = 1000: 1.000.000.
for i in range(n):
for j in range(n):
# ... etwas tun
passGleiche Komplexität, andere Syntax: O(n²).
Bei n = 100 sind das 10.000 Operationen. Bei n = 1000 sind es 1.000.000: Faktor 100 mehr Eingabe gibt Faktor 10.000 mehr Arbeit.
Eine Bubblesort-Implementierung braucht O(n²) Zeit. Mergesort braucht O(n log n).
Bei 1.000 Einträgen:
Das ist Faktor 100 schneller: durch die richtige Algorithmuswahl, nicht durch besseren Code.
Big-O ist eine Worst-Case-Abschätzung für sehr große n. Bei kleinen Eingaben kann eine theoretisch schlechtere Komplexität schneller sein, weil sie weniger Overhead hat.
Beispiel: Für n < 50 ist eine simple Insertion-Sort oft schneller als Mergesort, obwohl Insertion-Sort O(n²) und Mergesort O(n log n) ist. Java's Arrays.sort() und Python's sorted() nutzen deshalb Timsort, das bei kleinen Subarrays auf Insertion-Sort wechselt.
Merksatz: Big-O sagt dir was passiert wenn n gross wird, nicht was bei einer konkreten Eingabe wirklich am schnellsten ist.
Big-O bleibt abstrakt solange du nicht siehst, was es in echt bedeutet. Schieb den Regler bis n = 1.000.000 und beobachte die Tabelle: jede Klasse zeigt dir wie lange ein moderner PC dafür bräuchte (Annahme: 1 Operation = 1 Nanosekunde).
Was du sehen wirst:
Interaktive Visualisierung
Vergleicht Wachstumsraten verschiedener Komplexitätsklassen (O(1), O(log n), O(n), O(n log n), O(n^2)).
Genau das ist Big-O. Bei kleinen n ist der Unterschied minimal: bei großen n entscheidet die Komplexität, ob dein Algorithmus in Millisekunden oder Stunden läuft. Mergesort bei einer Million Datensätzen: 20 Millisekunden. Bubblesort: 16 Minuten.
Klausurfragen mit Lösungen (6)
Antwort: O(n²)
Erklärung: Big-O ignoriert konstante Faktoren UND niedrigere Ordnungen. Es zählt nur der dominante Term: n². Daher O(n²), nicht O(5n²).
Antwort: O(log n)
Erklärung: Bei jeder Iteration halbiert sich der Suchraum. Das ist die Definition von O(log n).
Antwort: 1000000
Erklärung: n² bei n = 1000 ist 1.000 × 1.000 = 1.000.000. Quadratisch wird bei großem n schnell unhandlich.
Typ: Zahlen-Eingabe
Antwort: Konstante Operation (O(1))
Erklärung: O(1) braucht immer gleich viel Zeit: egal wie groß n ist. Selbst bei Millionen Einträgen ist es schneller als alle anderen.
Antwort: 100 Sekunden
Erklärung: Bei O(n²) wird bei zehnfacher Eingabe (100 → 1000) die Zeit hundertfach (1s → 100s). Faktor n × n = 10 × 10 = 100.
Richtige Antworten: O(1); O(log n)
Erklärung: O(1) und O(log n) wachsen langsamer als O(n) → effizienter. O(n log n), O(n²) und O(2ⁿ) wachsen schneller → ineffizienter. Klausur-Tipp: Reihenfolge auswendig lernen — O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
Typ: Multi-Select