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 rekursiven Aufruf (''conquer'')
# Teillösungen zusammenführen zu der Gesamtlösung (''konkatenieren'')

::<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 />

==Das schnelle Sortieren==
<math>sqrt(5 + 5)</math>
quicksort

==Sortieren durch mischen==

mergesort

==Vergleich Quicksort und Mergesort==

==Übungen==

==Links und Quellen==