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).
Erklärung
Big-O beschreibt eine asymptotische obere Schranke des Wachstums einer Funktion (typischerweise Laufzeit oder Speicher) relativ zur Eingabegröße n. Statt absolute Zeiten zu messen, klassifizierst du Algorithmen in Komplexitätsklassen wie O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), die konstante Faktoren und CPU-Geschwindigkeit ignorieren. Du lernst hier die typische Klausurfrage "Welche Laufzeit hat dieser Code?", die Worst/Average/Best-Case-Abgrenzung, wie du an verschachtelten Schleifen die Komplexität ablesest, warum O(n²) schon bei n=10 000 zu langsam wird und warum O(2ⁿ) bei n=50 bereits unpraktikabel ist.
In Klausuren ist mit Big-O meistens die Worst-Case-Laufzeit gemeint, wenn nichts anderes angegeben ist. Big-O kann aber genauso gut Average Case, Best Case oder Speicherbedarf beschreiben, es ist nur eine Wachstumsschranke, kein "Worst-Case-Synonym".
Die wichtigsten Klassen, sortiert nach Geschwindigkeit:
- O(1): konstant, z. B. Array-Index-Zugriff. Hashmap-Lookup ist im Average Case O(1) bei guter Hash-Funktion. Insert-Operationen sind amortisiert O(1), weil gelegentliche Resize-Operationen über viele Inserts hinweg abgeschrieben werden. Worst Case je nach Implementierung schlechter (z. B. viele Hash-Kollisionen).
- O(log n): logarithmisch, z.B. Binäre Suche oder Heap-Operationen
- O(n): linear, z.B. Lineare Suche oder ein Array-Durchlauf
- O(n log n): quasilinear, z.B. Mergesort (garantiert), Quicksort (Average Case)
- O(n²): quadratisch, z.B. Bubblesort, oder zwei verschachtelte Schleifen, die jeweils proportional zu
nlaufen - O(2ⁿ): exponentiell, z.B. naive Fibonacci-Rekursion oder Brute-Force über alle Teilmengen ohne Memoisierung
In Klausuren wirst du oft gefragt: "Welche Big-O-Klasse hat dieser Code?". Faustregel: zähl verschachtelte Schleifen über n, eine ist O(n), zwei verschachtelte (beide proportional zu n) sind O(n²). Halbieren in jeder Iteration (z.B. Binäre Suche) ist O(log n). Wenn die innere Schleife z. B. logarithmisch läuft oder von i abhängt, kann ein anderes Ergebnis entstehen, dann genauer zählen.
Die Idee in einem Satz
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.
Die wichtigsten Klassen
| 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 |
Wachstum konkret (Modellannahme: 1 Operation = 1 ns)
| n | log₂ n | n | n log₂ n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | 3 ns | 10 ns | 33 ns | 100 ns | ~1 µs |
| 100 | 7 ns | 100 ns | 664 ns | 10 µs | astronomisch |
| 1 000 | 10 ns | 1 µs | 10 µs | 1 ms | astronomisch |
| 1 000 000 | 20 ns | 1 ms | 20 ms | 16 min | astronomisch |
Schon bei n = 10⁶ trennt sich O(n²) deutlich vom Rest. Bei n = 10⁹ ist O(n²) praktisch nicht mehr berechenbar.
Konkrete Beispiele
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 Operationen: Zehnfache Eingabe bedeutet hundertfache Arbeit (10² = 100).
Warum das wichtig ist
Bubblesort braucht O(n²). Mergesort garantiert O(n log n). Quicksort liefert im Average Case O(n log n), im Worst Case O(n²) (bei ungünstiger Pivot-Wahl).
Bei 1.000 Einträgen (grobe Modellrechnung):
- Bubblesort: ~1.000.000 Operationen
- Mergesort: ~10.000 Operationen
Das ist Faktor 100 schneller und zwar allein durch die richtige Algorithmuswahl, nicht durch besseren Code.
Klausur-Trace: Komplexität ablesen
Die klassische Klausurfrage lautet: "Welche Big-O-Klasse hat dieser Code?". Wir gehen vier typische Muster durch, die in fast jeder Algorithmen-Klausur in irgendeiner Form auftauchen.
Beispiel 1: Eine Schleife über n
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
Eine Schleife läuft n mal, Schleifenrumpf ist O(1). Gesamt: O(n). Verdoppelst du n, verdoppelt sich die Laufzeit.
Beispiel 2: Zwei unabhängige Eingabegrößen
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// O(1) Arbeit
}
}
Hier ist die Komplexität O(m · n), nicht O(n²). Nur wenn m = n garantiert ist, darfst du O(n²) schreiben. Sonst verlierst du Information: bei m=10 und n=1 000 000 ist das Verhalten linear in n, nicht quadratisch.
Beispiel 3: Innere Schleife mit Halbierung
for (int i = 0; i < n; i++) {
int k = n;
while (k > 1) k = k / 2;
}
Äußere Schleife läuft n mal. Die innere halbiert k in jeder Iteration, das sind log₂ n Schritte. Gesamt: O(n log n). Genau dieselbe Komplexitätsklasse wie Mergesort.
Beispiel 4: Innere Schleife abhängig vom äußeren Index
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// O(1) Arbeit
}
}
Hier läuft die innere Schleife n-i mal. Summe über i = 0..n-1: n + (n-1) + ... + 1 = n(n+1)/2, also O(n²). Die "Dreiecksschleife" sieht harmloser aus als die volle verschachtelte Schleife, ist asymptotisch aber identisch (nur halb so viele Operationen, gleiche Klasse).
Entscheidungstabelle für die Klausur:
| Muster im Code | Komplexität |
|---|---|
Eine Schleife über n | O(n) |
Zwei verschachtelte Schleifen, beide über n | O(n²) |
Zwei verschachtelte über m und n | O(m · n) |
| Schleife mit Halbierung des Restbereichs | O(log n) |
| Rekursion mit zwei Aufrufen pro Schritt | meist O(2ⁿ) |
| Rekursion: Problem halbieren + lineare Arbeit | O(n log n) |
Merksatz: Big-O ignoriert konstante Faktoren und schaut nur auf die dominante Wachstumsrate für sehr große Eingaben. Bei kleinen
nkann eine theoretisch schlechtere Klasse schneller sein, das ist der nächste Abschnitt.
Was Big-O NICHT sagt
Big-O beschreibt asymptotisches Wachstum für sehr große n und ignoriert Konstanten. 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. Python's sorted() nutzt deshalb Timsort, das bei kleinen Subarrays auf Insertion-Sort wechselt. Java's Arrays.sort() nutzt Timsort nur für Objekt-Arrays; bei primitiven Arrays kommt seit Java 7 Dual-Pivot Quicksort zum Einsatz (Praxis-Hinweis, durch die OpenJDK-Doku belegt, kein direkter Stoff aus den ALGORITHMS-Trusted-Sources CLRS/Sedgewick/Ottmann).
Reale Laufzeiten hängen außerdem stark von Hardware, Cache, Sprache, Speicherzugriff, Implementierungs-Konstanten und Datenverteilung ab, Big-O vergleicht Wachstum, nicht Benchmark-Zeiten.
Merksatz: Big-O sagt dir was passiert wenn n groß wird, nicht was bei einer konkreten Eingabe wirklich am schnellsten ist.
Interaktiv
Wachstum & Realzeit
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 (Modellannahme: 1 abstrakte Operation = 1 Nanosekunde, das ist eine didaktische Vereinfachung, reale Laufzeiten variieren stark):
- Bei n = 1.000 sind O(1), O(log n), O(n) und O(n log n) typischerweise unter einer Millisekunde. O(n²) liegt je nach Konstanten schon im Millisekunden-Bereich, O(2ⁿ) ist bei n = 1000 völlig unpraktikabel (2¹⁰⁰⁰ ist astronomisch groß)
- Bei n = 100.000 trennt sich O(n²) von der Konkurrenz: schon 10 Sekunden
- Bei n = 1 Million ist O(n²) bei 16 Minuten: Bubblesort wäre ein No-Go
- O(log n) bleibt selbst bei einer Million unter einer Mikrosekunde
Die Zeiten sind nur Modellwerte zur Veranschaulichung. Big-O vergleicht Wachstum, nicht echte Benchmark-Zeiten, reale Laufzeiten hängen von Hardware, Cache, Sprache und Implementierungs-Konstanten ab.
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. Bei Modellannahme n log₂ n und 1 ns pro abstrakter Operation: Mergesort bei einer Million Datensätzen ca. 20 ms (n log₂ n ≈ 20 Mio Operationen). Bubblesort bei einer Million: ca. 16 Minuten (n²/2 ≈ 5 · 10^(11) Operationen). Reale Laufzeiten können stark abweichen.
Quiz
Klausurfragen mit Lösungen (6)
- F1.Eine Funktion braucht 5n² + 100n + 50 Operationen. Welche engste Big-O-Klasse beschreibt die dominante Wachstumsrate?
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²).
- F2.Welche Komplexitätsklasse hat eine binäre Suche im sortierten Array?
Antwort: O(log n)
Erklärung: Bei jeder Iteration halbiert sich der Suchraum. Das ist die Definition von O(log n).
- F3.Eine verschachtelte Schleife läuft n × n Mal. Wie oft wird der innere Block bei n = 1000 ausgeführt?
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
- F4.Welche der folgenden Algorithmen ist im Worst Case AM SCHNELLSTEN für ein Array der Größe 1 Million?
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.
- F5.Wenn ein Algorithmus für n = 100 Eingabewerte 1 Sekunde braucht und O(n²) ist, wie lange braucht er ungefähr für n = 1000?
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.
- F6.Welche der folgenden Komplexitätsklassen wachsen asymptotisch langsamer als O(n)? (mehrere Antworten möglich)
Richtige Antworten: O(1); O(log n)
Erklärung: Asymptotisch wachsen O(1) und O(log n) langsamer als O(n) → effizienter für große `n`. O(n log n), O(n²) und O(2ⁿ) wachsen schneller → ineffizienter. **Achtung**: Für kleine Eingaben können Konstanten und Overhead trotzdem entscheiden, ein O(n)-Algorithmus mit kleinen Konstanten kann bei kleinen `n` schneller sein als ein O(log n)-Algorithmus mit hohem Overhead. 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
