Hallo.
Die Wortcase Laufzeit ist mit O(n^2) angegeben. Wenn ich das
richtig verstehe passiert das z. B. dann, wenn ich als
Pivotelement bzw. Wert das erste Element wähle und die Liste
absteigend sortiert ist.
So wie ich das sehe, kann ich dem doch vorbeugen indem ich vor
dem Sortieren für jede (Teil-)Liste den Median ermittel und
dann mit diesem Wert bzw. diesem Element als Pivotelement
arbeite.
In dem Fall muss man die Laufzeit zur Berechnung des Median für jede Teilliste mit einrechnen.
Oder würde sich dadurch die durchschnittliche Laufzeit so
stark verschlechtern, dass sich das nicht lohnt?
Wenn ich mich nicht ganz irre, gibt es Median-Algorithmen, die O(n) Laufzeit benötigen. Man muss aber nun nicht nur einen Median berechnen, sondern für jede Teilliste. Im worst case bekommt man insgesamt n Teillisten, somit wäre das ebenfalls O(n^2) insgesamt.
Die Laufzeit würde dadurch also nicht verbessert.
Als Möglichkeiten für die Pivot-Wahl kenne ich eigentlich folgende:
- Immer 1. Element (gibt Worstcase-Laufzeit auf sortierten Listen)
- Immer Element mit mittlerem Index
- Median aus 1., letzetem und mittlerem Element (die Berechnung hat dann konstante Laufzeit, da Median aus 3 Elementen)
- zufällige Wahl des Pivotelements
Der Worst case O(n^2) kann in jedem der Fälle eintreten. Im 4. Fall ist die zugrunde liegende Liste egal, da hängt der worst case rein vom Zufall ab. Bei den 1. drei Fällen hängt es davon ab, wie die Liste vorher sortiert war.
Sebastian.
