Quicksort: Unterschied zwischen den Versionen

Zeile 155:

== Laufzeitanalyse ==

~~=== Worst-Case (Schlechtester Fall) ===~~

~~[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]~~

Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.

Der Aufwand für das Vergleichen (Partitionieren) einer Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).

~~Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.~~

~~Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:~~

~~<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math>~~

~~Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:~~

~~<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>~~

~~Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.~~

~~'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.~~

=== Best-Case (Bester Fall) ===

Zeile 223:

Zeile 207:

Da konstante Vorfaktoren wie die <math>2</math> beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:

'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.

=== Worst-Case (Schlechtester Fall) ===

[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]

Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.

Der Aufwand für das Vergleichen (Partitionieren) einer Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).

Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.

Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:

Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:

<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>

Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.

'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

[[Kategorie:FI_I_TP2]]

@@ Zeile 155: / Zeile 155: @@
 == Laufzeitanalyse ==
-=== Worst-Case (Schlechtester Fall) ===
-[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]
-Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.
-Der Aufwand für das Vergleichen (Partitionieren) einer Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).
-Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.
-Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
-<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math>
-Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:
-<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>
-Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.
-'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.
 === Best-Case (Bester Fall) ===
@@ Zeile 223: / Zeile 207: @@
 Da konstante Vorfaktoren wie die <math>2</math> beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:
 '''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.
+=== Worst-Case (Schlechtester Fall) ===
+[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]
+Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.
+Der Aufwand für das Vergleichen (Partitionieren) einer Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).
+Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.
+Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
+<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math>
+Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:
+<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>
+Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.
+'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]
 [[Kategorie:FI_I_TP2]]