Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 17:53] – [Quicksort] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:16] – [Die Landau Notation im Detail] sbel
@@ Zeile 27: / Zeile 27: @@
 Quicksort hat im **Worst Case** eine Laufzeit von O(n<sup>2</sup>), im **Average Case** eine Laufzeit von O(n log n)
 </WRAP>
+Aber was bedeutet **Worst Case** und **Avergae Case** genau?
+===== Die Landau Notation im Detail =====
+Die Landau Notation unterschlägt Konstanten - wenn man schreibt O(n) meint man eigentlich O(c*n). Das kann man sich am Beispiel eine Methode klar machen, die die Elemente eines Arrays ausgibt:
+<code>
+printArray(array):
+  für jedes Element element von array:
+    print element
+</code>
+Diese Methode hat die Laufzeit O(n) - sie muss jedes Element einmal anfassen uns ausgeben, bei doppelt so vielen Elementen dauert das doppelt so lange.
+Jetzt betrachten wir die folgende Methode (Pseudocode):
+<code>
+printArrayMitPause(array):
+  für jedes Element element von array:
+    print element
+    warte(10s)
+</code>
+Die Methode ''printArrayMitPause'' benötigt sehr viel länger, um das Array auszugeben, da sie zwischen der Ausgabe zweier Arrayelement immer eine Pause von 10 Sekunden macht. Sie hat also gewissermaßen die Laufzeit ''10Sekunden * n''. **Dennoch hat auch sie in der Landau-Notation die Laufzeit O(n), da man die Konstante (hier: 10 Sekunden) vernachlässigt!**
+Darf man das?
+Dazu vergleichen wir nochmal gedanklich die einfach Suche und die binäre Suche und ergänzen die Laufzeiten mit realen Zeitfaktoren:
+^ Einfache Suche ^ Binäre Suche ^
+| ''10 Millisekunden * n'' | ''1 Sekunde * log n'' |
+Die einfache Suche läuft also beispielsweise auf einem sehr viel schnelleren Rechner, so dass pro Element lediglich 10 Millisekunden hinzukommen - die binäre Suche läuft auf einem langsameren Rechner, die Zeit wächst hier zwar logarithmisch aber mit einem Faktor von 1 Sekunde.
+Dieser Vorteil wird jedoch von einer großen Anzahl von Elementen zunichte gemacht.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+Wie lange dauert es, eine Liste mit 4 Milliarden Elementen mit den beiden Algorithmen zu durchsuchen?
+++++ Lösung |
+| Einfache Suche | 10ms * 4 Milliarden | 462 Tage |
+| Binäre Suche | 1Sekunde * log(4Milliarden) | 35 Sekunden |
+Beachte: der Logarithmus in O(log n) wird zur Basis 2 berechnet.
+++++