Divide and Conquer
Aus ProgrammingWiki
Mit einfachen Sortieralgorithmen, wie beispielweise Selection Sort, Insertion Sort oder Bubble Sort, ist es möglich, Arrays bzw. Listen zu sortieren. Im worst case beträgt die Zeitkomplexität dieser Verfahren $\mathcal{O}(n^2)$, wobei $n$ für die Anzahl der Feldelemente steht.
Es gibt jedoch Algorithmen, die dies wesentlich schneller können und in einer besseren Komplexitätsklasse liegen. Eines dieser Verfahren ist Merge Sort. Es arbeitet nach dem Muster "Divide and Conquer" (Teile und Herrsche). Ein Teile-und-Herrsche-Algorithmus läuft im Wesentlichen in drei Schritten ab:
- Teilen - Das Problem wird in $a$ gleichartige Subprobleme der Größe $\frac{n}{b}$ geteilt, welche sich einfacher lösen lassen.
- Die Subprobleme werden rekursiv gelöst (d.h. solange geteilt, bis sie so klein sind, dass es sich um triviale Probleme handelt, die sich sehr einfach lösen lassen).
- Die Ergebnisse der Subprobleme werden zusammengeführt (to merge), um dadurch das Ergebnis für das ursprüngliche große Problem zu gewinnen.
Warum müssen die Subprobleme rekursiv gelöst werden? Dies ist notwendig, um eine bessere Zeitkomplexität zu erzielen, wie folgendes Beispiel illustriert:
Wir nehmen an, $a$ sei $3$ (Anzahl der Teilprobleme) und $b$ sei $2$ (Größe dieser Teilprobleme). Ein Verfahren $B$ verwendet zur Bearbeitung der Teilprobleme ein Verfahren $A$. Dann ergibt sich ein Aufwand von $T_B(n)=3\cdot T_A\left(\frac{n}{2}\right)+n$. Wenn $A$ mit quadratischem Aufwand arbeitet, d.h. $T_A\in\mathcal{O}(n^2)$, also $T_A(n)\leq c\cdot n^2$, gilt $T_B(n)\leq 3\cdot c\cdot \frac{n^2}{4}+n\leq \frac{3}{4}\cdot c\cdot n^2+n$. Am Faktor $\frac{3}{4}$ erkennt man, dass tatsächlich eine Effizienzverbesserung von 25% gegenüber dem quadratischen Zeitaufwand eintritt. Für große $n$ fällt das jedoch kaum ins Gewicht. An der Komplexitätsordnung (quadratisches Polynom) ändert das nichts.
Verwendet ein Verfahren $C$ rekursive Teilproblemlösungen, ergibt sich der Aufwand wie folgt: $$ \begin{eqnarray} T_C(n) &=& a\cdot T_C\left(\frac{n}{b}\right)+f(n)\\ &=& 3\cdot T_C\left(\frac{n}{2}\right)+f(n) \end{eqnarray} $$ Nach der Mastermethode, Fall 1, ergibt sich $f(n)=\mathcal{O}(n)=\mathcal{O}(n^{\log_23-\varepsilon})$, wenn $\varepsilon>0: T_C(n)=\mathcal{\Theta}(n^{\log_23})=\mathcal{\Theta}(n^{1.59}).$
Wir erkennen, dass sich gegenüber dem quadratischen Aufwand eine Verbesserung der Aufwandsordnung ergibt, wenn man die Teilprobleme rekursiv löst.
Inhaltsverzeichnis |
Mergesort
Bei Mergesort findet das Teilen (Divide) durch das Zerlegen der Liste in zwei (ungefähr) gleich große Teillisten statt. Bei Listen ungerader Länge entscheidet man sich einfach für eine Zerlegung bei der die Länge der einen Liste eins größer ist als die der anderen.
Die Elementarfälle der Rekursiven sind die leere und einelementige Listen. Diese sind bereits sortiert und können unverändert ausgegeben werden.
$mergesort([]) = []$
$mergesort([a_i]) = [a_i]$
$mergesort([a_0..a_n]) = merge(mergesort([a_0..a_i]) \circ mergesort([a_{i+1}..a_n])$
Der dritte Schritt ist das "Mergen" der sortierten Teillisten. Dies findet statt, indem die jeweils ersten Elemente beider Teillisten miteinander verglichen werden. Die Ergebnisliste besteht dann aus dem kleineren der beiden Elemente gefolgt von den "gemergeten" Restlisten, wobei die eine unverändert bleibt.
$merge([],b_0..b_m) = b_0..b_m$ $merge(a_0..a_n, []) = a_0..a_n$ $merge(a_0..a_n,b_0..b_m) = a_0\circ merge(a_1..a_n,b_0..b_m)$, wenn $a_0 < b_0$ $merge(a_0..a_n,b_0..b_m) = b_0\circ merge(a_0..a_n,b_1..b_m)$, wenn $b_0 < a_0$
Das folgende rekursive Programm setzt diese Beschreibung um.
Natürlich kann man die Verarbeitung dieser rekursiven Prozedur für $mergesort / merge$ analysieren. Die folgende Abb. zeigt das Ergebnis am Beispiel. Der rekursive Ab- und Aufstieg sind sehr gut erkennbar.
Komplexitätsbetrachtung
Die folgende Rekurrenzgleichung ergibt sich unmittelbar aus der rekursiven Natur des Verfahrens. \begin{eqnarray} T(0) &=& 0 \\ T(n) &=& 2 \cdot T \left(\frac{n}{2} \right) + n \end{eqnarray}
Man kann sie mit der Meistermethode rezeptartig lösen. Es greift Fall 2 für $a=2, b=2$ und $f(n)=n$.
$$\Theta \left(n^{\log_{b}a} \right) = \Theta \left(n^{\log_{2}2} \right) = \Theta(n)$$ $$f(n) \in \Theta(n)$$ $$n \in \Theta(n)$$
Damit ergibt sich:
$$ \begin{align} T(n) & \in \Theta \left(n^{\log_{b}a}\log_{2}n \right) \\ & \in \Theta \left(n^{\log_{2}2}\log_{2}n \right) \\ & \in \Theta \left(n\log n \right) \end{align} $$
Der Zeitaufwand für Mergesort liegt in $\mathcal{O}(n\log{n})$ (in all cases) und ist damit eines der besten Sortierverfahren überhaupt.
Zu beachten ist allerdings, dass Mergesort kein in-place-Verfahren ist und deshalb das Ergebnis, also die sortierte Gesamtliste in ein separates Feld (um)speichert.
Mergesort in nichtrekursiver Implementierung eignet sich als externes Sortierverfahren. D.h., es brauchen nicht alle Daten gleichzeitig im Hauptspeicher vorzuliegen, sondern zum Teil in einer externen Datei. Dann werden drei Dateien verwendet und mit Mergesort verarbeitet.
Quicksort
Das Sortierverfahren Quicksort (1960 von C. Antony R. Hoare) zerlegt die Gesamtliste $ls$ der zu sortierenden Elemente so in genau zwei Teillisten $lls$ (linke Teilliste) und $rls$ (rechte Teilliste) so, dass alle Elemente von $lls$/$rls$ kleiner/größer als ein Vergleichselement $v$ sind. Dieses Vergleichselement wird Pivotelement genannt. Es wird der zu sortierenden Gesamtliste an beliebiger Stelle entnommen: Eine Möglichkeit ist es, immer das erste oder letzte Element der Liste zu nehmen. Eine weitere gängige Methode ist es, das Pivotlement zufällig auszuwählen, welche Auswirkungen dies auf die average- und worst-case Zeitkomplexität hat, wird im Kapital der randomisierten Algorithmen betrachtet.
Nachdem die beiden Teillisten rekursiv sortiert wurden (zu $slls$ und $srls$), brauchen sie nur noch verkettet zu werden: $slls\circ v\circ srls$, wobei $v$ zwischen ihnen steht. Da das Pivotelement $v$ der Gesamtliste $ls$ entnommen wurde, ist sichergestellt, dass beide Teillisten kürzer sind als $ls$. Dies gilt auch, wenn eine der beiden Listen leer ist.
Die Basisfälle sind die gleichen wie bei Mergesort: Ist die Liste leer oder enthält sie nur ein Element, so ist praktisch nichts zu tun und die Liste kann unverändert zurückgegeben werden.
Das Zusammenführen, also der dritte Schritt eines Divide-and-Conquer-Algorithmus, ist bei Quicksort trivial, da die Teilarrays in ihrer vorhandenen Reihenfolge lediglich verbunden werden müssen, natürlich mit dem Pivotelement dazwischen.
Das folgende Programm setzt das beschriebene Verfahren adäquat um.
Die Implementierung von Quicksort wird im Allgemeinen als In-place-Verfahren vorgenommen. Zwei Zeiger bewegen sich aufeinander zu -- einer von links und einer von rechts über die Gesamtliste. Zugehörige Vergleiche führen dazu, dass Platzwechsel stattfinden. Eine bildhafte Beschreibung dieses In-place-Verfahrens ist durch "burns the candle at both ends" gegeben. Das folgende Programm bildet dies ab.
Komplexitätsbetrachtung
Best case
Der best-case tritt ein, wenn das Pivotelement die Listen immer in zwei gleich große Teillisten teilt.
$$ \begin{align} T(0) & = 0 \\ T(n) & = 2 \cdot T \left(\frac{n}{2} \right) + n \end{align}$$
Dies kann äquivalent zu Mergesort mit der Meistermethode gelöst werden und man erhält eine Zeitkomplexität von $\mathcal{O}(n\log{n})$ im best-case (s. CW-Buch). Dies gilt übrigens auch für den average-case.
Worst case
Der worst case liegt vor, wenn das Pivotelement die Liste immer in eine leere Teilliste und eine Teilliste der Größe $n-1$ teilt. Dies ist beispielsweise der Fall, wenn man immer das erste Element als Pivot wählt und eine bereits sortierte Liste sortiert. Das ist kein Schreibfehler: Das Verfahren hat die schlechteste Effizienz, wenn die zu sortierende Liste bereits sortiert ist. Dann erhält man in jedem Schritt Teilbäume der Länge $|ls|-1$ und $0$.
$$ \begin{align} T(0) & = 0 \\ T(n) & = T(0) + T(n-1) + n \end{align}$$
Dies kann mit Hilfe der Iterationsmethode gelöst werden.
$$ \begin{align} T(n) & = T(0) + T(n-1) + n \\ & = T(0) + (T(0) + T(n-2) + n-1) + n \\ & = 2T(0)+ T(n-2) + 2n-1 \\ & = 2T(0)+ (T(0) + T(n-3) + n-2) + 2n-1 \\ & = 3T(0)+ T(n-3) + 3n-3 \\ & = 3T(0)+ (T(0) + T(n-4) + n-3) + 3n-3 \\ & = 4T(0)+ T(n-4) + 4n-6\\ & \vdots \\ T(n) & = iT(0) + T(n-i) + in - \sum_{k=0}^{i-1}k \end{align} $$ für $i=1,2,3,\ldots,n$. Wenn $i=n$ gilt:
$$ \begin{align} T(n) & = nT(0)+T(n-n)+n^2-\sum_{k=0}^{n-1}k \\ & = n^2 + \frac{n-1}{2}n \\ & = \frac{n^2+n}{2} \end{align} $$
Ergebnis: Quicksort im worst case liegt in $\mathcal{O}(n^2)$
Der Zeitaufwand beträgt also $\mathcal{O}(n^2)$ im worst-case. Wenn man aufgrund des Anwendungskontextes vermuten muss, dass die zu sortierende Liste bereits sortiert oder fast sortiert ist, kann die betrachtete Liste "durcheinander gewirbelt" werden:
Konvexe Hülle
Auch im Bereich der geometrischen Algorithmen spielen Teile-und-Herrsche-Verfahren eine große Rolle.
Die konvexe Hülle einer Menge $P$ von Punkten des $n$-dimensionalen euklidischen Raums ist das konvexe $n$-Polytop, das alle Punkte aus $P$ enthält und ein minimales Volumen bzw. minimalen Flächeninhalt besitzt. Äquivalent handelt es sich dabei um ein beliebiges $n$-Polytop mit minimaler Außenfläche bzw. minimalem Umfang.
In der Ebene, also im 2-dimensionalen euklidischen Raum, handelt es sich dabei um das Polygon mit minimalen Umfang, das alle Punkte aus $P$ enthält.
Eine Menge $M$ heißt konvex, wenn für alle Punkte $p,q\in M$ gilt, dass sämtliche Punkte, die auf der Strecke pq liegen, ebenfalls in $M$ ist.
Man kann es sich so vorstellen, als würde man ein Gummiband um die Punkte spannen.
Ziel ist es nun einen Algorithmus zu entwickeln, der das Problem, die konvexe Hülle einer beliebigen Menge gegebener Punkte $P$ zu finden, möglichst effizient löst. Zur Vereinfachung nehmen wir an, dass keine 3 Punkte auf einer Linie liegen und dass keine 2 Punkte dieselbe x-Koordinate haben.
Brute-Force - Ansatz
Man kann sich jede Verbindung zwischen zwei Punkten als ein Segment vorstellen. Die konvexe Hülle besteht dabei aus einer Menge $S$ solcher Segmente. Diese Menge $S$ ist gleichzeitig eine Teilmenge aller möglichen Segmente der $n$-Punkte. Anhand dieser Tatsache kann man die konvexe Hülle finden, indem man alle möglichen Segmente bildet und bei jedem einzelnen Segment prüft, ob es zur konvexe Hülle gehört oder nicht. Alle Segmente, bei denen dieser Test positiv ausfällt, bilden zusammen die konvexe Hülle. Ein Segment gehört genau dann zur konvexe Hülle, wenn alle Punkte $P$ auf genau einer Seite der Geraden liegen, welche durch das Segment geht.
Für $n$ Punkte gibt es $\binom{n}{2}$ Punktepaare. Folglich beträgt die Anzahl der zu prüfenden Segmente ebenso $\binom{n}{2}$: $$\sum_{i=0}^{n-1}i =\frac{n (n-1)}{2} = \binom{n}{2} \in \mathcal{O}(n^2)$$
Für jedes der $\binom{n}{2}$ Segmente muss nun für jeden der $n-2$ Punkte geprüft werden, ob sie alle auf ein und derselben Seite liegen. Dies ergibt einen Aufwand von $\mathcal{O}(n^2)\cdot\mathcal{O}(n)=\mathcal{O}(n^3)$. Das ist ein beachtlicher Aufwand. Mit einem Teile-und-herrsche-Verfahren sollte das besser möglich sein.
Divide and Conquer - Ansatz
Der erste Schritt ist das Teilen. Das Teilen findet statt, indem zunächst alle Punkte in $P$ entlang einer beispielsweise zur y-Achse parallelen Geraden eingeordnet werden, was dazu führt, dass die Punkte nach ihren x-Koordinaten sortiert werden. Wenn wir dafür Merge-Sort verwenden, kostet dies $\mathcal{O}(n \log n) $. Nach dem Sortieren können die Punkte aus $P$ in zwei gleich große Mengen geteilt werden, wodurch nun zwei Teilprobleme entstehen, welche rekursiv gelöst werden.
Die Basisfälle bilden Mengen, die aus genau zwei Punkten bestehen. ($|P|=0, |P|=1$ sind nicht erlaubt.) In diesem Fall ist die konvexe Hülle die Strecke zwischen den zwei Punkten.
Hat man die Teilprobleme gelöst, so ist es notwendig, die beiden konvexen Hüllen der Teilprobleme zur konvexen Hülle des Gesamtproblems zusammenzuführen (Merge). Der naive Ansatz wäre es, alle Segmente zwischen einem Punkt aus der linken Hälfte und einem Punkt aus der rechten Hälfte durchzugehen, und das höchste und tiefste Segment, als das Segment, welche die beiden Teil-konvexen Hüllen verbindet, zu wählen.
Da es aber auf beiden Seiten jeweils $\frac{n}{2}$ Punkte gibt, müssten $\frac{n^2}{4}$, also $\mathcal{O}(n^2)$ Segmente überprüft werden. Damit ist die Merge-Operation so aufwendig, das kein Gewinn in der Komplexitätsklasse gegenüber dem ursprünglichen Brute-Froce-Ansatz entsteht.
Wir brauchen also ein anderes Verfahren für die Merge-Operation. Hierfür wird zunächst jeweils ein Punkt aus beiden Mengen genommen, beispielsweise $a_1$ und $b_1$. Der Schnittpunkt mit der Geraden in der Mitte wird ermittelt. Nun besteht das Ziel darin, ein Segment zu finden, welches einen höher liegenden Schnittpunkt hat (größerer y-Wert), da das höchste und tiefste Segment gesucht werden.
Dieser Vorgang geschieht, indem zunächst auf der rechten Seite der im Uhrzeigersinn nächste Punkt gewählt wird. Der Schnittpunkt mit der Geraden des neuen Segments wird verglichen, ist er nicht höher als der bisherige Wert, so braucht man nicht weiter im Uhrzeigersinn zu gehen und hat den Punkt der rechten Hälfte, welcher zum oberen Segment gehört, bereits gefunden. Ist er hingegen höher, so muss auf der linken Seite gegen den Uhrzeigersinn gegangen werden, und das daraus entstandene Segment mit dem bisherigen Spitzenreiter verglichen werden.
Dieser Vorgang des abwechselnd auf der linken Seite gegen den Uhrzeigersinn und auf der rechten Seite im Uhrzeigersinn zu gehen, wird solange weitergeführt, bis auf der jeweiligen Seite kein höher liegender Schnittpunkt mit der Geraden erreicht wird.
Um das untere Segment zu finden, muss das Segment mit dem niedrigsten Schnittpunkt gefunden werden und entsprechend auf der linken Seite im Uhrzeigersinn und auf der rechten Seite entgegen des Uhrzeigersinns gegangen werden.
Hieraus ergibt sich, dass das Segment $(a_3, b_2)$ das gesuchte ist.
Das Teile-und-Herrsche-Verfahren erfordert also durch die Halbierungen der jeweiligen Punktmengen und deren Hüllenbestimmung einen Aufwand in $\mathcal{O}(\log n)$. Für das Merging der linken und rechten Hüllen ist ein Aufwand in $\mathcal{O}(n)$ erforderlich. Dies ergibt insgesamt $\mathcal{O}(n\log n)$, s. auch GeeksForGeeks.
