AuK/Teile und Herrsche 1 SS09

Wiki-Quelltext dieser Seite.

== 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<br />
# in Teilprobleme zerlegt wird
# die Teilprobleme gelöst werden
# die Teilprobleme zu einer Lösung vereint werden.<br />
<br />
Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:<br />
Wir nehmen an, dass ein bestimmter Algorithmus <math>A</math> ein Problem mit <math>O\left(n^2\right)</math>, also <math>T_A\leq c \cdot n^2</math>, löst. Für ein Algorithmus <math>B</math>, der drei dieser Probleme der Größe <math>\frac{n}{2}</math> mit <math>A</math> bearbeitet und mit <math>O\left( n \right) </math> zusammenfügt gilt:<br /><br />
<math>
\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}
</math><br /><br />
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.<br /><br />
Um dies zu erreichen nehmen wir an, das wir einen Algorithmus <math>C</math> haben, der die Teilprobleme rekursiv löst. Das bedeutet, dass der Algorithmus auch die Teilprobleme löst, einzig die Basisfälle <math>n \leq n_0</math> werden von dem Algorithmus <math>A</math> übernommen. Das bedeutet:<br /><br />
<math>T_C(n)=\begin{cases}T_A(n), & wenn n\leq n_0 \\ 3T_C(\frac{n}{2}), & sonst\end{cases}</math><br /><br />
Die Anwendung der Meistermethode ergibt:<br />
<math>T_C(n)=O(n^{1,59})</math>.<br /><br />
Anhand der Ergebnisses kann man sehen, das "Teile und Herrsche" aus Effizienzgründen immer mit Rekursion arbeitet.
== Quicksort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung ===
=== Effizienz von Quicksort ===
=== Interne Suchberfahren ===


== Mergesort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung mit Multiple-value-context ===
=== Effizienzanalysen ===