FLBK-Wiki

Laufzeitanalyse: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.195 Bearbeitungen
VisuellWikitext
Markierung: Zurückgesetzt
 
(12 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]]
[[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.
Die Laufzeitanalyse untersucht die sogenannte Zeitkomplexität eines [[Algorithmus]]. Man stellt sich dabei im Kern die Frage: '''„Wie verhält sich die Rechenzeit, wenn die Menge der zu verarbeitenden Daten extrem groß 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]]).
Da die echte Ausführungszeit (in Sekunden) stark vom jeweiligen Computer abhängt, misst man stattdessen die Anzahl der elementaren [[Anweisung|Befehle]] (z. B. Vergleiche oder Tauschoperationen). Diese Anzahl hängt von der Größe der Eingabemenge ab, die in der Informatik meist als '''Problemgröße <math>n</math>''' bezeichnet wird.
 
Für kleine Datenmengen (z. B. eine Liste mit 10 Elementen sortieren) ist fast jeder Algorithmus schnell genug. Spannend wird es erst bei sehr großen Datenmengen (z. B. Millionen von Kundendatensätzen). Hier betrachtet man die sogenannte asymptotische [[Programmausführung|Laufzeit]]. Sie beschreibt das Verhalten des Algorithmus, wenn die Datenmenge <math>n</math> theoretisch ins Unendliche wächst.


Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
Zeile 10: Zeile 12:
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.
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 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.
Die Laufzeit wird mit der sogenannten Landau-Notation (Groß-O-Notation, z. B. <math>\mathcal{O}(n^2)</math>) abgeschätzt. Dabei werden konstante Vorfaktoren (wie <math>\frac{1}{2}</math>) oder kleinere Summanden ignoriert, da bei riesigen Datenmengen nur noch der dominierende Teil der Funktion das Wachstum bestimmt.


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.
=== Was die Laufzeitanalyse NICHT ist ===
 
Sie misst '''nicht''' den tatsächlichen Zeitaufwand in Millisekunden auf einem echten Computer. Sie ist ein theoretisches Modell, um Algorithmen hardwareunabhängig miteinander vergleichen zu können.
=== Abgrenzung ===
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.


== Szenarien der Laufzeitabschätzung ==
== Szenarien der Laufzeitabschätzung ==
Man unterscheidet bei der Laufzeitabschätzung klassischerweise drei Varianten:
Da Algorithmen je nach Vorsortierung der Daten unterschiedlich schnell arbeiten, unterscheidet man drei klassische Fälle:
 
* 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.
* 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) ==
* Das '''Worst-Case-Szenario''' (Schlechtester Fall): Die Daten liegen so ungünstig vor, dass der Algorithmus maximal lange braucht. Dies liefert eine absolute Sicherheitsgarantie (obere Schranke).
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.  
* Das '''Best-Case-Szenario''' (Bester Fall): Die Daten liegen optimal vor (z. B. bereits sortiert). Der Algorithmus ist minimal schnell fertig.
* Das '''Average-Case-Szenario''' (Durchschnittlicher Fall): Beschreibt die zu erwartende Laufzeit bei völlig zufällig gemischten Daten. Dies ist oft das realistischste Szenario in der Praxis.


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:
== Mathematische Berechnung des Average-Case ==
Oft wird fälschlicherweise angenommen, der Average-Case sei einfach „die Hälfte des Worst-Case“. Das ist mathematisch ungenau. Tatsächlich berechnet man den Average-Case mit Hilfe der Stochastik: Er entspricht dem '''Erwartungswert''' der Laufzeit.


<math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math>
Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:


Dabei ist:
<math>E(T) = \sum_{i=1}^{|F|} p_i \cdot t_i</math>
* <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.
Hierbei bedeuten die Variablen:
* <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.


=== Beispiel: Average-Case der Linearen Suche ===
Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.
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:
=== Average-Case der Linearen Suche ===
# Das gesuchte Element <math>x</math> befindet sich definitiv im Array.
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.
# 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:
* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Die Wahrscheinlichkeit, dass unsere Zahl an Position 1, 2 oder <math>n</math> steht, ist jeweils <math>p = \frac{1}{n}</math>.
* '''Schritt 2: Schritte zählen.''' Steht die Zahl an Position 1, brauchen wir 1 Vergleich. An Position 2 brauchen wir 2 Vergleiche. An Position <math>n</math> brauchen wir <math>n</math> Vergleiche.
* '''Schritt 3: Erwartungswert berechnen.''' Wir setzen dies in die Formel ein:


<math>E(T) = \sum_{i=1}^{n} \left( \frac{1}{n} \cdot i \right)</math>
<math>E(T) = \frac{1}{n}\cdot 1 + \frac{1}{n}\cdot 2 + \dots + \frac{1}{n}\cdot n = \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:
Wir klammern <math>\frac{1}{n}</math> aus:


<math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math>
<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:
Die Summe der Zahlen von 1 bis <math>n</math> lässt sich mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>:
 
<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{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} = \frac{1}{2}n + \frac{1}{2}</math>


<math>E(T) = \frac{n+1}{2} = \frac{1}{2}n + \frac{1}{2}</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>.


'''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.  
== Laufzeitanalyse von Insertion Sort ==
Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an.  


=== 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">
<syntaxhighlight lang="java">
public int findMax(int[] A) {
public void sortierenEinfuegen_MC() {
     int max = A[0];
     int v, i, j;
     for (int i = 1; i < A.length; i++) {
     for (i = 1; i < zSortfeld.length; i++) {
         if (A[i] > max) {
         if (zSortfeld[i] < zSortfeld[i - 1]) {
             max = A[i]; // Update-Operation
             v = zSortfeld[i];
            j = i;
            do {
                zSortfeld[j] = zSortfeld[j - 1];
                j--;
            } while ((j > 0) && (zSortfeld[j - 1] > v));
            zSortfeld[j] = v;
         }
         }
        printAnalyse(i);
     }
     }
    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 ==
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">
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>
</syntaxhighlight>


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>.
Wir analysieren eine Liste mit <math>n</math> Elementen. Den Zeitverbrauch für einen einzelnen Vergleich nennen wir <math>c</math>.


=== 1. Best-Case-Szenario (Bester Fall) ===
=== 1. Best-Case-Szenario (Bester Fall) ===
Ein Best-Case-Szenario liegt vor, wenn die Liste bereits aufsteigend sortiert ist, beispielsweise:
Die Liste ist bereits perfekt aufsteigend sortiert (z. B. <code>[0, 2, 3, 5, 7]</code>).
<code>[0, 2, 3, 5, 7, 11]</code>
* '''Verhalten:''' Da jedes Element schon größer als sein Vorgänger ist, ist die <code>if</code>-Bedingung immer falsch. Die innere <code>do-while</code>-Schleife wird ignoriert.
 
* '''Aufwand:''' Wir machen exakt einen Vergleich pro Element in der äußeren Schleife. Das ergibt <math>c \cdot (n - 1)</math> Vergleiche.
* '''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.
* '''Komplexität:''' Der Aufwand wächst wie eine Gerade (linear). Die Komplexität ist <math>\mathcal{O}(n)</math>.
* '''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) ===
=== 2. Worst-Case-Szenario (Schlechtester Fall) ===
Ein Worst-Case-Szenario liegt vor, wenn die Liste in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise:
Die Liste ist exakt falsch herum sortiert (z. B. <code>[7, 5, 3, 2, 0]</code>).
<code>[11, 7, 5, 3, 2, 0]</code>
* '''Verhalten:''' Die <code>if</code>-Bedingung ist immer wahr. Jedes Element muss durch die innere Schleife komplett bis an den Anfang der Liste getauscht werden.
* '''Aufwand:''' Beim 1. Durchlauf machen wir 1 Vergleich. Beim 2. Durchlauf 2 Vergleiche. Beim letzten Durchlauf <math>n-1</math> Vergleiche. Wir müssen also wieder addieren: <math>1 + 2 + 3 + \dots + (n-1)</math>.


* '''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.
Wie bei der linearen Suche hilft uns hier die Gaußsche Summenformel:
* '''Aufwand:''' 
<math>c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n</math>
** 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):
<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]]
[[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:''' Für extrem große <math>n</math> dominiert das <math>n^2</math> alles andere. Wir ignorieren den Faktor <math>\frac{c}{2}</math> und den kleineren Teil <math>n</math>. Das Wachstum ist quadratisch, also <math>\mathcal{O}(n^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>.


=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
Das Average-Case-Szenario geht von einer völlig zufälligen Verteilung der Werte im Array aus.
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.
 
* '''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>.
* '''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:


* '''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.
<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>
* '''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 ===
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:
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{v+c}{2}n^2 - \frac{v+c}{2}n</math>
<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>


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>.
'''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:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:AHR_I_Informatik_LK]]
Abgerufen von „https://wiki.flbk-hamm.de/Laufzeitanalyse“