faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:start [31.01.2022 18:30] – [Faktoren spielen doch eine Rolle?] sbelfaecher: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.  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%> <WRAP center round info 95%>
Zeile 28: Zeile 28:
 </WRAP> </WRAP>
  
-Aber was bedeutet **Worst Case** und **Avergae Case** genau?+Aber was bedeutet **Worst Case** und **Average Case** genau?
  
 ===== Die Landau Notation im Detail ===== ===== Die Landau Notation im Detail =====
Zeile 90: Zeile 90:
  
  
-===== Faktoren spielen doch eine Rolle? =====+==== Faktoren spielen doch eine Rolle? ====
  
 Manchmal spielen Faktoren aber eben doch eine Rollen - nämlich dann, wenn die Anzahl der Elemente beim Vergleich zweier Algorithmen vorgegeben ist. Das ist beispielsweise dann der Fall, wenn wir ein und dasselbe Array mit zwei unterschiedlichen Sortierverfahren sortieren wollen: Wenn die Laufzeit von Quicksort sich in Abhängigkeit des gewählten Pivotelements verändert, spielt der Faktor eine Rolle. Manchmal spielen Faktoren aber eben doch eine Rollen - nämlich dann, wenn die Anzahl der Elemente beim Vergleich zweier Algorithmen vorgegeben ist. Das ist beispielsweise dann der Fall, wenn wir ein und dasselbe Array mit zwei unterschiedlichen Sortierverfahren sortieren wollen: Wenn die Laufzeit von Quicksort sich in Abhängigkeit des gewählten Pivotelements verändert, spielt der Faktor eine Rolle.
  
-Die Konstante von Quicksort ist kleiner als die von Mergesort. Wenn beide Algorithmen eine Laufzeit von O(n log n) benötigen, ist Quicksort also schneller, wenn sich bei einer festen Anzahl von Elementen aber die Laufzeit von Quicksort hin zu O(n<sup>2</sup>) verschiebt, kann es sein, dass Mergesort irgendwann schnellet ist, weil Mergesort //immer// die Laufzeit O(n log n) hat.+Die Konstante von Quicksort ist kleiner als die von Mergesort. Wenn beide Algorithmen eine Laufzeit von O(n log n) benötigen, ist Quicksort also schneller, wenn sich bei einer festen Anzahl von Elementen aber die Laufzeit von Quicksort hin zu O(n<sup>2</sup>) verschiebt, kann es sein, dass Mergesort irgendwann schneller ist, weil Mergesort //immer// die Laufzeit O(n log n) hat. 
 + 
 +===== Average Case und Worst Case bei Quicksort ===== 
 + 
 +Wie oben bereits angedeutet, ist es besonders ungünstig, wenn die Partitionireung bei Quicksort immer so ausfällt, dass das größte zu sortierende "Unterarray" lediglich ein Element weniger hat, als das Array im Rekursionsschritt zuvor. Besonders leicht kann man sich das klar machen, wenn man ein Array betrachtet, das bereits sortiert ist und stets das erste Array-Element als Pivotelement wählt: 
 + 
 +{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray04.drawio.png  |}} 
 + 
 +==== Worst Case ==== 
 + 
 + 
 +Wenn man den Sortiervorgang nachvollzieht, wenn man jeweils das erste Element des Arrays mit den größeren Elementen als Pivotelement wählt, sieht das so aus: 
 + 
 +{{ :faecher:informatik:oberstufe:algorithmen:sortieren:landau_revisited:qsortarray05.drawio.png |}} 
 + 
 +Auf jeder Ebene des des Call Stacks muss man alle Elemente betrachten um zu partitionieren - unabhängig vom gewählten Pivotelement. Das bedeutet, die Bearbeitung jeder Ebene des Call Stacks benötigt den Aufwand O(n). 
 + 
 +Im **Worst Case** haben wir also n Ebenen, die jeweils mit dem Aufwand O(n) bearbeitet werden müssen - im schlechtesten Fall hat Quicksort also die Laufzeit O(n*n) also O(n<sup>2</sup>).  
 + 
 +==== 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.
  • faecher/informatik/oberstufe/algorithmen/sortieren/landau_revisited/start.1643650226.txt.gz
  • Zuletzt geändert: 31.01.2022 18:30
  • von sbel