Teile und herrsche (Divide and Conquer)

Kurz: Teile und herrsche zerlegt ein Problem in kleinere gleichartige Teilprobleme, löst sie (oft rekursiv) und setzt die Teillösungen zusammen.

Genauer: Drei Schritte: teilen, die Teile lösen, zusammenführen. Klassische Beispiele sind Mergesort, Quicksort und die Binäre Suche. Oft ergibt sich daraus eine Laufzeit von O(n log n) statt O(n²).

Im Detail

• Basisfall: Die Zerlegung endet, wenn das Teilproblem trivial ist.
• Master-Theorem: Hilft, die Laufzeit solcher rekursiven Verfahren zu berechnen.
• Parallelisierung: Teilprobleme sind unabhängig und lassen sich auf mehrere Kerne verteilen.
• Weitere Beispiele: Schnelle Fourier-Transformation, Matrixmultiplikation nach Strassen, Karatsuba-Multiplikation.
• Abgrenzung: Bei überlappenden Teilproblemen ist Dynamische Programmierung besser.

Siehe auch: Rekursion, Big-O-Notation