Teile und Herrsche 1 SS10
Aus ProgrammingWiki
Archivierte Version vom 2010-04-06T12:56:35+00:00. Aktuelle Version
Inhaltsverzeichnis |
Autoren:
- Raffael Thomas Lang (siralang@stud.hs-zigr.de)
- Sebastian Kramer (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)
In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand eines Algorithmus aus den Teilproblemen * der Größe der Teilprobleme + den Aufwand ergibt.
-
\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}
-
\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}
Das schnelle Sortieren
sqrt(5 + 5)quicksort
Sortieren durch mischen
mergesort