|
|
| Zeile 54: |
Zeile 54: |
|
| |
|
| '''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>. | | '''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>. |
|
| |
| === 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 von Insertion Sort == | | == Laufzeitanalyse von Insertion Sort == |
