Divide and Conquer (deutsch: Teile und Herrsche) ist ein Algorithmus-Paradigma, bei dem ein großes Problem in kleinere, unabhängige Teilprobleme zerlegt wird. Die Teilprobleme werden einzeln gelöst — meist rekursiv — und die Teillösungen anschließend zu einer Gesamtlösung zusammengesetzt. Die Methode steckt in vielen klassischen Algorithmen und bildet das Gegenstück zu Greedy und dynamischer Programmierung.
Die drei Schritte
Ein Divide-and-Conquer-Algorithmus läuft immer nach demselben Muster ab:
- Divide: Das Problem wird in zwei oder mehr Teilprobleme zerlegt.
- Conquer: Die Teilprobleme werden gelöst. Sind sie klein genug, direkt (Basisfall), sonst rekursiv nach demselben Muster.
- Combine: Die Teillösungen werden zur Lösung des Gesamtproblems zusammengesetzt.
Klassische Beispiele
- Merge Sort (stabiler Sortieralgorithmus): Liste halbieren, Hälften sortieren, sortiert zusammenführen. Laufzeit immer O(n log n).
- Quick Sort: Pivot wählen, kleiner/gleich/größer aufteilen, Teile rekursiv sortieren.
- Binäre Suche: In einem sortierten Array die Mitte prüfen und den Suchraum halbieren — O(log n).
- Karatsuba-Verfahren und Strassen-Matrixmultiplikation: schnelle Multiplikation großer Zahlen bzw. Matrizen.
Wann funktioniert Divide and Conquer?
Die Methode zahlt sich aus, wenn die Teilprobleme unabhängig sind und eine Kombination der Teillösungen wirtschaftlich ist. Überlappen sich Teilprobleme massiv, ist dynamische Programmierung meist die bessere Wahl, weil sie Zwischenergebnisse speichert statt sie neu zu berechnen. Die Big-O-Notation hilft bei der Abschätzung, ob sich die Zerlegung lohnt.
Verwandte Grundlagen: Rekursion, Greedy-Algorithmus, Dynamische Programmierung, Backtracking.