Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
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:44] – 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 [[Aufwandsabschätzung|..:..:big_o:start] gemacht. | + | 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. | ||
+ | |||
+ | {{ :faecher: | ||
+ | |||
+ | Um ein Gefühl dafür zu bekommen, was die gängigsten Laufzeitcharakteristiken bedeuten, können die folgenden Beispiele dienen: | ||
+ | |||
+ | ^ ^ 10 Elemente | ||
+ | | O(log n) | 0,15 Sekunden | ||
+ | | O(n) | 0,5 Sekunden | ||
+ | | O(n log n) | 1,6 Sekunden | ||
+ | | O(n< | ||
+ | | O(n!) | 2,1 Tage | 1, | ||
+ | |||
+ | 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< | ||
+ | |||