Quicksort: Unterschied zwischen den Versionen

Zeile 120:

}

</syntaxhighlight>

== Maximumsuche ==

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:

public int findMax(int[] A) {

int max = A[0];

for (int i = 1; i < A.length; i++) {

if (A[i] > max) {

max = A[i]; // Update-Operation

}

return max;

}

</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)?

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

* '''Mathematischer Ansatz (Indikatorvariablen):'''

Wir definieren einen „Schalter“ (die Indikatorvariable) <math>X_i</math>. Er ist <math>1</math>, wenn ein neues Maximum an Stelle <math>i</math> gefunden wird, sonst <math>0</math>. Die Wahrscheinlichkeit dafür ist <math>P(X_i = 1) = \frac{1}{i}</math>.

Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:

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.

== Laufzeitanalyse ==

@@ Zeile 120: / Zeile 120: @@
 }
 </syntaxhighlight>
+== Maximumsuche ==
+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:
+<syntaxhighlight lang="java">
+public int findMax(int[] A) {
+    int max = A[0];
+    for (int i = 1; i < A.length; i++) {
+        if (A[i] > max) {
+            max = A[i]; // Update-Operation
+        }
+    }
+    return max;
+}
+</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)?
+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 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>.
+* '''Mathematischer Ansatz (Indikatorvariablen):'''
+Wir definieren einen „Schalter“ (die Indikatorvariable) <math>X_i</math>. Er ist <math>1</math>, wenn ein neues Maximum an Stelle <math>i</math> gefunden wird, sonst <math>0</math>. Die Wahrscheinlichkeit dafür ist <math>P(X_i = 1) = \frac{1}{i}</math>.
+Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:
+<math>E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}</math>
+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.
 == Laufzeitanalyse ==