Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:17] – [Die Landau Notation im Detail] sbel | faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 19:00] – [Best Case/Average Case] sbel | ||
---|---|---|---|
Zeile 85: | Zeile 85: | ||
++++ | ++++ | ||
+ | <WRAP center round important 95%> | ||
+ | Wenn die **Anzahl der Elemente veränderlich** ist, spielen Faktoren bei der Landau Notation keine Rolle. Jeder Vorteil eines Faktors wird bei einem Algorithmus mit besserer Laufzeit bei genügend großer Anzahl der Elemente wieder eingeholt. | ||
+ | </ | ||
+ | ==== Faktoren spielen doch eine Rolle? ==== | ||
+ | Manchmal spielen Faktoren aber eben doch eine Rollen - nämlich dann, wenn die Anzahl der Elemente beim Vergleich zweier Algorithmen vorgegeben ist. Das ist beispielsweise dann der Fall, wenn wir ein und dasselbe Array mit zwei unterschiedlichen Sortierverfahren sortieren wollen: Wenn die Laufzeit von Quicksort sich in Abhängigkeit des gewählten Pivotelements verändert, spielt der Faktor eine Rolle. | ||
+ | Die Konstante von Quicksort ist kleiner als die von Mergesort. Wenn beide Algorithmen eine Laufzeit von O(n log n) benötigen, ist Quicksort also schneller, wenn sich bei einer festen Anzahl von Elementen aber die Laufzeit von Quicksort hin zu O(n< | ||
+ | ===== Average Case und Worst Case bei Quicksort ===== | ||
+ | Wie oben bereits angedeutet, ist es besonders ungünstig, wenn die Partitionireung bei Quicksort immer so ausfällt, dass das größte zu sortierende " | ||
+ | {{ : | ||
+ | |||
+ | ==== Worst Case ==== | ||
+ | |||
+ | |||
+ | Wenn man den Sortiervorgang nachvollzieht, | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Auf jeder Ebene des des Call Stacks muss man alle Elemente betrachten um zu partitionieren - unabhängig vom gewählten Pivotelement. Das bedeutet, die Bearbeitung jeder Ebene des Call Stacks benötigt den Aufwand O(n). | ||
+ | |||
+ | Im **Worst Case** haben wir also n Ebenen, die jeweils mit dem Aufwand O(n) bearbeitet werden müssen - im schlechtesten Fall hat Quicksort also die Laufzeit O(n*n) also O(n< | ||
+ | |||
+ | ==== Best Case/ | ||
+ | |||
+ | Wir wählen bei unserem sortierten Beispielarray jetzt immer das mittlere Element als Privotelement und schauen, was dann passiert: | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Die Größe des Call Stacks ist hier nur 4 -- oder allgemein (analog zur binären Suche) von der Ordnung '' | ||
+ | |||
+ | Da es aber nur log n Ebenen gibt, ist der Aufwand von Quicksort im Best Case O(n * log n) also O(n log n) |