Teile und Herrsche 1 WS13-14
Aus ProgrammingWiki
Inhaltsverzeichnis |
Vorbetrachtungen
Grundsätzliches
- Ein großes Problem wird in kleinere Teilprobleme zerlegt (teilen - divide)
- Teilprobleme werden einzeln rekursiv gelöst (herrschen - conquer)
- Zusammensetzen der einzelnen Lösungen zu einer Gesamtlösung
Beispiele allgemein und aus der Informatik
- Das Programmingwiki: Das große Problem der Veranstaltung Algorithmen wird aufgeteilt (Themen) und diese zerlegten Teilprobleme von einzelnen Studenten bearbeitet und gelöst (Referat). Am Ende werden die einzelnen Lösungen zusammengefügt und bilden die Lehrveranstaltung Algorithmen und Komplexität.
- Beim Sortieren: Es ist eine Gesamtliste L gegeben mit n Elementen, also $L = (e_{0},\ e_{1},..., e_{n})$, welche nach der Größe der Elemente sortiert werden soll. Man teilt die Liste auf, sortiert die Teillisten der Größe nach und fügt die geordneten Listen in der richtigen Reihenfolge wieder zusammen.
Effizienzbetrachtung von Teile und Herrsche
Es wird erhofft, dass diese Technik effizienter ist als das Lösen des Gesamtproblems ohne es zu zerlegen.
Angenommen, ein Algorithmus $\mathcal{A}$ löst das Problem in $\mathcal{O}\left(n^{2}\right)$, d.h. mit $\mathit{T}_{\mathcal{A}}\left(n\right)\leq c\cdot n$. Für den Gesamtaufwand $\mathit{T}_{\mathcal{B}}$ eines Algorithmus $\mathcal{B}$, der beispielsweise drei dieser Probleme der Größe $\frac{n}{2}$ mittels Prozedur $\mathcal{A}$ bearbeitet, um die Teillösungen anschließend mit dem Aufwand in $\mathcal{O}\left(n\right)$ zusammenzufügen, gilt damit:
\begin{align} \begin{array}{rcl} T_{B} \left( n \right) & = & 3 \cdot T_{A} \cdot\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+1}{2}\right) \left( \frac{n+1}{2}\right) + d \cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n^{2} + 2n + 1}{4}\right) + d \cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n^{2}}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\ & \leq & \frac{3cn^{2}}{4} + \frac{6cn}{4} + \frac{3c}{4} + d \cdot n\\\\ & \leq & \frac{3}{4}cn^{2} + \frac{3}{2}cn + \frac{3}{4}c + d \cdot n\\\\ & \leq & \frac{3}{4}cn^{2} + \left(\frac{3}{2}c + d\right) \cdot n + \frac{3}{4} c\\\\ \end{array} \end{align}
Man erkennt an den führenden Summanden, dass sich tatsächlich eine Effizienzsteigerung von ca. 25% ergibt. Allerdings liegt noch immer ein quadratischer Aufwand mit $\mathcal{O}\left(n^{2}\right)$ vor. Daher betrachten wir nun einen Algorithmus $\mathcal{C}$, welcher das Problem auf rekursive Art löst.
\begin{align} \mathit{T}_{\mathcal{C}}\left(n\right) = \begin{cases} \mathit{T}_{\mathcal{A}}\left(n\right), \mbox{$wenn$}\ n\leq n_{0} \\ \mathit{3\ T}_{\mathcal{C}}\left(\dfrac{n}{2}\right), \mbox{$sonst$}\end{cases} \end{align}
Nach dem Lösen dieser Formel kommen wir zu dem Ergebnis $\mathit{T}_{\mathcal{C}}\left(n\right)=\mathcal{O}\left(n^{1.59}\right)$.
Quicksort
Der Quicksort-Algorithmus wurde 1962 von C.A.O. Hoare angegeben. Der Grundgedanke ist, eine Liste
$L = (e_{0}, e_{1},\dots, e_{n})$
in zwei Teillisten zu zerlegen, eine linke Teilliste $TL$ und eine rechte Teilliste $TR$. Diese Listen werden durch Vergleich mit einem Pivotelment (Vergleichselement) $v$ gebildet. Dabei muss $\mathit{v} \in L$ gelten. Es wird verabredet, dass alle Elemente von $L$ paarweise verschieden sind.
Durch $m \neq n$ gilt $e_{m} \neq e_{n}$.
Dies ist zwar nicht erforderlich, aber im Allgemeinen sinnvoll, da es sich normalerweise um Schlüssel zur Identifikation von Datensätzen handelt. Weiterhin wird verabredet, dass es sich um eine Liste mit natürlichen Zahlen handelt. Eine weitere Festlegung ist es, das am weitesten links stehende Element aus $L$ als $v$ zu nehmen, das bedeutet $\mathit{v} = e_{0}$.
Die sortierte Gesamtliste $L_{sortiert}$ entsteht durch zusammenführung der Teilliste $TL_{sortiert}$, dem Pivotelement $\mathit{v}$ und der Teilliste $TR_{sortiert}$ in dieser Reihenfolge. Die Abarbeitung der Teillisten findet dabei rekursiv statt.
Die zwei Elementarfälle: Ist $L$ leer oder hat nur ein einzelnes Element, dann ist $L$ = $L_{sortiert}$. Bei der Teilung der Liste $L$ in $TL$ und $TR$ entstehen wieder Listen die mindestens $|L-1|$ Elemente enthalten, da $v$ entfernt wurde. Es wird nach endlich vielen Zerlegungen einer der Elementarfälle erreicht.
Funktionaler Aufbau
Hierbei entstehen zwei Teillisten. Um eine sortierte Liste zu bekommen, wird noch eine weitere Prozedur benötigt:
Effizienz von Quicksort
Best Case
Quicksort arbeitet am effektivsten, wenn die zu sortierenden Teillisten etwa gleich lang sind.
\begin{align} \mathit{T}\left(0\right) &= 0\notag\\ \mathit{T}\left(n\right) &= 2 \cdot \mathit{T}\left(\frac{n}{2}\right) + c \cdot n\notag \end{align}
Dabei kommen wir auf einen Aufwand von $\mathit{T}\left(n\right)= \mathcal{O}\left(n \log_{2} n\right)$. Zur Lösung der Rekursionsgleichung wird die Meistermethode verwendet. Dies ist naheliegend, da die in der allgemeinen Form
\begin{align} \mathit{T}\left(n\right) &= a \cdot \mathit{T}\left(\frac{n}{c}\right) + f \left(n\right) \end{align}
vorkommenden Variablen eine ganz bestimmte Bedeutung haben:
- Anzahl der Teilprobleme: $a \dots$
- Größe des Teilproblems, wobei die Zerlegung immer "aufgehen" möge: $\frac{n}{c} \dots$
Worst Case
Dieser Fall ist etwas sonderbar, da er dann eintritt, wenn bereits eine vollständig sortierte Liste vorliegt und das Ergebnis dadurch schon entsprechend vorhanden ist.
Die Rekursionsgleichung...
\begin{align} \mathit{T}\left(0\right) &= 0\notag\\ \mathit{T}\left(0\right) &= \underbrace{\mathit{T}\left(0\right)}_\text{= 0} + \mathit{T}\left(n - 1\right) + c \cdot n\notag \end{align}
...kann iterativ gelöst werden...
\begin{align} \mathit{T}\left(n - 1\right) &= \mathit{T}\left(n - 2\right) + c \left(n - 1\right)\notag\\ \mathit{T}\left(n - 2\right) &= \mathit{T}\left(n - 3\right) + c \left(n - 2\right)\notag\\\\ \vdots \\\\ \mathit{T}\underbrace{\left(\ n - k \ \right)}_{\text{ = 1 $\curvearrowright$ k = n - 1}} &= \mathit{T}\left(0\right) + c \left(n - k\right)\notag\\ \end{align}
...und nach einsetzen des Ausdruckes in die Klammer der allgemeinen Form...
\begin{align} \begin{array}{rcl} T(n) &=& c \cdot \sum\limits_{k=0}^{n-1} \left(n-k\right)\\\\ &=& c\cdot\left(\sum\limits_{k=0}^{n-1} n - \sum\limits_{k=0}^{n-1} k\right)\\\\ &=& c\cdot\left(n^2 - \frac {n-1}{2}\left(\left(n-1\right)+1\right)\right)\\\\ &=& c\cdot\left(n^2 - \frac {n^2 -n}{2}\right)\\\\ &=& c\cdot\left(\frac {n^2} {2} + \frac {n} {2}\right) \\\\\\ T(n) &=& \mathcal{O}\left(n^2\right)\\\\ \end{array}\notag \end{align}
...kann abgelesen werden, dass hier ein quadratischer Aufwand vorliegt.
Average Case
Hier wird davon ausgegangen, dass jede der $\mathit{n}$ Teillistenlängen mit der gleichen Wahrscheinlichkeit auftritt, nämlich $\dfrac{1}{n}$.
Somit gilt:
\begin{align} \begin{array}{rcl} T(i) = T\left(n-i-1\right) = \frac {1}{n} \cdot \sum\limits_{j=0}^{n-1} T\left( j\right)\\\\ T(n) = \underbrace{T\left(i\right)}_{linke\ Teilliste} + \underbrace{T\left(n-i-1\right)}_{rechte\ Teilliste} + \underbrace{c \cdot n}_{Teillistenbildung}\\\\ \end{array} \end{align}
Eingesetzt ergibt sich folgendes:
\begin{align} \begin{array}{rcl} T\left(n\right) &=& \frac {2}{n} \sum\limits_{j=0}^{n-1} \ T\ \left(j\right) + c \cdot n\\\\ \end{array} \end{align}
Um die Summe zu beseitigen, werden Differenzen gebildet:
\begin{align} \begin{array}{rcl} nT\left(n\right) &=& 2 \ \sum\limits_{j=0}^{n-1} \ T\ \left(j\right) + c \cdot n^{2} \\\\ \left(n-1\right)T\left(n-1\right) &=& 2 \sum\limits_{j=0}^{n-2}\ T\ \left(j\right) + c \cdot \left(n-1\right)^2 \mid \text{für} \ n:=n - 1; -\\\\ \\\\ nT\left(n\right) - \left(n-1\right)T\ \left(n-1\right) &=& 2T\ \left(n-1\right) + 2cn - c \mid -c\ \text{entfällt für}\ n \rightarrow \infty\\\\ \frac{T\left(n\right)}{n+1} &=& \frac{T\left(n-1\right)}{n} + \frac{2c}{n+1}\\\\ \frac {T\left(n-1\right)}{n} &=& \frac{T\left(n-2\right)}{n-1} + \frac{2c}{n}\\\\ \vdots & & \vdots\\\\ \frac{T\left(2\right)}{3} &=& \frac{T\left(1\right)}{2} + \frac{2c}{3}\\\\ \\\\ \frac{T\left(n\right)}{n+1} &=& \underbrace{\frac{T\left(1\right)}{2}}_{=0, da\ T\left(1\right) =0} + 2 \sum\limits_{i=3}^{n+1} \frac{1}{i}\\\\ \end{array} \end{align}
Bei der Benutzung der bekannten Schranken $\frac {\lfloor log_{2} \ n \rfloor +1}{2} < \mathit{H}_{n} \leq \lfloor log_{2} \ n \rfloor +1$ für die harmonischen Zahlen $\mathit{H}_{n} = \sum\limits_{k=1}^{n} \frac{1}{k}$ ergibt sich:
\begin{align} \frac {T\left(n\right)}{n+1} = \mathcal{O} \left(log_{2} \ n\right)\curvearrowright T\left(n\right) = \mathcal {O} \left(n \cdot log_{2} \ n\right) \end{align}
Die Effizienz von Quicksort in allen drei Fällen:
\begin{align} \begin{array}{|c|c|} \hline best \ case & \Theta\left(n \ \log_{2} n\right) \\ \hline average \ case & \mathcal{O}\left(n \ \log_{2} n\right) \\ \hline worst \ case & \Omega\left(n^{2}\right) \\ \hline \end{array} \end{align}
Mergesort
Mergesort und Quicksort sind eng miteinander verwandt. "Merge" kann mit "Zusammenführen" übersetzt werden. Eine zu sortierende Gesamtliste
- $L = \left(Le_{0}, Le_{1}, Le_{2}, \dots , Le_{n}, Re_{0}, Re_{1}, Re_{2}, \dots , Re_{m}\right)$
wird in zwei etwa gleich große Teillisten
- $TL = \left(Le_{0}, Le_{1}, Le_{2}, \dots , Le_{n}\right)$ und TR$= \left(Re_{0}, Re_{1}, Re_{2}, \dots , Re_{m}\right)$
geteilt.
- $n = |L|\div 2 = m\div 2$.
Es wird kein Vergleich oder Vorsortierung vorgenommen. Das $\div$-Zeichen steht für eine ganzzahlige Division.
Es gilt entweder $m = 2n$ oder $m = 2n +1$.
Dann werden die beiden Teillisten rekursiv, das bedeutet mit Mergesort, sortiert. Die Elementarfälle sind die selben wie bei Quicksort. Der dritte Schritt besteht darin, die sortierten Teillisten mit einem Reißverschlusssystem wieder zusammenzufügen.
Die jeweiligen führenden Teilelemente $Le_{i}$ und $Re_{j}$ gelangen an ein "Tor". Wenn $Le_{i} < Re_{j}$ gilt, wird $Le_{i}$ durchgelassen und nimmt die nächste freie Position in der Gesamtliste ein. $Re_{j}$ wird anschließend mit $Le_{i+1}$ verglichen. Ansonsten natürlich umgekehrt.
Effizienz von Mergesort
Um Mergesort zu analysieren, ist die Rekursionsgleichung
- $\mathcal{\mathit{T}\left(n\right) = 2\cdot \mathit{T}\left(\frac{n}{2}\right)+\Theta\left(n\right)}$
mit
- $\mathcal{T(0)=0}$
und
- $\mathcal{T(1)=0}$
zu lösen. Es wird vereinfacht angenommen, dass die Anzahl der Elemente $n$ eine Zweierpotenz ist.
Das Ergebnis lautet für alle auftretenden Fälle, also best-, worst- und average case:
- $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log_{2} n\right)$
Das ist kein Zufall, da Quicksort und Mergesort eng miteinander verwandt sind, ist dies auch das Ergebnis für den best case bei Quicksort.
Internes Sortierverfahren
Die bisherigen Implementierungen von Quick- bzw. Mergesort verstoßen gegen eine wichtige Forderung, welche auch für die zwei genannten Verfahren gilt. Es handelt sich um interne Sortierverfahren. Das bedeutet, es darf dem Vorgabefeld gegenüber kein zusätzlicher Speicher benutzt werden. Die Prozedur Teile gibt aber zwei Listen zurück, die einen neuen Speicherplatz benutzen. Es muss also der Erzeugung der Teillisten besondere Aufmerksamkeit gegeben werden.
Hier finden Sie eine genaue Informationen zum internen Sortierverfahren.
Beschreibung internes Sortierverfahren
Übungsaufgaben
1. Implementieren Sie den Quicksort-Algorithmus in einer Programmiersprache ihrer Wahl, sortieren Sie eine vorsortierte Liste mit 3000 Elementen und messen Sie die Zeit.
2. Verwenden Sie nun eine unsortierte Liste und wiederholen Sie die Zeitmessung.
3. Implementieren Sie in Racket den Mergesort-Algorithmus. Die zu verwendenden Teilprozeduren werden für Sie im entsprechenden Abschnitt freigeschaltet.
Quellen
[1] Wagenknecht, Chr.: Algorithmen und Komplexität, Leipzig: Fachbuchverlag, 2003.
