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 17:44] – sbel | faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 17:51] – [Quicksort] sbel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Aufwandsabschätzung im Detail ====== | ====== Aufwandsabschätzung im Detail ====== | ||
+ | {{ : | ||
Im Abschnitt zur binären Suche haben wir uns bereits einige Gedanken zur [[: | Im Abschnitt zur binären Suche haben wir uns bereits einige Gedanken zur [[: | ||
- | |||
- | Eine Besonderheit des QuicksortAlgorithmus ist, dass er Aufwand von der Wahl des Pivotelement abhängt. | ||
- | |||
- | {{ : | ||
Um ein Gefühl dafür zu bekommen, was die gängigsten Laufzeitcharakteristiken bedeuten, können die folgenden Beispiele dienen: | Um ein Gefühl dafür zu bekommen, was die gängigsten Laufzeitcharakteristiken bedeuten, können die folgenden Beispiele dienen: | ||
Zeile 19: | Zeile 16: | ||
- | Es ist aber wichtig zu verstehen, dass bei Problemen der Kategorie O(n< | + | Es ist aber wichtig zu verstehen, dass bei Problemen der Kategorie O(n< |
+ | |||
+ | ===== Quicksort ===== | ||
+ | |||
+ | Eine Besonderheit des Quicksort-Algorithmus ist, dass er Aufwand von der Wahl des Pivotelement abhängt. | ||
+ | |||
+ | Das hast du vielleicht bei deinen Übungen bereits bemerkt: Wenn man das Element stets sehr ungünstig wählt, gewinnt man bei Aufteilen des Problem kaum etwas, die nach der Partitionierung größte zu sortierende Menge ist im schlechtesten Fall in jedem Rekursionsschritt nur ein Element kleiner als zuvor, wobei die kleinste Menge immer leer ist. | ||
+ | Quicksort hat im **Worst Case** eine Laufzeit von O(n< | ||