Teile und Herrsche 1 SS09
Inhaltsverzeichnis |
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
- in Teilprobleme zerlegt wird
- die Teilprobleme gelöst werden
- die Teilprobleme zu einer Lösung vereint werden.
Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:
Wir nehmen an, dass ein bestimmter Algorithmus A ein Problem mit O\left(n^2\right), also T_A\leq c \cdot n^2, löst. Für ein Algorithmus B, der drei dieser Probleme der Größe \frac{n}{2} mit A bearbeitet und mit O\left( n \right) zusammenfügt gilt:
\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}
Es tritt also eine Effizienzverbesserung um 25% auf. Da der Aufwand allerdings quadratisch ist, kann man bei großen n den Faktor vernachlässigen.