Laufzeitanalyse: Unterschied zwischen den Versionen

(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)

Zeile 29:

Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:

* <math>p_i</math> ist die Wahrscheinlichkeit ~~für einen bestimmten Fall~~ <math>i</math>.

Hierbei bedeuten die Variablen:

* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus ~~in diesem Fall~~ braucht.

* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).

* <math>|F|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.

* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.

* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.

Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder ~~Fall~~ tritt mit derselben Wahrscheinlichkeit auf.

Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.

=== ~~Beispiel 1:~~ Average-Case der Linearen Suche ===

=== Average-Case der Linearen Suche ===

Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich.

Zeile 55:

Zeile 58:

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

==~~= Beispiel 2: Vorbereitung auf Quicksort (Maximumsuche) ===~~

== Laufzeitanalyse von Insertion Sort ==

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.

~~== Beispiel 3:~~ Laufzeitanalyse von Insertion Sort ==

Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an.

Zeile 96:

Zeile 65:

int v, i, j;

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

~~c++; // Zähler für Vergleiche~~

if (zSortfeld[i] < zSortfeld[i - 1]) {

v = zSortfeld[i];

Zeile 131:

Zeile 99:

=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===

~~Die Werte im~~ Array sind ~~völlig zufällig verteilt~~.

Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.

* '''~~Verhalten~~:''' ~~Im Durchschnitt müssen wir ein Element nicht~~ bis ganz ~~an den Anfang schieben (wie im Worst-Case~~), ~~sondern nur bis zur~~ '''~~Hälfte~~''' des ~~bisher sortierten Bereichs~~.

* '''~~Aufwand~~:''' Die ~~Anzahl~~ der ~~Vergleiche halbiert~~ sich ~~grob im Vergleich zum Worst-Case~~. ~~Der Aufwand liegt~~ bei ~~ca.~~ <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.

* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.

* '''~~Komplexität~~:''' ~~Wie wir gelernt haben, ignoriert die Groß-~~O-Notation ~~konstante Brüche~~ (wie <math>\frac{1}{4}</math>)~~. Es bleibt bei~~ der ~~höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin~~ <math>\mathcal{O}(n^2)</math>.

* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.

* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):

<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>

Wir klammern <math>\frac{1}{2}</math> aus:

<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>

Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:

<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>

'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

@@ Zeile 29: / Zeile 29: @@
 Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:
-<math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math>
+<math>E(T) = \sum_{i=1}^{|F|} p_i \cdot t_i</math>
-* <math>p_i</math> ist die Wahrscheinlichkeit für einen bestimmten Fall <math>i</math>.
+Hierbei bedeuten die Variablen:
-* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus in diesem Fall braucht.
+* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
+* <math>|F|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
+* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
+* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.
-Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Fall tritt mit derselben Wahrscheinlichkeit auf.
+Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.
-=== Beispiel 1: Average-Case der Linearen Suche ===
+=== Average-Case der Linearen Suche ===
 Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich.
@@ Zeile 55: / Zeile 58: @@
 '''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>.
-=== Beispiel 2: Vorbereitung auf Quicksort (Maximumsuche) ===
+== Laufzeitanalyse von Insertion Sort ==
-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.
-== Beispiel 3: Laufzeitanalyse von Insertion Sort ==
 Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an.
@@ Zeile 96: / Zeile 65: @@
      int v, i, j;
      for (i = 1; i < zSortfeld.length; i++) {
-        c++; // Zähler für Vergleiche
          if (zSortfeld[i] < zSortfeld[i - 1]) {
              v = zSortfeld[i];
@@ Zeile 131: / Zeile 99: @@
 === 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
-Die Werte im Array sind völlig zufällig verteilt.
+Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.
-* '''Verhalten:''' Im Durchschnitt müssen wir ein Element nicht bis ganz an den Anfang schieben (wie im Worst-Case), sondern nur bis zur '''Hälfte''' des bisher sortierten Bereichs.
-* '''Aufwand:''' Die Anzahl der Vergleiche halbiert sich grob im Vergleich zum Worst-Case. Der Aufwand liegt bei ca. <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.
+* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.
-* '''Komplexität:''' Wie wir gelernt haben, ignoriert die Groß-O-Notation konstante Brüche (wie <math>\frac{1}{4}</math>). Es bleibt bei der höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin <math>\mathcal{O}(n^2)</math>.
+* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.
+* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):
+<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>
+Wir klammern <math>\frac{1}{2}</math> aus:
+<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>
+Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:
+<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>
+'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]