Teile und Herrsche 1 SS10
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 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.
-
\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}
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