Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 17:38] – [Tabelle] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 17:50] – [Quicksort] sbel
@@ Zeile 1: / Zeile 1: @@
 ====== Aufwandsabschätzung im Detail ======
+{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:onotation.drawio.png?300|}}
 Im Abschnitt zur binären Suche haben wir uns bereits einige Gedanken zur [[:faecher:informatik:oberstufe:algorithmen:big_o:start|Aufwandsabschätzung]] gemacht.
-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:
-{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:onotation.drawio.png?400|}}
+^                   ^ 10 Elemente    ^ 100 Elemente                ^ 1000 Elemente                ^
+| O(log n)          | 0,15 Sekunden  | 0,3 Sekunden                | 0,5 Sekunden                 |
+| O(n)              | 0,5 Sekunden   | 5 Sekunden                  | 50 Sekunden                  |
+| O(n log n)        | 1,6 Sekunden   | 33 Sekunden                 | 490 Sekunden                 |
+| O(n<sup>2</sup>)  | 5 Sekunden     | 8 Minuten                   | 14 Stunden                   |
+| O(n!)             | 2,1 Tage       | 1,4*10<sup>149</sup> Jahre  | 0,6*10<sup>2559</sup> Jahre  |
-Um ein Gefühl dafür zu bekommen, was die gängigsten Laufzeitcharakteristiken bedeuten, können die folgenden Beispiele dienen:
+Hypothetisch wurden für diese sehr grobe Berechnung eine Bearbeitungsgeschwindigkeit von ca. 20 Operationen je Sekunde zugrunde gelegt, was natürlich sehr viel langsamer ist, als ein Computer real arbeitet.
+Es ist aber wichtig zu verstehen, dass bei Problemen der Kategorie O(n<sup>2</sup>) oder gar O(n!) keine Rolle spielt: Wenn die Anzahl der Elemente wächst, **wächst der Aufwand schneller als jede Rechenleistung das zu kompensieren vermag**((Bei den Beispielen haben wir ja gerade mal 1000 Elemente betrachtet, das sind ja eigentlich lächerlich wenige...)).
+===== Quicksort =====
+Eine Besonderheit des Quicksort-Algorithmus ist, dass er Aufwand von der Wahl des Pivotelement abhängt.
-^                   ^ 10 Elemente    ^ 100 Elemente  ^ 1000 Elemente  |   |
+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.
-| O(log n)          | 0,15 Sekunden  | 0,3 Sekunden  | 0,5 Sekunden   |   |
-| O(n)              | 0,5 Sekunden   | 5 Sekunden    | 50 Sekunden    |   |
-| O(n log n)        | 1,6 Sekunden   | 33 Sekunden   | 490 Sekunden   |   |
-| O(n<sup>2</sup>)  ^ 5 Sekunden     | 5s            | 8Min           |   |