Teile und Herrsche 1 WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-19T08:33:51+00:00. Aktuelle Version

Autoren:

Grundsätzliches

  • Ein großes Problem wird in in kleinere Teilprobleme zerlegt (teile - divide).
  • Teilprobleme werden einzeln gelöst (herrsche - conquer).
  • Zusammensetzen der einzelnen Lösungen zu einer Gesamtlösung.

Beispiele allgemein und aus der Informatik

  • Das Programmingwiki: Das große Problem der Veranstaltung Algorithmen wird aufgeteilt (Themen) und diese zerlegten Teilprobleme von einzelnen (Studenten) bearbeitet und gelöst(Referat). Am Ende werden die einzelnen Lösungen zusammengefügt und bilden die Lehrveranstaltung Algorithmen und Komplexität.
  • Beim Sortieren: Es ist eine Gesamtliste L gegeben mit n Elementen, also L = (e_{1}, e_{2},..., e_{n}), welche nach der göße der Elemente Sortiert werden soll. Man teilt die Liste auf und sortiert die Teillisten nach der Größe und fügt die geortneten Listen in der richtigen Reihenfolge wieder zusammen.

Effizienzbetrachtung von Teile und Herrsche

\begin{array}{ccl} T_B \left( n \right) & = & 3 \cdot T_A \cdot\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+1}{2}\right) \left( \frac{n+1}{2}\right) +d \cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n^2 + 2n + 1}{4}\right) + d \cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n^2}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\ & \leq & \frac{3cn^2}{4} + \frac{6cn}{4} + \frac{3c}{4} + 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) \cdot n + \frac{3}{4} c\\\\ \end{array}