Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:52] – [Worst Case] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 19:07] – [Best Case/Average Case] sbel
@@ Zeile 114: / Zeile 114: @@
 ==== Best Case/Average Case ====
+Wir wählen bei unserem sortierten Beispielarray jetzt immer das mittlere Element als Privotelement und schauen, was dann passiert:
+{{ :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''. 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)
+Wenn du immer ein zufälliges Element des Arrays als Pivotelement auswählst, beträgt die Laufzeit von Quicksort auch im
+Durchschnitt O(n log n): Der **Average Case** ist der **Best Case**.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Welche Laufzeiten haben die folgenden Operationen? Gib die Landau-Notation an und begründe deine Entscheidung kurz.
+   * Ausgabe der Werte aller Elemente in einem Array.
+   * Verdoppeln der Werte aller Elemente in einem Array.
+   * Verdoppeln des Werts des ersten Elements in einem Array.
+   * Erzeugen einer Multiplikationstabelle mit allen Elementen in einem Array. Es soll jedes Array-Element mit jedem anderen multipliziert werden.