Quicksort: Unterschied zwischen den Versionen

Zeile 121:

</syntaxhighlight>

== ~~Maximumsuche~~ ==

== Vorbereitung: Indikatorvariablen und die Harmonische Reihe ==

Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem ~~mathematischen Trick~~: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu ~~verstehen~~, analysieren wir einen simplen Code zur Maximumsuche:

Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen der Vergleiche oft nicht mehr aus. Hier arbeiten wir in der Laufzeitanalyse mit einem stochastischen Werkzeug: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das Prinzip zu verinnerlichen, analysieren wir vorab einen simplen Code zur Maximumsuche:

Zeile 135:

}

</syntaxhighlight>

Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?

Die Vergleiche in der <code>if</code>-Bedingung werden immer exakt <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt tatsächlich überschrieben (Update-Operation)?

Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.

* '''Intuitiver Ansatz:'''

Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).

Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).

Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist bei zufälliger Verteilung exakt 50% (<math>\frac{1}{2}</math>).

Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.

Zeile 152:

Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).

'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um ~~später selbst~~ zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um im nächsten Abschnitt zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

== Laufzeitanalyse ==

Zeile 169:

<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 ~~asymtotischen~~ Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.

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>.

Zeile 205:

=== Average-Case (Durchschnittlicher Fall) ===

In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste ~~beispielsweise im Verhältnis~~ 30:70 oder 60:40.

In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf ~~das Prinzip der '''~~Indikatorvariablen~~'''~~ und ~~der '''Harmonischen~~ Reihe~~'''~~ zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>) im Laufe des Algorithmus miteinander verglichen werden?''

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische Reihe) zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des Algorithmus direkt miteinander verglichen werden?''

* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein Element, dessen Wert zwischen ~~den beiden~~ liegt, als Pivot gewählt wird.

* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.

* Sind die Daten völlig zufällig verteilt, ~~ist die Wahrscheinlichkeit, dass von~~ <math>k</math> ~~Elementen genau das größte oder kleinste~~ zuerst als Pivot gewählt ~~wird~~, exakt <math>\frac{2}{k}</math>.

* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.

* Sind die Daten völlig zufällig verteilt, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gewählt zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle (<math>z_i</math> oder <math>z_j</math>) bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.

Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im Array auf, erhalten wir folgende Doppel-Summe:

Summieren wir diese Wahrscheinlichkeiten (den Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:

~~Setzt~~ man ~~für~~ den Abstand <math>(j - i + 1)</math> ~~eine neue Variable~~ <math>k</math> ~~ein~~, löst sich die innere Summe auf zu:

Ersetzt man den Abstand <math>(j - i + 1)</math> formal durch die Laufvariable <math>k</math>, löst sich die innere Summe auf zu:

<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>

Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder~~, die wir bereits bei der Maximumsuche kennengelernt haben~~! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.

Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (stark vereinfacht) <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.

Da ~~Konstanten~~ wie ~~der Faktor~~ 2 beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:

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>.

@@ Zeile 121: / Zeile 121: @@
 </syntaxhighlight>
-== Maximumsuche ==
+== Vorbereitung: Indikatorvariablen und die Harmonische Reihe ==
-Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:
+Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen der Vergleiche oft nicht mehr aus. Hier arbeiten wir in der Laufzeitanalyse mit einem stochastischen Werkzeug: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das Prinzip zu verinnerlichen, analysieren wir vorab einen simplen Code zur Maximumsuche:
 <syntaxhighlight lang="java">
@@ Zeile 135: / Zeile 135: @@
 }
 </syntaxhighlight>
-Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?
+Die Vergleiche in der <code>if</code>-Bedingung werden immer exakt <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt tatsächlich überschrieben (Update-Operation)?
 Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.
 * '''Intuitiver Ansatz:'''
 Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).
-Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).
+Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist bei zufälliger Verteilung exakt 50% (<math>\frac{1}{2}</math>).
 Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.
@@ Zeile 152: / Zeile 152: @@
 Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).
-'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.
+'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um im nächsten Abschnitt zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.
 == Laufzeitanalyse ==
@@ Zeile 169: / Zeile 169: @@
 <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 asymtotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.
+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>.
@@ Zeile 205: / Zeile 205: @@
 === Average-Case (Durchschnittlicher Fall) ===
-In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste beispielsweise im Verhältnis 30:70 oder 60:40.
+In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).
-Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf das Prinzip der '''Indikatorvariablen''' und der '''Harmonischen Reihe''' zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>) im Laufe des Algorithmus miteinander verglichen werden?''
+Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische Reihe) zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des Algorithmus direkt miteinander verglichen werden?''
-* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein Element, dessen Wert zwischen den beiden liegt, als Pivot gewählt wird.
+* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.
-* Sind die Daten völlig zufällig verteilt, ist die Wahrscheinlichkeit, dass von <math>k</math> Elementen genau das größte oder kleinste zuerst als Pivot gewählt wird, exakt <math>\frac{2}{k}</math>.
+* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
+* Sind die Daten völlig zufällig verteilt, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gewählt zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle (<math>z_i</math> oder <math>z_j</math>) bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.
-Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im Array auf, erhalten wir folgende Doppel-Summe:
+Summieren wir diese Wahrscheinlichkeiten (den Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:
 <math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>
-Setzt man für den Abstand <math>(j - i + 1)</math> eine neue Variable <math>k</math> ein, löst sich die innere Summe auf zu:
+Ersetzt man den Abstand <math>(j - i + 1)</math> formal durch die Laufvariable <math>k</math>, löst sich die innere Summe auf zu:
 <math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>
-Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder, die wir bereits bei der Maximumsuche kennengelernt haben! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.
+Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (stark vereinfacht) <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.
-Da Konstanten wie der Faktor 2 beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:
+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>.