AuK/Teile und Herrsche 1 SS09

Wiki-Quelltext dieser Seite.

== 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<br />
# in Teilprobleme zerlegt wird
# die Teilprobleme gelöst werden
# die Teilprobleme zu einer Lösung vereint werden.<br />
<br />
Die folgende Rechnung dient als Beweis, das eine Effizienzverbesserung auftritt:<br />
Wir nehmen an, dass ein bestimmter Algorithmus <math>A</math> ein Problem mit <math>O\left(n^2\right)</math>, also <math>T_A\leq c \cdot n^2</math>, löst.

== Quicksort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung ===
=== Effizienz von Quicksort ===
=== Interne Suchberfahren ===


== Mergesort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung mit Multiple-value-context ===
=== Effizienzanalysen ===