@@ Zeile 1: / Zeile 1: @@
 == Einführung ==
 [[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]]
-Die Laufzeitanalyse untersucht die Zeitkomplexität eines [[Algorithmus]]. Da die reale Ausführungszeit stark von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine, hardwareunabhängige Betrachtung die Anzahl der elementaren [[Anweisung|Befehle]] (Operationen) analysiert, die ein Algorithmus zur Lösung eines Problems benötigt. Diese Anzahl ist abhängig von der Größe der Eingabemenge, deren Umfang auch als '''Problemgröße''' (oft <math>n</math>) bezeichnet wird.
-Für kleine Eingabemengen ist die Analyse häufig von geringerer Bedeutung, da auch ineffiziente [[Algorithmus|Algorithmen]] hier oft ausreichend schnelle Ergebnisse liefern. Entscheidend ist die Betrachtung für sehr große Problemgrößen, insbesondere unter ungünstigen Startbedingungen. Hier spricht man von der asymptotischen [[Programmausführung|Laufzeit]]. In Anlehnung an eine mathematische Asymptote beschreibt sie das Zeitverhalten des Algorithmus für eine potenziell unendlich wachsende Eingabemenge (z. B. eine theoretisch unendlich lange Zahlenfolge beim [[Sortieren]]).
+Die '''Laufzeitanalyse''' untersucht, wie viele Rechenschritte ein [[Algorithmus]] benötigt, um ein Problem zu lösen.
+Da die tatsächliche Laufzeit eines Programms stark vom Computer abhängt (z. B. Prozessor oder Arbeitsspeicher), betrachtet man nicht die Zeit in Sekunden, sondern die Anzahl der benötigten '''Operationen'''.
+Diese Anzahl hängt von der Größe der Eingabe ab.
+Die Eingabegröße wird meist mit <math>n</math> bezeichnet.
+Beispiel:
+* Beim Sortieren ist <math>n</math> die Anzahl der zu sortierenden Werte.
+* Beim Durchsuchen einer Liste ist <math>n</math> die Länge der Liste.
-Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
+Für kleine Eingaben spielt die Laufzeitanalyse oft kaum eine Rolle, weil selbst langsame Verfahren schnell genug sind.
-<math>f(x) = \frac{1}{x} + x</math>
+Wichtig wird sie bei großen Datenmengen.
-So nähert sich die rot dargestellte Funktion <math>\color{red}{f(x)}</math> für große <math>x</math> der grün dargestellten Asymptote <math>\color{green}{g(x) = x}</math> an.
+Die Frage lautet dann:
-Die Laufzeit wird in Abhängigkeit von der Länge <math>n</math> der Eingabe angegeben und für immer größer werdende <math>n</math> asymptotisch unter Verwendung der Landau-Notation (Groß-O-Notation) abgeschätzt.
+'''Wie wächst der Aufwand, wenn die Eingabe immer größer wird?'''
-In der Praxis ist die Laufzeitanalyse essenziell, um entscheiden zu können, ob ein Programm bei stark anwachsenden Datenmengen noch performant und wirtschaftlich betrieben werden kann.
+Genau das beschreibt die '''asymptotische Laufzeit'''.
-=== Abgrenzung ===
+Wenn sich die Laufzeit eines Algorithmus durch eine Funktion beschreiben lässt, z. B.
-Es ist wichtig zu betonen, was die asymptotische Laufzeitanalyse '''nicht''' leistet:
-Sie misst nicht den tatsächlichen Zeitaufwand (in Sekunden) eines implementierten Algorithmus auf einem spezifischen Computer für eine konkrete, endliche Eingabemenge.
+<math>f(x)=\frac{1}{x}+x</math>
+dann erkennt man für große <math>x</math>, dass der Anteil <math>\frac{1}{x}</math> immer kleiner wird.
+Das Verhalten der Funktion wird dann fast nur noch durch <math>x</math> bestimmt.
+Deshalb betrachtet man bei der Laufzeitanalyse nur das Verhalten für große Werte von <math>n</math>.
+Dieses Verhalten beschreibt man mit der '''Landau-Notation''' (Groß-O-Notation), z. B.:
+<math>\mathcal{O}(n)</math>, <math>\mathcal{O}(n^2)</math>, <math>\mathcal{O}(n \log n)</math>
+Damit kann man Algorithmen vergleichen, ohne von einer bestimmten Hardware abhängig zu sein.
+=== Wichtige Abgrenzung ===
+Die asymptotische Laufzeitanalyse gibt '''nicht''' an, wie viele Sekunden ein Programm wirklich benötigt.
+Sie beschreibt nur, '''wie stark der Aufwand wächst''', wenn die Eingabemenge größer wird.
+Das macht verschiedene Algorithmen vergleichbar.
 == Szenarien der Laufzeitabschätzung ==
-Man unterscheidet bei der Laufzeitabschätzung klassischerweise drei Varianten:
-* Das '''Worst-Case-Szenario''' (schlechtester Fall): Beschreibt diejenige Datenanordnung, die zu einer maximalen Durchlaufzeit des Algorithmus führt. Dies entspricht der oberen Schranke des Problems.
+Bei der Laufzeitanalyse betrachtet man meist drei Fälle:
-* 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) ==
+* '''Best Case''' (bester Fall):
-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.
+  Der Algorithmus arbeitet unter idealen Bedingungen und benötigt minimalen Aufwand.
-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:
+* '''Worst Case''' (schlechtester Fall):
+  Der Algorithmus trifft auf die ungünstigste Eingabe und benötigt maximalen Aufwand.
-<math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math>
+* '''Average Case''' (durchschnittlicher Fall):
+  Man betrachtet den durchschnittlichen Aufwand bei zufälligen Eingaben.
-Dabei ist:
+Diese drei Fälle helfen dabei, das Verhalten eines Algorithmus besser einzuschätzen.
-* <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.
+== Average-Case und Erwartungswert ==
-=== Beispiel: Average-Case der Linearen Suche ===
+Der Average-Case beschreibt die '''durchschnittliche Laufzeit'''.
-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:
+Mathematisch wird diese mit dem '''Erwartungswert''' berechnet:
-# 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}^{|E|} p_i \cdot t_i</math>
-<math>E(T) = \sum_{i=1}^{n} \left( \frac{1}{n} \cdot i \right)</math>
+Dabei gilt:
-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>t_i</math>: Laufzeit bei einer bestimmten Eingabe
+* <math>p_i</math>: Wahrscheinlichkeit dieser Eingabe
-<math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math>
+Der Erwartungswert ist also:
-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:
+'''Laufzeit × Wahrscheinlichkeit'''
-<math>E(T) = \frac{1}{n} \cdot \frac{n(n+1)}{2}</math>
+für alle möglichen Eingaben zusammengezählt.
-Durch Kürzen des <math>n</math> erhalten wir das finale Ergebnis:
+Oft nimmt man an, dass alle Eingaben gleich wahrscheinlich sind.
+Dann spricht man von einer '''Gleichverteilung'''.
-<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.
+=== Beispiel: Lineare Suche ===
-=== Indikatorvariablen und die Harmonische Reihe ===
+Bei der linearen Suche wird eine Liste von vorne nach hinten durchsucht.
-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:
+Steht das gesuchte Element:
-<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.
+* an Position 1 → 1 Vergleich
-* '''Schritt 1: Indikatorvariablen definieren'''
+* an Position 2 → 2 Vergleiche
-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>.
+* ...
+* an Position <math>n</math> → <math>n</math> Vergleiche
-* '''Schritt 2: Wahrscheinlichkeit ermitteln'''
+Wenn jede Position gleich wahrscheinlich ist, ergibt sich:
-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'''
+<math>E(T)=\frac{1}{n}\sum_{i=1}^{n} i</math>
-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>.
+Mit der Gaußschen Summenformel:
-'''Erkenntnis für Quicksort:'''
+<math>\sum_{i=1}^{n} i = \frac{n(n+1)}{2}</math>
-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.
+folgt:
+<math>E(T)=\frac{1}{n}\cdot\frac{n(n+1)}{2}=\frac{n+1}{2}</math>
+Im Durchschnitt benötigt die lineare Suche also etwa halb so viele Vergleiche wie im schlechtesten Fall.
+Für große <math>n</math> dominiert der Term <math>n</math>, daher gilt:
+<math>\mathcal{O}(n)</math>
 == Beispiel: Laufzeitanalyse von Insertion Sort ==
-Im Folgenden wird die Laufzeitanalyse beispielhaft anhand des [[Insertion-sort|Insertion Sorts]] (Sortieren durch Einfügen) durchgeführt. Wir betrachten eine mögliche Implementierung in der Programmiersprache [[Java]]. Der Algorithmus arbeitet mit einem [[Array]] als Datenstruktur und verwendet als [[Kontrollstruktur|Kontrollstrukturen]] [[Verzweigung|Verzweigungen]] und [[Schleife|Schleifen]].
-<syntaxhighlight lang="java">
+Beim [[Insertion-sort|Insertion Sort]] wird jedes neue Element an der richtigen Stelle in den bereits sortierten Teil eingefügt.
-public void sortierenEinfuegen_MC() {
-    int v, i, j;
+=== Best Case ===
-    for (i = 1; i < zSortfeld.length; i++) {
-        c++; // Zähler für Vergleiche
+Der beste Fall liegt vor, wenn die Liste bereits sortiert ist:
-        if (zSortfeld[i] < zSortfeld[i - 1]) {
-            v = zSortfeld[i];
+<code>[1,2,3,4,5]</code>
-            j = i;
-            do {
+Dann genügt pro Element ein Vergleich.
-                zSortfeld[j] = zSortfeld[j - 1];
-                j--;
+Bei <math>n</math> Elementen:
-            } while ((j > 0) && (zSortfeld[j - 1] > v));
-            zSortfeld[j] = v;
+<math>T(n)=n-1</math>
-        }
-        printAnalyse(i);
+Das Wachstum ist linear:
-    }
-}
+<math>\mathcal{O}(n)</math>
-</syntaxhighlight>
+=== Worst Case ===
+Der schlechteste Fall liegt vor, wenn die Liste rückwärts sortiert ist:
+<code>[5,4,3,2,1]</code>
+Dann muss jedes neue Element an den Anfang verschoben werden.
+Die Anzahl der Vergleiche ist:
+<math>1+2+3+\dots+(n-1)</math>
+Mit Gauß:
+<math>\frac{n(n-1)}{2}</math>
+Das ergibt quadratisches Wachstum:
+<math>\mathcal{O}(n^2)</math>
+=== Average Case ===
+Bei zufälliger Reihenfolge liegt das neue Element im Durchschnitt ungefähr in der Mitte des bereits sortierten Bereichs.
+Daher braucht man im Mittel etwa halb so viele Vergleiche wie im Worst Case:
+<math>\frac{1}{2}\cdot\frac{n(n-1)}{2}</math>
+Das ist ebenfalls proportional zu <math>n^2</math>.
-Wir analysieren nun die drei Szenarien für eine Liste mit <math>n</math> Elementen und betrachten zunächst den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Den konstanten Zeitverbrauch für einen einzelnen Vergleich bezeichnen wir allgemein mit <math>c</math>.
+Deshalb gilt auch hier:
-=== 1. Best-Case-Szenario (Bester Fall) ===
+<math>\mathcal{O}(n^2)</math>
-Ein Best-Case-Szenario liegt vor, wenn die Liste bereits aufsteigend sortiert ist, beispielsweise:
-<code>[0, 2, 3, 5, 7, 11]</code>
-* '''Verhalten:''' Die äußere <code>for</code>-Schleife durchläuft das Array <math>n - 1</math> Mal. Da das aktuell betrachtete Element stets größer oder gleich seinem Vorgänger ist, ist die Bedingung der <code>if</code>-Anweisung (<code>zSortfeld[i] < zSortfeld[i - 1]</code>) '''immer falsch'''. Die innere <code>do-while</code>-Schleife wird somit nie betreten.
+Der konstante Faktor ist zwar kleiner als im Worst Case, die '''Komplexitätsklasse''' bleibt aber gleich.
-* '''Aufwand:''' Es findet pro Durchlauf der äußeren Schleife exakt ein Vergleich statt. Der Gesamtaufwand lautet <math>c \cdot (n - 1)</math>.
-* '''Komplexität:''' Für sehr große <math>n</math> wächst der Aufwand linear zur Eingabemenge. Der Insertion Sort hat im Best-Case somit eine Zeitkomplexität von <math>\mathcal{O}(n)</math>.
-=== 2. Worst-Case-Szenario (Schlechtester Fall) ===
-Ein Worst-Case-Szenario liegt vor, wenn die Liste in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise:
-<code>[11, 7, 5, 3, 2, 0]</code>
-* '''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.
+== Wichtige Erkenntnis ==
-* '''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>.
-** Dies setzt sich fort bis zum letzten Durchlauf, der <math>n - 1</math> Vergleiche erfordert. Aufwand: <math>c \cdot (n - 1)</math>.
-Der Gesamtaufwand für die Vergleiche entspricht einer [[Arithmetische-reihe|arithmetischen Reihe]] (Gaußsche Summenformel):
+Bei der Groß-O-Notation interessieren nur:
-<math>c \cdot (1 + 2 + 3 + \dots + (n - 1)) = c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n</math>
-[[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]]
+* das grundsätzliche 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>.
+* die höchste Potenz.
-* '''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>.
-=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
+Konstanten werden ignoriert.
-Das Average-Case-Szenario geht von einer völlig zufälligen Verteilung der Werte im Array aus.
-* '''Verhalten:''' Im Durchschnitt ist das betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also nicht bis ganz an den Anfang, sondern im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben.
+Beispiele:
-* '''Aufwand:''' Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst-Case in etwa. Der rechnerische Aufwand läge grob bei <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.
-* '''Komplexität:''' Da in der asymptotischen Landau-Notation konstante Faktoren (wie die Halbierung) ignoriert werden, da primär die höchste Potenz das Wachstum dominiert, bleibt es auch hier bei einem quadratischen Wachstum. Die Zeitkomplexität im Average-Case lautet ebenfalls <math>\mathcal{O}(n^2)</math>.
-=== Einfluss weiterer Operationen ===
+* <math>3n</math> → <math>\mathcal{O}(n)</math>
-Wie beeinflussen Lese- und Schreiboperationen (das tatsächliche Verschieben der Werte im Array) die Zeitkomplexität? Für das Verschieben käme lediglich ein konstanter Aufwand je Vergleich hinzu. Nennen wir diesen Aufwand <math>v</math>. Die angepasste Worst-Case-Funktion lautet dann beispielsweise:
+* <math>\frac{1}{2}n^2</math> → <math>\mathcal{O}(n^2)</math>
-<math>\frac{v+c}{2}n^2 - \frac{v+c}{2}n</math>
+Deshalb können zwei Algorithmen unterschiedlich schnell sein, aber trotzdem dieselbe Komplexitätsklasse besitzen.
-Auch hier gilt: Für sehr große <math>n</math> werden der niederwertige Term und die konstanten Faktoren ignoriert. Es bleibt bei der Erkenntnis, dass Lese- und Schreibzugriffe die fundamentale Komplexitätsklasse nicht verändern. Das Laufzeitverhalten bleibt asymptotisch in der Klasse <math>\mathcal{O}(n^2)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]

Laufzeitanalyse: Unterschied zwischen den Versionen