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).
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
Klausur-Tipp: Wenn du die Laufzeit eines D&C-Algorithmus analysieren sollst — immer Master-Theorem anwenden. Schreibe die Rekurrenz explizit hin, dann vergleich mit → einer der 3 Fälle.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
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).
k kleinere Teilprobleme (typisch k = 2).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.
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.
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-KostenGibt 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:
T(n) = 2 T(n/2) + n → a=2, b=2, log_b a = 1, f(n) = n → Fall 2 → Θ(n log n)T(n) = T(n/2) + 1 → a=1, b=2, log_b a = 0, f(n) = 1 → Fall 2 → Θ(log n)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))| 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 |
Beide nutzen Rekursion. Unterschied:
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.
| 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.
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.
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.
Sieh den Rekursions-Baum von Mergesort für ein 8-Element-Array. Du siehst:
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.
6 Aufgaben zu D&C-Prinzip, Master-Theorem, klassischen Algorithmen.
Klausurfragen mit Lösungen (6)
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.
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).
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
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.
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
Zuordnungen:
Erklärung: Klassische D&C-Algorithmen + Rekurrenzen. Master-Theorem liefert die Laufzeit aus der Rekurrenz.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
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.
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
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.
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.
Lösungen pro Lücke:
Erklärung: D&C-Vokabular. Divide-Conquer-Combine, Master-Theorem, Mergesort-Beispiel.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Mergesort-Workflow. Erst rekursiv teilen bis zur Basis, dann von unten merger nach oben.
Typ: Reihenfolge
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) |