Teile und Herrsche 1 SS09

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

1. in Teilprobleme zerlegt wird
2. die Teilprobleme gelöst werden
3. die Teilprobleme zu einer Lösung vereint werden.
   

Die folgende Rechnung dient als Beweis, das 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.

Quicksort

Das Verfahren

Funktionsorientierte Beschreibung

Effizienz von Quicksort

Interne Suchberfahren

Mergesort

Das Verfahren

Funktionsorientierte Beschreibung mit Multiple-value-context

Effizienzanalysen