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:01] – [Quicksort] 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. **Dennoch hat auch Sie die Laufzeit O(n)!**