Divide and Conquer
Teile und herrsche zerlegt ein Problem in unabhängige Teilprobleme, löst sie rekursiv und führt die Ergebnisse zusammen; der Master-Satz bestimmt üblicherweise seine Komplexität.
Zweck
Ein allgemeines Paradigma für den Entwurf effizienter Algorithmen bereitstellen, etwa Mergesort oder die schnelle Fourier-Transformation.
Mechanismus
Drei Schritte: teile (in Teilprobleme zerlegen), herrsche (Teilprobleme rekursiv lösen), kombiniere (Teillösungen verschmelzen). Master-Satz: asymptotische Schranke von T(n)=aT(n/b)+f(n). Klassiker: Mergesort O(n log n), FFT O(n log n).
Anwendungsfälle
- Algorithmenentwurf
- Sortieren und Suchen
- Polynommultiplikation