Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 19:04] – [Best Case/Average Case] sbel
+++ faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2024 16:48] (aktuell) – [Quicksort] Marco Kuemmel
@@ Zeile 22: / Zeile 22: @@
 Eine Besonderheit des Quicksort-Algorithmus ist, dass er Aufwand von der Wahl des Pivotelement abhängt.
-Das hast du vielleicht bei deinen Übungen bereits bemerkt: Wenn man das Element stets sehr ungünstig wählt, gewinnt man bei Aufteilen des Problem kaum etwas, die nach der Partitionierung größte zu sortierende Menge ist im schlechtesten Fall in jedem Rekursionsschritt nur ein Element kleiner als zuvor, wobei die kleinste Menge immer leer ist.
+Das hast du vielleicht bei deinen Übungen bereits bemerkt: Wenn man das Element stets sehr ungünstig wählt, gewinnt man beim Aufteilen des Problems kaum etwas. Die nach der Partitionierung größte zu sortierende Menge ist im schlechtesten Fall in jedem Rekursionsschritt nur ein Element kleiner als zuvor, wobei die kleinste Menge immer leer ist.
 <WRAP center round info 95%>
@@ Zeile 28: / Zeile 28: @@
 </WRAP>
-Aber was bedeutet **Worst Case** und **Avergae Case** genau?
+Aber was bedeutet **Worst Case** und **Average Case** genau?
 ===== Die Landau Notation im Detail =====
@@ Zeile 125: / Zeile 125: @@
 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.