Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Divide-and-Conquer (D&C)
Teile ein großes Problem in mehrere kleine. Löse jedes klein. Kombiniere die Lösungen. Das ist Divide-and-Conquer, die Strategie hinter Mergesort, Quicksort, Binäre Suche, Karatsuba-Multiplikation, FFT. Klausur-Klassiker als Paradigma, 11/17 WInf-Algo-Klausuren fragen explizit nach D&C.
Die Idee in einem Satz
Divide-and-Conquer: Zerlege das Problem rekursiv in kleinere Teilprobleme (Divide), löse die Teilprobleme (Conquer), kombiniere die Lösungen zu einer Gesamtlösung (Combine).
Die 3 Phasen
- DIVIDE: Teile das Problem in
kkleinere Teilprobleme (typischk = 2). - CONQUER: Löse jedes Teilproblem rekursiv. Bei trivialer Größe: direkt lösen (Basis-Fall).
- COMBINE: Kombiniere die Teil-Lösungen zur Gesamt-Lösung.
Beispiel: Mergesort
mergesort(arr):
if len(arr) <= 1: return arr # Basis-Fall
mid = len(arr) // 2
left = mergesort(arr[:mid]) # DIVIDE + CONQUER
right = mergesort(arr[mid:]) # DIVIDE + CONQUER
return merge(left, right) # COMBINE
Divide: Array in zwei Hälften. Conquer: Rekursiv sortieren. Combine: Merge der zwei sortierten Hälften.
Beispiel: Binäre Suche
binarySearch(arr, target, lo, hi):
if lo > hi: return -1 # Basis (nicht gefunden)
mid = (lo + hi) // 2
if arr[mid] == target: return mid # Basis (gefunden)
elif arr[mid] < target:
return binarySearch(arr, target, mid+1, hi) # DIVIDE: rechte Hälfte
else:
return binarySearch(arr, target, lo, mid-1) # DIVIDE: linke Hälfte
Sonderfall: Binäre Suche teilt in 2 Hälften, geht aber nur in EINE weiter. Combine entfällt. → trotzdem D&C.
Master-Theorem
Für eine D&C-Rekurrenz der Form:
T(n) = a · T(n/b) + f(n)
mit:
a= Anzahl Teilproblemeb= Faktor um den Eingabe reduziertf(n)= Combine-Kosten
Gibt es 3 Fälle abhängig vom Vergleich f(n) vs. n^(log_b a):
| Fall | Bedingung | T(n) |
|---|---|---|
| 1 | f(n) = O(n^(log_b a - ε)) | Θ(n^(log_b a)) |
| 2 | f(n) = Θ(n^(log_b a)) | Θ(n^(log_b a) log n) |
| 3 | f(n) = Ω(n^(log_b a + ε)) | Θ(f(n)) |
Beispiele:
- Mergesort:
T(n) = 2 T(n/2) + n→a=2, b=2, log_b a = 1, f(n) = n→ Fall 2 →Θ(n log n) - Binäre Suche:
T(n) = T(n/2) + 1→a=1, b=2, log_b a = 0, f(n) = 1→ Fall 2 →Θ(log n) - Karatsuba:
T(n) = 3 T(n/2) + n→a=3, b=2, log_b a = log₂ 3 ≈ 1.585, f(n) = n→ Fall 1 →Θ(n^(log₂ 3))
Klassische D&C-Algorithmen
| Algorithmus | Rekurrenz | Laufzeit |
|---|---|---|
| Binäre Suche | T(n) = T(n/2) + O(1) | O(log n) |
| Mergesort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Quicksort (avg) | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Karatsuba-Multiplikation | T(n) = 3T(n/2) + O(n) | O(n^(1.585)) |
| Strassen-Matrix | T(n) = 7T(n/2) + O(n²) | O(n^(2.807)) |
| FFT (Cooley-Tukey) | T(n) = 2T(n/2) + O(n) | O(n log n) |
D&C vs. DP
Beide nutzen Rekursion. Unterschied:
- D&C: Teilprobleme sind unabhängig und überlappen sich nicht.
- DP: Teilprobleme überlappen sich, DP speichert ihre Ergebnisse, D&C nicht.
Mergesort (D&C): keine Überlappung, jede Hälfte wird einmal sortiert. Fibonacci-Rekursion (kann mit DP optimiert werden): fib(n-2) wird mehrfach gebraucht.
Wenn deine D&C-Rekurrenz Teilprobleme wiederholt aufruft → wechsele zu DP.
Wann D&C?
| Anzeichen | Lösung |
|---|---|
| Problem-Größe lässt sich halbieren | binäre Suche, Mergesort |
| Lösung lässt sich aus Teil-Lösungen mergen | Mergesort, FFT |
Naive O(n^k)-Algorithmus → Verbesserung gesucht | Karatsuba, Strassen |
| Teilprobleme sind unabhängig (parallelisierbar!) | parallele Algorithmen |
D&C ist besonders attraktiv für parallele/verteilte Systeme, weil die Teilprobleme unabhängig sind.
Klausur-Faustregeln
1. Drei Phasen: Divide, Conquer (rekursiv), Combine.
2. Master-Theorem zur Laufzeit-Analyse. Drei Fälle merken: f < n^(log_b a) (Fall 1), f = (Fall 2), f > (Fall 3).
3. Mergesort: a=2, b=2, f=n → Fall 2 → Θ(n log n).
4. D&C unterscheidet sich von DP durch UNABHÄNGIGE Teilprobleme. Überlappen sie sich → DP nutzen.
5. Binäre Suche ist D&C, auch wenn Combine trivial.
Häufige Stolpersteine
1. Master-Theorem falsch anwenden. Vergleich ist f(n) vs. n^(log_b a), NICHT n^a oder n^b.
2. D&C mit DP verwechseln. D&C: Teilprobleme unabhängig. DP: Teilprobleme überlappen. Bei Fibonacci wird's DP, nicht D&C.
3. Combine-Kosten unterschätzen. Beim Mergesort ist Merge O(n), nicht O(1). Bei der Rekurrenz unbedingt f(n) korrekt setzen.
4. Basis-Fall vergessen. Ohne Basis: Endlos-Rekursion. Bei Mergesort: len(arr) <= 1: return arr.
5. Annehmen, D&C sei IMMER schneller. Bei sehr kleinem n ist der Rekursions-Overhead höher als der naive Algorithmus. Quicksort wechselt oft bei n < 16 zu Insertion Sort.
Interaktiv verstehen
Mergesort-Baum-Visualizer
Sieh den Rekursions-Baum von Mergesort für ein 8-Element-Array. Du siehst:
- Divide: Array wird halbiert (binärer Baum)
- Conquer: Rekursion bis zur Basis (Einzelelemente)
- Combine: Merge von unten nach oben
Markant: die Baum-Höhe ist log₂ n, und auf jeder Ebene O(n) Arbeit → insgesamt O(n log n).
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Wenn du die Laufzeit eines D&C-Algorithmus analysieren sollst, immer Master-Theorem anwenden. Schreibe die Rekurrenz T(n) = a T(n/b) + f(n) explizit hin, dann vergleich f(n) mit n^(log_b a) → einer der 3 Fälle.
Praxis-Übung
Divide-and-Conquer, Praxis-Übung
6 Aufgaben zu D&C-Prinzip, Master-Theorem, klassischen Algorithmen.
Klausurfragen mit Lösungen (6)
- F1.Was sind die 3 Phasen von Divide-and-Conquer?
Antwort: Divide, Conquer, Combine
Erklärung: Divide (Problem teilen), Conquer (Teilprobleme rekursiv lösen), Combine (Teil-Lösungen mergen). Bei manchen Algorithmen (Binäre Suche) ist Combine trivial.
- F2.Welche Rekurrenz beschreibt Mergesort?
Antwort: T(n) = 2·T(n/2) + O(n)
Erklärung: Mergesort: 2 rekursive Aufrufe (eine pro Hälfte) + O(n) für Merge. T(n) = 2·T(n/2) + O(n). Mit Master-Theorem Fall 2: Θ(n log n).
- F3.Binäre Suche ist KEIN Divide-and-Conquer, weil sie nur in EINE Hälfte rekurriert.
Antwort: Falsch
Erklärung: FALSCH. Binäre Suche IST D&C, sie teilt in 2 Hälften (Divide) und löst rekursiv weiter (Conquer). Combine ist trivial (= das Ergebnis weiterreichen). T(n) = T(n/2) + O(1) → O(log n).
Typ: Wahr/Falsch
- F4.Mit Master-Theorem: T(n) = 4 T(n/2) + n². Welche Laufzeit?
Antwort: Θ(n² log n)
Erklärung: a=4, b=2, log_b a = log_2 4 = 2. f(n) = n² = n^(log_b a) → Fall 2 → Θ(n^2 · log n) = Θ(n² log n). Die rechnerischen Optionen 0 und 2 sind asymptotisch identisch (Θ(n²)) aber falsch, weil log n fehlt.
- F5.Welche Aussagen über D&C sind RICHTIG?
Richtige Antworten: D&C-Teilprobleme sind unabhängig; DP-Teilprobleme überlappen sich; Mergesort ist D&C; Karatsuba ist D&C (T(n) = 3T(n/2) + O(n))
Erklärung: Richtig: D&C unabhängig vs. DP überlappend, Mergesort D&C, Karatsuba D&C. Falsch: Greedy ist nicht-rekursiv lokal; Master-Theorem ist für D&C-Rekurrenzen T(n) = a·T(n/b) + f(n), nicht DP.
Typ: Multi-Select
- F6.Ordne Algorithmus seiner D&C-Rekurrenz zu:
Zuordnungen:
- Mergesort → T(n) = 2T(n/2) + O(n) → Θ(n log n)
- Binäre Suche → T(n) = T(n/2) + O(1) → Θ(log n)
- Karatsuba-Multiplikation → T(n) = 3T(n/2) + O(n) → Θ(n^1.585)
- Strassen-Matrix-Multiplikation → T(n) = 7T(n/2) + O(n²) → Θ(n^2.807)
Erklärung: Klassische D&C-Algorithmen + Rekurrenzen. Master-Theorem liefert die Laufzeit aus der Rekurrenz.
Typ: Zuordnung
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Wie unterscheidet sich D&C von dynamischer Programmierung?
Antwort: D&C-Teilprobleme sind unabhängig, DP-Teilprobleme überlappen sich
Erklärung: D&C-Teilprobleme sind UNABHÄNGIG (z.B. linke und rechte Hälfte beim Mergesort). DP-Teilprobleme ÜBERLAPPEN sich (z.B. fib(n-2) wird mehrfach gebraucht). Wenn deine Teilprobleme sich überlappen, brauchst du DP statt D&C.
- F2.Quicksort ist im Average-Case Divide-and-Conquer mit Rekurrenz T(n) = 2T(n/2) + O(n).
Antwort: Wahr
Erklärung: RICHTIG (im Average Case). Quicksort teilt um das Pivot in zwei (nahezu) gleich große Hälften, ruft sich rekursiv auf. Partition ist O(n). Average: Θ(n log n). Worst: T(n) = T(n-1) + O(n) → O(n²).
Typ: Wahr/Falsch
- F3.Master-Theorem: T(n) = T(n/3) + n. Welche Laufzeit?
Antwort: Θ(n)
Erklärung: a=1, b=3, log_b a = log_3 1 = 0. f(n) = n = n^1. Vergleich: 1 > 0 → Fall 3 → Θ(f(n)) = Θ(n). Combine dominiert die Rekurrenz.
- F4.Welche Algorithmen-Familie ist BESONDERS gut für parallele Ausführung geeignet?
Antwort: D&C (unabhängige Teilprobleme)
Erklärung: D&C ist ideal für Parallelisierung, die Teilprobleme sind UNABHÄNGIG, können also gleichzeitig gelöst werden. Frameworks wie Cilk, OpenMP nutzen das. DP hat zu viel Datenabhängigkeit.
- F5.D&C hat 3 Phasen: {{1}}, {{2}} (rekursiv), {{3}}. Das {{4}}-Theorem berechnet die Laufzeit aus T(n) = a·T(n/b) + f(n). Bei Mergesort ist a={{5}}, b=2, f(n)=O(n) → Θ(n log n).
Lösungen pro Lücke:
- {{1}}: Divide
- {{2}}: Conquer
- {{3}}: Combine
- {{4}}: Master
- {{5}}: 2
Erklärung: D&C-Vokabular. Divide-Conquer-Combine, Master-Theorem, Mergesort-Beispiel.
Typ: Lückentext
- F6.Sortiere: Mergesort-Anwendung auf [5, 2, 8, 1].
Richtige Reihenfolge:
- DIVIDE: [5, 2, 8, 1] → [5, 2] + [8, 1]
- DIVIDE: [5, 2] → [5] + [2], [8, 1] → [8] + [1]
- BASIS: Einzelelemente sind sortiert
- COMBINE: merge([5], [2]) = [2, 5], merge([8], [1]) = [1, 8]
- COMBINE: merge([2, 5], [1, 8]) = [1, 2, 5, 8]
Erklärung: Standard-Mergesort-Workflow. Erst rekursiv teilen bis zur Basis, dann von unten merger nach oben.
Typ: Reihenfolge
