AuK/Teile und Herrsche 1 SS10

Wiki-Quelltext dieser Seite.

Autoren:
* Raffael Thomas Lang ([mailto:siralang@stud.hs-zigr.de siralang@stud.hs-zigr.de])
* Sebastian Kramer ([mailto:sisekram@stud.hs-zigr.de sisekram@stud.hs-zigr.de])

== Was ist überhaupt Divide and Conquer? ==

DaC (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera". Es beschreibt folgendes Vorgehen bei Problemen:

# zerteilen des Problems in Teilprobleme (''divide'')
# lösen der einzelnen Teilprobleme, mittels rekursiver Programmierung (''conquer'')
# Teillösungen zusammenführen zu der Gesamtlösung (''konkatenieren'')

=== Ziel ===
Ziel dieser Methode eine Effiziensverbesserung zu erreichen. Der Lösungsaufwand soll minimiert werden durch die Zerlegung des Hauptproblems.

===Effizienz von DaC=== 
In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand eines Algorithmus aus den Teilproblemen multipliziert mit der Größe der Teilprobleme plus den Aufwand ergibt.

::<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 n\\\\
		& \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}cn+\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 eine Effiziensverbesserung von 25% auf, jedoch ist zubeachten das immer ein rekursiver Aufruf enthalten sein muss.

==Das schnelle Sortieren==
Beispielsweise wird beim Sortieren mit dem Quicksortalg. die sortierte ergebnisliste aus kleinen jeweils für sich sortierten teillisten zusammengesetzt.

==Sortieren durch mischen==

mergesort

==Vergleich Quicksort und Mergesort==

==Übungen==

==Links und Quellen==