Divide and Conquer

Divide and Conquer: teile, löse rekursiv, kombiniere (Mergesort, Quicksort, klassische Median-of-medians-Ideen).

Komplexität oft über Rekursionsgleichungen (Mastertheorem).

$$T(n)=aT(n/b)+f(n)$$

Wo gebraucht

Merge/Quick, FFT-Pipelines, parallele Aggregation, MapReduce-Idee. Zerlegen, unabhängig lösen, kombinieren.

Vertiefung

Divide and Conquer zerlegt ein Problem in kleinere Instanzen, löst diese rekursiv und setzt ihre Ergebnisse zu einer Gesamtlösung zusammen. Ein Basisfall beendet die Zerlegung. Die Form und Balance der Teilprobleme bestimmen Höhe und Breite des Rekursionsbaums.

Die Laufzeit lässt sich oft durch eine Rekurrenz ausdrücken. Bei zwei halb so grossen Teilproblemen und linearer Zusatzarbeit entsteht das Muster von Merge Sort. Wenn nur ein Teilproblem weiterverfolgt wird, wie bei binärer Suche, ergibt sich eine andere Rekurrenz.

Schwierigkeitsstufen

1. Zerlegung, Basisfall und Zusammenführung identifizieren.
2. Aus dem Ablauf eine Rekurrenz aufstellen.
3. Balance und Zusatzarbeit im Rekursionsbaum analysieren.

Fallstricke

Nicht jede Rekursion ist Divide and Conquer. Die Teilprobleme sollten klar kleiner sein und gewöhnlich weitgehend unabhängig gelöst werden. Stark überlappende Teilprobleme deuten eher auf Memoisierung oder dynamische Programmierung.