Big-O: wie die Arbeit wächst
Kurz gesagt: Big-O beschreibt, wie die Arbeit eines Algorithmus mit den Daten wächst, ohne Konstanten: O(1), O(log n), O(n), O(n log n), O(n²) und O(2ⁿ).
Problem
Hält es mit einer Million durch?
Der Shop hat einen Vertrag mit einem großen Lieferanten geschlossen. In einem Monat wächst der Katalog von 1.000 auf 1.000.000 Produkte. Im Code gibt es sechs Funktionen, durch die jedes Produkt oder jede Zahlung geht:
- der erste Preis in der Liste (für das Banner auf der Startseite);
- die Suche nach einem Preis in der sortierten Preisliste;
- die Summe der Preise (für den Bericht);
- das Sortieren der Preise (für die Seite „Günstigste zuerst“);
- die Prüfung auf doppelte Zahlungen aus der vorherigen Lektion;
- alle Kombinationen von Produkten, die ins Budget des Kunden passen.
Welche halten durch? Daten mit einer Million Produkten gibt es noch nicht, und die Sekunden auf deinem Laptop lügen sowieso. Du musst es am Code erkennen. Jeden Schritt genau zu zählen, wie bei n(n − 1) / 2, ist langsam. Und auf die Einzelheiten kommt es nicht an: Wichtig ist, wie die Arbeit wächst.
Die Idee
Big-O: was das Verdoppeln bewirkt
Big-O ist ein kurzer Name dafür, wie die Zahl der Operationen wächst, wenn n (die Datenmenge) wächst. Es nennt keine Sekunden, sondern eine Form: Was passiert mit der Arbeit, wenn sich die Daten verdoppeln.
| Klasse | Name | Beispiel aus dem Shop | n verdoppelt sich → die Arbeit |
|---|---|---|---|
| O(1) | konstant | der erste Preis | ändert sich nicht |
| O(log n) | logarithmisch | Suche in der sortierten Preisliste | ein Schritt mehr |
| O(n) | linear | die Summe der Preise | ×2 |
| O(n log n) | „n log n“ | Sortieren | etwas mehr als ×2 |
| O(n²) | quadratisch | doppelte Zahlungen | ×4 |
| O(2ⁿ) | exponentiell | alle Kombinationen im Budget | zum Quadrat |
Hier sind die sechs Funktionen. Die Preise sind in Cent, also ganze Zahlen:
static int firstPrice(int[] prices) { return prices[0];}static int total(int[] prices) { int sum = 0; for (int p : prices) { sum += p; } return sum;}static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { if (ids[i] == ids[j]) { found++; } } } return found;}firstPrice macht einen Schritt, egal wie viele Preise es gibt. total macht einen pro Preis. doublePayments macht einen pro Paar.
Sieh es dir an
O(log n): wie oft du halbierst
Die Suche in der sortierten Preisliste schaut in die Mitte. Ist der gesuchte Preis größer, wird die linke Hälfte gar nicht gebraucht und weggeworfen. Sonst fliegt die rechte Hälfte raus. Nach jeder Prüfung bleibt also die Hälfte übrig:
static int indexOf(int[] sorted, int price) { int lo = 0; int hi = sorted.length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (sorted[mid] == price) { return mid; } else if (sorted[mid] < price) { lo = mid + 1; } else { hi = mid - 1; } } return -1;}Wie viele Prüfungen, wenn der Preis nicht darin ist? So oft, wie du n halbieren kannst, bis nichts mehr übrig ist. Das ist der Logarithmus: log₂ n heißt „wie oft du halbierst“.
for (int n : new int[] {1000, 100000, 1000000, 1000000000}) { int halvings = 0; for (int left = n; left > 0; left /= 2) { halvings++; } System.out.println(n + " → " + halvings);}1000 → 10100000 → 171000000 → 201000000000 → 30Tausendmal so viele Preise (von 1.000 auf 1.000.000) sind nur 10 Prüfungen mehr. Eine Verdoppelung fügt eine hinzu. Deshalb wächst O(log n) kaum.
Mehr über die Grenzen der binären Suche (und wo man sich um eins verzählt) kommt in der Lektion „Binäre Suche“.
Sieh es dir an
O(n log n) und O(2ⁿ)
Das Sortieren nutzt das eingebaute Arrays.sort:
static int[] sortedPrices(int[] prices) { int[] copy = prices.clone(); Arrays.sort(copy); return copy;}Gute Sortieralgorithmen teilen das Array in Hälften (log n Ebenen) und gehen auf jeder Ebene einmal alles durch (n Schritte). Darum sind sie O(n log n). Wie genau, siehst du in der Lektion zu Merge Sort.
Die Kombinationen im Budget: Für jedes Produkt gibt es zwei Möglichkeiten, „nehmen“ oder „weglassen“. Darum ruft combos sich zweimal selbst auf:
static int combos(int[] prices, int i, int sum, int budget) { if (i == prices.length) { return sum <= budget ? 1 : 0; } return combos(prices, i + 1, sum, budget) + combos(prices, i + 1, sum + prices[i], budget);}Bei 1 Produkt gibt es 2 Kombinationen, bei 2 sind es 4, bei 3 sind es 8. Jedes neue Produkt verdoppelt alles, was es bisher gab. Das ist O(2ⁿ).
Alle sechs, ausgeführt mit fünf Preisen und fünf Zahlungen:
int[] prices = {1299, 450, 3999, 899, 2450};int[] sorted = sortedPrices(prices);int[] payments = {100231, 100232, 100233, 100232, 100234};System.out.println("Erster Preis: " + firstPrice(prices));System.out.println("2450 steht an Index " + indexOf(sorted, 2450));System.out.println("Summe: " + total(prices));System.out.println("Am günstigsten: " + sorted[0] + ", am teuersten: " + sorted[4]);System.out.println("Doppelte Zahlungen: " + doublePayments(payments));System.out.println("Kombinationen bis 5000: " + combos(prices, 0, 0, 5000));Erster Preis: 12992450 steht an Index 3Summe: 9097Am günstigsten: 450, am teuersten: 3999Doppelte Zahlungen: 1Kombinationen bis 5000: 18Sieh es dir an
Was das Verdoppeln bewirkt
static int combos(int[] prices, int i, int sum, int budget) { if (i == prices.length) { return sum <= budget ? 1 : 0; } return combos(prices, i + 1, sum, budget) + combos(prices, i + 1, sum + prices[i], budget);}static int firstPrice(int[] prices) { return prices[0];}static int indexOf(int[] sorted, int price) { int lo = 0; int hi = sorted.length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (sorted[mid] == price) { return mid; } else if (sorted[mid] < price) { lo = mid + 1; } else { hi = mid - 1; } } return -1;}static int total(int[] prices) { int sum = 0; for (int p : prices) { sum += p; } return sum;}static int[] sortedPrices(int[] prices) { int[] copy = prices.clone(); Arrays.sort(copy); return copy;}static int doublePayments(int[] ids) { int found = 0; for (int i = 0; i < ids.length; i++) { for (int j = i + 1; j < ids.length; j++) { if (ids[i] == ids[j]) { found++; } } } return found;}static int combos(int[] prices, int i, int sum, int budget) { if (i == prices.length) { return sum <= budget ? 1 : 0; } return combos(prices, i + 1, sum, budget) + combos(prices, i + 1, sum + prices[i], budget);}Schritt für Schritt, in Worten
- Der erste Preis: ein Schritt bei 4 Preisen und bei 8. Die Arbeit hängt nicht von n ab: O(1).
- Die binäre Suche schaut in die Mitte und wirft die Hälfte weg. 4 → 2 → 1 sind 3 Prüfungen, 8 → 4 → 2 → 1 sind 4. Doppelt so viele Preise, eine Prüfung mehr: O(log n).
- Die Summe besucht jeden Preis einmal: 4 und 8 Schritte. Doppelt so viele Preise, doppelt so viel Arbeit: O(n).
- Das Sortieren mischt Ebene für Ebene (hier Merge Sort, wie im Bench). Es gibt log n Ebenen, auf jeder höchstens n Vergleiche: 5 → 16. O(n log n).
- Doppelte Zahlungen: jede mit jeder, die danach kommt. 6 → 28: Das Dreieck wächst in zwei Richtungen. O(n²).
- Kombinationen im Budget: Jedes Produkt wird „genommen“ oder „weggelassen“, und jedes neue verdoppelt die Anzahl. 16 → 256: Bei 8 Produkten ist die Arbeit die für 4, zum Quadrat. O(2ⁿ).
Die sechs Klassen mit 4 und mit 8 Preisen. Jeder Würfel ist ein Schritt, genau so viele, wie Bench zählt. O(1) bewegt sich nicht. O(log n) bekommt einen Balken dazu. O(n) verdoppelt sich. O(n log n) verdoppelt sich und bekommt eine Ebene mehr. O(n²) wächst in zwei Richtungen. O(2ⁿ) wird aus einem Quadrat von 4 × 4 ein Quadrat von 16 × 16.
Die Idee
Konstanten und kleine Terme fallen weg
Der Bericht über doppelte Zahlungen macht n(n − 1) / 2 = n²/2 − n/2 Schritte. Warum ist er O(n²) und nicht O(n²/2 − n/2)?
Der kleinere Term verschwindet, wenn n wächst:
| n | n²/2 | n/2 | n/2 als Anteil der Summe |
|---|---|---|---|
| 10 | 50 | 5 | 10 % |
| 1.000 | 500.000 | 500 | 0,1 % |
| 100.000 | 5.000.000.000 | 50.000 | 0,001 % |
Die Konstante ändert die Form nicht. n²/2 und n² wachsen gleich: doppelt so viele Daten, vierfache Arbeit. Eine Konstante ist wie eine langsamere Maschine: Sie ändert die Sekunden, aber nicht, was passiert, wenn sich die Daten verdoppeln. Und du weißt schon, dass Sekunden lügen.
Big-O behält also nur den am schnellsten wachsenden Term, ohne die Zahl davor: 3n + 5 ist O(n), n²/2 − n/2 ist O(n²), 2n log n + 7n ist O(n log n).
Genauer, für Neugierige
Die genaue Definition: f(n) ist O(g(n)), wenn es eine Konstante c und eine Schwelle n₀ gibt, sodass f(n) ≤ c · g(n) für jedes n ≥ n₀. Das heißt: Ab irgendeinem n wächst f nicht schneller als g, bis auf eine Konstante. Also ist O(n) auch O(n²) (es ist eine obere Schranke), aber wir nennen die engste. Es gibt auch Θ (genau so viel) und Ω (mindestens so viel). In Gesprächen und Interviews meint „O(n)“ meist Θ(n).
Die Basis des Logarithmus wird ebenfalls nicht geschrieben: log₂ n und log₁₀ n unterscheiden sich um eine Konstante (log₂ n ≈ 3,32 · log₁₀ n).
Sieh es dir an
Die sechs Kurven im Browser
Führe die sechs Funktionen in Bench aus. Die Achse ist logarithmisch: Jede Marke ist ×10. O(n) ist eine Gerade, O(n²) ist doppelt so steil, und O(2ⁿ) hebt sofort ab.
- Der erste Preis
O(1) - Binäre Suche
O(log n) - Die Summe der Preise
O(n) - Sortieren (Merge Sort)
O(n log n) - Jedes Paar von Bestellungen
O(n²) - Jede Kombination im Budget
O(2ⁿ)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 |
|---|---|---|---|
| Der erste Preis | 1 | 1 | 1 |
| Binäre Suche | 4 | 10 | 17 |
| Die Summe der Preise | 10 | 1.000 | 100.000 |
| Sortieren (Merge Sort) | 21 | 8.709 | 1.536.371 |
| Jedes Paar von Bestellungen | 45 | 499.500 | ≈ 4.995.000.000 |
| Jede Kombination im Budget | 1.024 | ≈ 10³⁰¹ | ≈ 10³⁰¹⁰² |
Die Antwort für die Million Produkte: Der erste Preis, die Suche, die Summe und das Sortieren halten durch. Die doppelten Zahlungen werden zu 500 Milliarden Schritten und müssen auf die Menge aus der vorherigen Lektion umziehen. Und alle Kombinationen von einer Million Produkten lassen sich auf keinem Computer auflisten: 2 hoch eine Million ist eine Zahl mit 301.030 Stellen.
Genauer, für Neugierige
Was das eingebaute Sortieren in jeder Sprache benutzt. Arrays.sort für int[] ist Dual-Pivot-Quicksort, und für Arrays von Objekten (und List.sort) ist es TimSort. Beide sind O(n log n). Quicksort hat im schlechtesten Fall O(n²), aber Java wechselt bei Gefahr zu Heapsort, also ist es auch O(n log n). Bench zählt die Vergleiche von Merge Sort, weil man das eingebaute von außen nicht zählen kann. Die Klasse ist dieselbe.
Probier es aus
Sag die Ausgabe voraus
Die äußere Schleife läuft n = 8-mal. Die innere halbiert, bis nichts mehr übrig ist. Was gibt das Programm aus?
int n = 8;int steps = 0;for (int i = 0; i < n; i++) { for (int left = n; left > 0; left /= 2) { steps++; }}System.out.println(steps);Die innere Schleife geht 8, 4, 2, 1: 4-mal, das ist log₂ 8 + 1. Die äußere führt sie 8-mal aus: 8 × 4 = 32. n mal log n: genau die Form von O(n log n).
Probier es aus
Finde die versteckte Schleife
Die Methode zählt die verschiedenen Kunden in den Bestellungen des Monats. Sie hat nur eine Schleife und ist bei 100.000 Bestellungen trotzdem so langsam wie der Bericht über doppelte Zahlungen:
static int uniqueCustomers(int[] orders) { List<Integer> seen = new ArrayList<>(); for (int customer : orders) { if (!seen.contains(customer)) { seen.add(customer); } } return seen.size();}int[] orders = {7, 3, 7, 12, 3, 7};System.out.println(uniqueCustomers(orders));3In welcher Zeile versteckt sich die zweite Schleife?
Wähle die Zeile mit dem Fehler.
seen.contains(customer) geht die Liste Element für Element durch, bis es den Kunden findet. Das ist eine Schleife in der Schleife: Bei vielen verschiedenen Kunden ist die Arbeit O(n²). Ein Aufruf einer Methode ist nicht ein Schritt. Die Lösung ist eine Menge statt einer Liste, wie in der vorherigen Lektion: Dann ist die Prüfung ein Schritt, und alles ist O(n).
Übung
Wie viele Kombinationen
Löse die Aufgabe in deinem Editor.
Die Schritte der Kombinationen. Füge combos einen Zähler steps hinzu: ein Schritt für jede fertige Kombination (wenn i das Ende erreicht). Führe es mit 10, 11 und 12 Produkten mit Preisen von 500 + 100 · k Cent und einem Budget von 5000 aus und gib die Schritte aus:
10 Produkte: 1024 Schritte11 Produkte: 2048 Schritte12 Produkte: 4096 SchritteJedes Produkt verdoppelt die Schritte. Wie viele sind es bei 20 Produkten? Und bei 40? Rechne es aus, bevor du es ausführst.
Weitere Aufgaben
- Die Klasse jeder Funktion. Schreibe das Big-O jeder Funktion aus der Lektion „Zeitkomplexität: Schritte zählen“ auf, auch für die Verkäufe pro Produkt (50 Produkte × n Bestellungen).
- Binäre Suche mit Zähler. Füge
indexOfeinen Zähler hinzu und suche einen Preis, der nicht da ist, in 1.000 und in 100.000 sortierten Preisen. Vergleiche mit dem Programm, das halbiert. - Noch einmal eine Menge. Repariere das Zählen der verschiedenen Kunden mit einer Menge und vergleiche die Schritte bei 1.000 verschiedenen Kunden.
Test