Algorithmen4Lerneinheiten21minStand30.05.2026

Divide-and-Conquer.

Fachliche Qualität

Noch nicht klassifiziertNoch nicht geprüft.

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.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

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).

Teil 1·Erklärung

Erklärung

Zur KategorieAlgorithmen.Mehr Themen entdeckenZum Themen-Hub.

Divide-and-Conquer, Algorithmen · UniProMax

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.

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).

DIVIDE: Teile das Problem in $k$ kleinere Teilprobleme (typisch $k = 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.

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 \cdot T(n/b) + f(n)$

mit:

$a$ = Anzahl Teilprobleme
$b$ = Faktor um den Eingabe reduziert
$f(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 - \epsilon})$	$\Theta(n^{\log_b a})$
2	$f(n) = \Theta(n^{\log_b a})$	$\Theta(n^{\log_b a} \log n)$
3	$f(n) = \Omega(n^{\log_b a + \epsilon})$	$\Theta(f(n))$

Beispiele:

Mergesort: $T(n) = 2 T(n/2) + n$ → $a=2, b=2, \log_b a = 1, f(n) = n$ → Fall 2 → $\Theta(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 → $\Theta(\log n)$
Karatsuba: $T(n) = 3 T(n/2) + n$ → $a=3, b=2, \log_b a = \log_2 3 ≈ 1.585, f(n) = n$ → Fall 1 → $\Theta(n^{\log_2 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	$T(n) = 7T(n/2) + O(n^2)$	$O(n^{2.807})$
FFT (Cooley-Tukey)	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$

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.

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 → $\Theta(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:

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_2 n$ , und auf jeder Ebene $O(n)$ Arbeit → insgesamt $O(n \log n)$ .

Lade Visualisierung...

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.

Anmelden, um den Fortschritt zu speichern.

Nächster Schritt

Wenn du fertig bist: jetzt üben.

Aktives Abrufen festigt Wissen schneller als nochmal lesen.

Divide-and-Conquer (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 k kleinere Teilprobleme (typisch k = 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 Teilprobleme
b = Faktor um den Eingabe reduziert
f(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

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.

Teil 3·Quiz / Klausurfragen

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

Teil 4·Quiz / Klausurfragen

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

Divide-and-Conquer.

Erklärung

Divide-and-Conquer.

Erklärung

Divide-and-Conquer (D&C)

Die Idee in einem Satz

Die 3 Phasen

Beispiel: Mergesort

Beispiel: Binäre Suche

Master-Theorem

Klassische D&C-Algorithmen

D&C vs. DP

Wann D&C?

Klausur-Faustregeln

Häufige Stolpersteine

Mergesort-Baum-Visualizer

Wenn du fertig bist: jetzt üben.

Divide-and-Conquer (D&C)

Die Idee in einem Satz

Die 3 Phasen

Beispiel: Mergesort

Beispiel: Binäre Suche

Master-Theorem

Klassische D&C-Algorithmen

D&C vs. DP

Wann D&C?

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

Mergesort-Baum-Visualizer

Praxis-Übung

Divide-and-Conquer — Praxis-Übung

Klausur-Quiz