Teile und Herrsche 1 SS09
Inhaltsverzeichnis |
Die Idee
"Teile und Herrsche" (engl. "divide and conquer" bzw. lat. "divide et impera") beschreibt ein Verfahren zur Lösung von Problemen, wobei das Problem
- in Teilprobleme zerlegt wird
- die Teilprobleme gelöst werden
- die Teilprobleme zu einer Lösung vereint werden.
Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:
Wir nehmen an, dass ein bestimmter Algorithmus A ein Problem mit O\left(n^2\right), also T_A\leq c \cdot n^2, löst. Für ein Algorithmus B, der drei dieser Probleme der Größe \frac{n}{2} mit A bearbeitet und mit O\left( n \right) zusammenfügt gilt:
\begin{array}{ccl}
T_B & = & 3T_A\left(\left\lceil \frac{n}{2}\right\rceil\right)+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right)^2+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n}{2} + \frac{1}{2} \right)^2+d \cdot c\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^2}{4}+2\frac{n}{4}+\frac{1}{4} \right)+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\frac{3}{2}nc+\frac{3}{4}c+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\left(\frac{3}{2}c+d\right)n+\frac{3}{4}c
\end{array}
Es tritt also eine Effizienzverbesserung um 25% auf. Da der Aufwand allerdings quadratisch ist, kann man bei großen n den Faktor vernachlässigen. Es ist also offensichtlich das eine Effizienzverbesserung nur auftritt, wenn der Exponent kleiner wird.
Um dies zu erreichen nehmen wir an, das wir einen Algorithmus C haben, der die Teilprobleme rekursiv löst. Das bedeutet, dass der Algorithmus auch die Teilprobleme löst, einzig die Basisfälle n \leq n_0 werden von dem Algorithmus A übernommen. Das bedeutet:
T_C(n)=\begin{cases}T_A(n), & wenn n\leq n_0 \\ 3T_C(\frac{n}{2}), & sonst\end{cases}
Die Anwendung der Meistermethode ergibt:
T_C(n)=O(n^{1,59}).
Anhand der Ergebnisses kann man sehen, das "Teile und Herrsche" aus Effizienzgründen immer mit Rekursion arbeitet.
Quicksort
Das Verfahren
Quicksort wurde 1962 von C.A.O. Hoare entwickelt und ist ein Algotithmus, der nach dem "Teile und Herrsche" - Verfahren arbeitet.
Die Idee von Quicksort besteht darin, jedes Listenelement mit einem Vergleichselement (Pivotelement) zu vergleichen und, je nachdem ob es kleiner oder größer ist, in eine linke oder eine rechte Liste einzufügen. Auf die beiden Teillisten wird jetzt wieder Quiksort angewandt (rekursive Verarbeitung aus Effizienzgründen) und anschließend werden die beiden Listen und das Pivotelement nach folgender Vorschrift zusammengefügt:
- linke Liste
- Pivotelement
- rechte Liste.
Damit die rekursive Abarbeitung terminiert, müssen noch zwei Basisfälle vorgesehen werden:
- die Gesamtliste ist leer
- die Gesamtliste besteht aus nur einem Element.
In beiden Fällen ist die Liste schon sortiert.
Funktionsorientierte Beschreibung
Die linke bzw. rechte Teilliste wird in dem folgendem Beispiel von den Hilfsfunktionen linke_liste und rechte_liste erzeugt. Das Pivotelement wird durch die Funktion trennelement ermittelt. Die Teillisten werden in der Hauptfunktion durch rekusrive Aufrufe von Quicksort ebenfalls sortiert und danach zu einer Erbnisliste zusammengefügt.
<eval>
(quicksort_trad '(9 129 4 2548 4 2395 9 82 4 21 5 2 1 4 6 3 5 67))
</eval>
Da die beiden Funktion linke_liste und rechte_liste sich nur durch das Relationszeichen unterscheiden könnte man die Teillistenbildung auch in einer Prozedur abhandeln. Nun besteht hier das Problem, dass in der funktionsorientierten Programmierung Prozeduren nur ein Funktionswert (Rückgabewert) besitzen. Es ist allerdings möglich, die beiden Teillisten wieder in einer Liste zu verpacken. Da die Teillisten aber bei den rekursiven Aufruf wieder benötigt werden, müsste die entsprechende Teilliste vor Aufruf von Quicksort wieder ausgepackt werden. Man sieht, dass dies ein ständiges verpacken und entpacken bedeutet.
Die Lösung liegt im Multiple-value-context. Dabei können Funktionen mehrere Funktionswerte besitzen, die an andere Funktionen weitergegeben und weiterverarbeitet werden können.