Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:59] – [Best Case/Average Case] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 19:00] – [Best Case/Average Case] sbel
@@ Zeile 119: / Zeile 119: @@
 {{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray06.drawio.png |}}
-Die Größe des Call Stacks ist hier nur 4 -- oder allgemein (analog zur binären Suche) von der Ordnung ''log n''.
+Die Größe des Call Stacks ist hier nur 4 -- oder allgemein (analog zur binären Suche) von der Ordnung ''log n''. Auch hier gilt natürlich, dass wir auf jeder Ebene des des Call Stacks  alle Elemente betrachten muss um zu partitionieren - unabhängig vom gewählten Pivotelement, also auch hier: Die Bearbeitung jeder Ebene des Call Stacks benötigt den Aufwand O(n).
+Da es aber nur log n Ebenen gibt, ist der Aufwand von Quicksort im Best Case O(n * log n) also O(n log n)