Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 16:58] – angelegt sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 17:45] – 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:
+^                   ^ 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  |
+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...)).
-Im Abschnitt zur binären Suche haben wir uns bereits einige Gedanken zur [[Aufwandsabschätzung|..:..:big_o:start] gemacht.