Vorteil T&H
Warum das Prinzip "Teile und Herrsche" einen zeitlichen Vorteil bietet, soll genauer an Quicksort betrachtet werden. Nehmen wir an, wir hätten einen Sortieralgorithmus mit quadratischer Charakteristik. Für die Sortierzeit ergibt sich
| T | = | K * n2 |
Werden die Datensätze in zwei gleichgroße Gruppen so aufgetrennt, dass alle Elemente der einen Gruppe kleiner sind als alle Elemente der zweiten Gruppe, bekommen wir folgende Zeiten:
| T | = | K * (½ n)2 + K * (½ n)2 | |
| = | ¼ K * n2 + ¼ K * n2 | ||
| = | ½ K * n2 |
Unter Vernachlässigung der Zeit für den Teilungsvorgang wird die Arbeit also doppelt so schnell erledigt. Werden diese Gruppen noch einmal unterteilt, erhalten wir
| T | = | K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2 | |
| = | 4/16 K * n2 | ||
| = | ¼ K * n2 |
Bei jeder Halbierung aller Gruppen halbiert sich also auch die gesamte Bearbeitungszeit. Wie oft eine Gruppe sinnvoll durch 2 geteilt werden kann, also wie viele Rekursionslevel man hat, errechnet sich über den Zweier-Logarithmus
| L | = | lg2 (n) |
Da auf der letzten Stufe nur noch ein Element in der Liste ist, verschwindet die quadratische Charakteristik für diese Listenlänge.
| n2 | = | 12 | = | 1 |
Da auf jedem Level jeder Datensatz einmal betrachtet werden muss (Entscheidung, wo er hin gehört), kann die Zeit für eine Sortierung durch
| T | = | M * n * lg2(n) |
angegeben werden, wobei M die Implementierung wiederspiegelt und angibt, wieviel Zeit man für die Entscheidung benötigt, in welche Unterhälfte ein Datensatz soll und um ihn dorhin zu verschieben.