Laufzeitanalyse: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 24: / Zeile 24: @@
 * Das '''Average-Case-Szenario''' (durchschnittlicher Fall): Beschreibt eine zufällige Problemgröße und Datenanordnung, die zu einer mittleren (erwarteten) Durchlaufzeit führt.
 * Das '''Best-Case-Szenario''' (bester Fall): Beschreibt diejenige Datenanordnung, die zu einer minimalen Durchlaufzeit führt (z. B. eine bereits vollständig sortierte Liste). Dies entspricht der unteren Schranke.
+== Mathematische Berechnung des Average-Case (Erwartungswert) ==
+Im Gegensatz zum Worst-Case oder Best-Case, die lediglich Extremfälle betrachten, ist die Berechnung des Average-Case (durchschnittlicher Fall) mathematisch anspruchsvoller. Er entspricht in der Stochastik dem '''Erwartungswert''' der Laufzeit.
+Um diesen zu berechnen, müssen alle möglichen Eingaben der Größe <math>n</math> sowie deren Eintrittswahrscheinlichkeiten berücksichtigt werden. Die allgemeine Formel für den Erwartungswert <math>E(T)</math> der Laufzeit lautet:
+<math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math>
+Dabei ist:
+* <math>E</math> die Menge aller möglichen Eingaben der Größe <math>n</math>.
+* <math>p_i</math> die Wahrscheinlichkeit, dass genau die Eingabe <math>i</math> auftritt.
+* <math>t_i</math> die Anzahl der elementaren Rechenschritte (Laufzeit), die der Algorithmus für die Eingabe <math>i</math> benötigt.
+Häufig wird der Einfachheit halber eine '''Gleichverteilung''' (Laplace-Annahme) vorausgesetzt. Das bedeutet, man geht davon aus, dass jede mögliche Eingabekonfiguration gleich wahrscheinlich ist.
+=== Beispiel: Average-Case der Linearen Suche ===
+Um das Prinzip zu verdeutlichen, betrachten wir den Algorithmus der linearen Suche: Ein Array der Länge <math>n</math> wird von vorne nach hinten durchsucht, bis ein gesuchtes Element <math>x</math> gefunden wird.
+Wir treffen für diese Analyse folgende Annahmen:
+# Das gesuchte Element <math>x</math> befindet sich definitiv im Array.
+# Jede Position <math>1, 2, \dots, n</math> im Array ist für das Element <math>x</math> gleich wahrscheinlich. Die Wahrscheinlichkeit <math>p</math>, dass es an einer bestimmten Stelle steht, ist somit <math>p = \frac{1}{n}</math>.
+Wenn das Element an der ersten Stelle steht, benötigen wir 1 Vergleich. Steht es an der zweiten Stelle, benötigen wir 2 Vergleiche, und so weiter. Steht es an der letzten Stelle, benötigen wir <math>n</math> Vergleiche. Wir setzen diese Werte in die Formel für den Erwartungswert ein:
+<math>E(T) = \sum_{i=1}^{n} \left( \frac{1}{n} \cdot i \right)</math>
+Da <math>\frac{1}{n}</math> ein konstanter Faktor unabhängig vom Laufindex <math>i</math> ist, können wir ihn vor die Summe ziehen:
+<math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math>
+Der hintere Teil der Gleichung ist die bekannte '''Gaußsche Summenformel''' (arithmetische Reihe), die sich auflösen lässt zu <math>\frac{n(n+1)}{2}</math>. Wir setzen dies ein:
+<math>E(T) = \frac{1}{n} \cdot \frac{n(n+1)}{2}</math>
+Durch Kürzen des <math>n</math> erhalten wir das finale Ergebnis:
+<math>E(T) = \frac{n+1}{2} = \frac{1}{2}n + \frac{1}{2}</math>
+'''Fazit:''' Im Durchschnitt benötigt die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Für die asymptotische Laufzeitanalyse ignorieren wir Konstanten und niederwertige Terme, sodass auch der Average-Case der linearen Suche in der Komplexitätsklasse <math>\mathcal{O}(n)</math> liegt.
+=== Vorbereitung auf Quicksort: Indikatorvariablen und die Harmonische Reihe ===
+Bei einfachen Algorithmen reicht eine Gleichverteilung zur Herleitung oft aus. Bei komplexeren, teile-und-herrsche-basierten Algorithmen wie [[Quicksort]] reicht dies nicht mehr. Um den Average-Case von Quicksort (<math>\mathcal{O}(n \log n)</math>) selbstständig ermitteln zu können, benötigt man zwei mathematische Werkzeuge: '''Indikatorzufallsvariablen''' und die '''Harmonische Reihe'''.
+Um diese Konzepte zu erlernen, betrachten wir als vorbereitendes Beispiel die Bestimmung des Maximums in einem unsortierten Array:
+<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 grundlegenden Vergleiche (<code>A[i] > max</code>) finden in jedem Fall <math>n-1</math> Mal statt. Die spannende Frage für die Laufzeitanalyse (insbesondere beim Schreiben in den Speicher) ist jedoch: '''Wie oft wird die Update-Operation <code>max = A[i]</code> im Durchschnitt ausgeführt?'''
+Wir gehen von einer zufälligen Permutation (Anordnung) der Zahlen aus.
+* '''Schritt 1: Indikatorvariablen definieren'''
+Wir definieren eine Indikatorzufallsvariable <math>X_i</math>. Diese nimmt den Wert <math>1</math> an, wenn an der Stelle <math>i</math> ein neues Maximum gefunden wird, und <math>0</math>, wenn nicht. Die Gesamtzahl der Updates <math>X</math> ist die Summe aller <math>X_i</math>: <math>X = \sum_{i=1}^{n} X_i</math>.
+* '''Schritt 2: Wahrscheinlichkeit ermitteln'''
+Damit an der Stelle <math>i</math> ein neues Maximum gefunden wird, muss die Zahl <math>A[i]</math> die größte unter den ersten <math>i</math> Zahlen sein. Da wir von einer zufälligen Anordnung ausgehen, ist jede der ersten <math>i</math> Zahlen mit gleicher Wahrscheinlichkeit die größte. Die Wahrscheinlichkeit ist also:
+<math>P(X_i = 1) = \frac{1}{i}</math>
+Der Erwartungswert <math>E[X_i]</math> ist bei Indikatorvariablen identisch mit ihrer Wahrscheinlichkeit: <math>E[X_i] = \frac{1}{i}</math>.
+* '''Schritt 3: Erwartungswert der Summe berechnen'''
+Dank der Linearität des Erwartungswertes (Erwartungswerte von Summen dürfen als Summe der Erwartungswerte geschrieben werden) erhalten wir:
+<math>E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}</math>
+Diese Summe ist in der Mathematik als die <math>n</math>-te Partialsumme der '''Harmonischen Reihe''' (<math>H_n</math>) bekannt. Für große <math>n</math> wächst die harmonische Reihe logarithmisch, sie lässt sich annähern durch den natürlichen Logarithmus: <math>H_n \approx \ln(n)</math>.
+'''Erkenntnis für Quicksort:'''
+Die Update-Operation wird im Average-Case also nur <math>\mathcal{O}(\log n)</math> Mal ausgeführt, obwohl das Array <math>n</math> Elemente hat. Genau dieses Prinzip – das Aufsummieren von stochastischen Wahrscheinlichkeiten der einzelnen Array-Elemente, die zu einer harmonischen Reihe und damit zu einem logarithmischen Faktor führen – ist der mathematische Schlüssel, um die Average-Case-Laufzeit von <math>\mathcal{O}(n \log n)</math> bei Quicksort herzuleiten.
 == Beispiel: Laufzeitanalyse von Insertion Sort ==
@@ Zeile 30: / Zeile 105: @@
 <syntaxhighlight lang="java">
 public void sortierenEinfuegen_MC() {
     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];
             j = i;
             do {
                 zSortfeld[j] = zSortfeld[j - 1];
                 j--;
             } while ((j > 0) && (zSortfeld[j - 1] > v));
             zSortfeld[j] = v;
         }
         printAnalyse(i);
     }
 }
 </syntaxhighlight>
@@ Zeile 62: / Zeile 137: @@
 * '''Verhalten:''' Die <code>if</code>-Bedingung ist hier '''immer wahr'''. Das aktuell betrachtete Element muss in der inneren <code>do-while</code>-Schleife jedes Mal bis ganz an den Anfang des Arrays verschoben werden.
 * '''Aufwand:'''
 ** Beim ersten Durchlauf vergleichen wir nur die 7 mit der 11 (1 Vergleich). Aufwand: <math>c \cdot 1</math>.
 ** Beim zweiten Durchlauf müssen wir das nächste Element mit den zwei bereits sortierten vergleichen. Aufwand: <math>c \cdot 2</math>.
@@ Zeile 71: / Zeile 146: @@
 [[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]]
 Für die asymptotische Betrachtung extrem großer Werte von <math>n</math> verwerfen wir den langsamer wachsenden (niederwertigen) Term <math>\frac{c}{2}n</math> sowie die Konstante <math>\frac{c}{2}</math>.
 * '''Komplexität:''' Der Aufwand wächst quadratisch. Der Insertion Sort hat im Worst-Case somit eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.