Teile und Herrsche

Teile und Herrsche (Divide and Conquer) ist ein Paradigma für den Algorithmenentwurf, das ein Problem löst, indem es dieses in kleinere Unterprobleme desselben Typs aufteilt, diese rekursiv löst und ihre Lösungen zu einer Lösung für das ursprüngliche Problem kombiniert.

Definition

Ein Divide-and-Conquer-Algorithmus zerlegt ein Problem rekursiv in zwei oder mehr Unterprobleme desselben oder eines verwandten Typs, bis die Unterprobleme einfach genug sind, um direkt gelöst zu werden. Anschließend werden die Lösungen der Unterprobleme kombiniert, um die Antwort auf das ursprüngliche Problem zu erhalten.

Scope

Dieses Thema behandelt die dreistufige Struktur von Divide-and-Conquer-Algorithmen (Teilen, Herrschen, Kombinieren), kanonische Beispiele wie Mergesort, Quicksort, binäre Suche sowie schnelle Ganzzahl- und Matrixmultiplikation und die rekursionsbasierte Analyse ihrer Laufzeiten. Es ist eng mit dem Master-Theorem und den Techniken zur Lösung von Rekursionen verbunden, die zur Analyse solcher Algorithmen verwendet werden.

Core questions

• Wie wird ein Problem so zerlegt, dass Unterprobleme unabhängig und von gleicher Form sind?
• Welche Arbeit wird im Kombinationsschritt geleistet und wie beeinflusst sie die Gesamtkosten?
• Wie werden die resultierenden Rekursionen gelöst, um asymptotische Laufzeiten zu erhalten?
• Wann übertrifft Divide-and-Conquer einen einfachen iterativen Ansatz?

Key concepts

• Teilen, Herrschen, Kombinieren
• Rekursionsbeziehungen
• Master-Theorem
• Mergesort
• Quicksort
• Binäre Suche
• Karatsuba-Multiplikation
• Strassen-Matrixmultiplikation

Key theories

Master-Theorem für Rekursionen

Das Master-Theorem liefert geschlossene asymptotische Lösungen für Divide-and-Conquer-Rekursionen der Form T(n) = aT(n/b) + f(n), indem es die Kosten der rekursiven Unterprobleme mit den Kombinationskosten f(n) vergleicht.

Subquadratische Multiplikation durch Zerlegung

Das rekursive Aufteilen von Operanden und die Reduzierung der Anzahl rekursiver Multiplikationen (wie bei der Karatsuba-Multiplikation und Strassens Matrixmultiplikation) führt zu asymptotisch schnelleren Algorithmen als die naiven quadratischen und kubischen Methoden.

Clinical relevance

Divide-and-Conquer liegt vielen der am weitesten verbreiteten Algorithmen zugrunde: effizientes Sortieren (Mergesort, Quicksort) in Standardbibliotheken, binäre Suche in Suchroutinen, die schnelle Fourier-Transformation in der Signal- und Bildverarbeitung und schnelle Multiplikation, die in der Kryptographie und der Arithmetik beliebiger Genauigkeit verwendet wird.

History

Mergesort wird John von Neumann (1945) zugeschrieben. C. A. R. Hoare veröffentlichte Quicksort im Jahr 1962. Karatsubas subquadratische Multiplikation von 1960 und Strassens Matrixmultiplikationsalgorithmus von 1969 zeigten, dass die rekursive Zerlegung klassische Grenzen übertreffen konnte, was dazu beitrug, Divide-and-Conquer als grundlegendes Paradigma zu etablieren.

Key figures

• C. A. R. Hoare
• John von Neumann
• Anatoly Karatsuba
• Volker Strassen

Seminal works

• hoare1962
• cormen2009

Frequently asked questions

Warum ist Mergesort O(n log n)?

Mergesort teilt das Array in zwei Hälften (log n Rekursionsebenen) und führt auf jeder Ebene eine lineare Zusammenführung aller Elemente durch, was die Rekursion T(n) = 2T(n/2) + O(n) ergibt, die das Master-Theorem als O(n log n) löst.

Ist Quicksort ein Divide-and-Conquer-Algorithmus, obwohl er keinen expliziten Kombinationsschritt hat?

Ja. Quicksort leistet seine Hauptarbeit im Teilungsschritt durch Partitionierung um ein Pivotelement; sobald die beiden Partitionen rekursiv sortiert sind, ist keine Kombinationsarbeit erforderlich. Das Paradigma erlaubt, dass der Großteil der Arbeit in jede der drei Phasen fallen kann.