FLBK-Wiki

Laufzeitanalyse: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.195 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Markierung: Zurückgesetzt
 
(10 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]]
[[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]]
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?“'''
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. 
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.
Die Eingabegröße wird meist mit <math>n</math> bezeichnet.


Beispiel:
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.
* 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.


Für kleine Eingaben spielt die Laufzeitanalyse oft kaum eine Rolle, weil selbst langsame Verfahren schnell genug sind. 
Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
Wichtig wird sie bei großen Datenmengen.
<math>f(x) = \frac{1}{x} + x</math>


Die Frage lautet dann:
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.


'''Wie wächst der Aufwand, wenn die Eingabe immer größer wird?'''
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.


Genau das beschreibt die '''asymptotische Laufzeit'''.
=== 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.
Wenn sich die Laufzeit eines Algorithmus durch eine Funktion beschreiben lässt, z. B.
 
<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 ==
== Szenarien der Laufzeitabschätzung ==
Da Algorithmen je nach Vorsortierung der Daten unterschiedlich schnell arbeiten, unterscheidet man drei klassische Fälle:


Bei der Laufzeitanalyse betrachtet man meist drei Fälle:
* 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).
* 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.


* '''Best Case''' (bester Fall): 
== Mathematische Berechnung des Average-Case ==
  Der Algorithmus arbeitet unter idealen Bedingungen und benötigt minimalen Aufwand.
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.


* '''Worst Case''' (schlechtester Fall):
Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:
  Der Algorithmus trifft auf die ungünstigste Eingabe und benötigt maximalen Aufwand.


* '''Average Case''' (durchschnittlicher Fall): 
<math>E(T) = \sum_{i=1}^{|F|} p_i \cdot t_i</math>
  Man betrachtet den durchschnittlichen Aufwand bei zufälligen Eingaben.


Diese drei Fälle helfen dabei, das Verhalten eines Algorithmus besser einzuschätzen.
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.


== Average-Case und Erwartungswert ==
Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.


Der Average-Case beschreibt die '''durchschnittliche Laufzeit'''.
=== 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.


Mathematisch wird diese mit dem '''Erwartungswert''' berechnet:
* '''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}^{|E|} p_i \cdot t_i</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>


Dabei gilt:
Wir klammern <math>\frac{1}{n}</math> aus:


* <math>t_i</math>: Laufzeit bei einer bestimmten Eingabe
<math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math>
* <math>p_i</math>: Wahrscheinlichkeit dieser Eingabe


Der Erwartungswert ist also:
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>:


'''Laufzeit × Wahrscheinlichkeit'''
<math>E(T) = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} = \frac{1}{2}n + \frac{1}{2}</math>


für alle möglichen Eingaben zusammengezählt.
'''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>.


Oft nimmt man an, dass alle Eingaben gleich wahrscheinlich sind. 
== Laufzeitanalyse von Insertion Sort ==
Dann spricht man von einer '''Gleichverteilung'''.
Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an.  


---
<syntaxhighlight lang="java">
public void sortierenEinfuegen_MC() {
    int v, i, j;
    for (i = 1; i < zSortfeld.length; i++) {
        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>


=== Beispiel: Lineare Suche ===
Wir analysieren eine Liste mit <math>n</math> Elementen. Den Zeitverbrauch für einen einzelnen Vergleich nennen wir <math>c</math>.


Bei der linearen Suche wird eine Liste von vorne nach hinten durchsucht.
=== 1. Best-Case-Szenario (Bester Fall) ===
Die Liste ist bereits perfekt aufsteigend sortiert (z. B. <code>[0, 2, 3, 5, 7]</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.
* '''Komplexität:''' Der Aufwand wächst wie eine Gerade (linear). Die Komplexität ist <math>\mathcal{O}(n)</math>.


Steht das gesuchte Element:
=== 2. Worst-Case-Szenario (Schlechtester Fall) ===
Die Liste ist exakt falsch herum sortiert (z. B. <code>[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>.


* an Position 1 → 1 Vergleich
Wie bei der linearen Suche hilft uns hier die Gaußsche Summenformel:
* an Position 2 → 2 Vergleiche
<math>c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n</math>
* ...
* an Position <math>n</math> → <math>n</math> Vergleiche
 
Wenn jede Position gleich wahrscheinlich ist, ergibt sich:
 
<math>E(T)=\frac{1}{n}\sum_{i=1}^{n} i</math>
 
Mit der Gaußschen Summenformel:
 
<math>\sum_{i=1}^{n} i = \frac{n(n+1)}{2}</math>
 
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 ==
 
Beim [[Insertion-sort|Insertion Sort]] wird jedes neue Element an der richtigen Stelle in den bereits sortierten Teil eingefügt.
 
=== Best Case ===
 
Der beste Fall liegt vor, wenn die Liste bereits sortiert ist:
 
<code>[1,2,3,4,5]</code>
 
Dann genügt pro Element ein Vergleich.
 
Bei <math>n</math> Elementen:
 
<math>T(n)=n-1</math>
 
Das Wachstum ist linear:
 
<math>\mathcal{O}(n)</math>
 
 
=== 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>.
 
Deshalb gilt auch hier:
 
<math>\mathcal{O}(n^2)</math>
 
Der konstante Faktor ist zwar kleiner als im Worst Case, die '''Komplexitätsklasse''' bleibt aber gleich.


[[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]]
* '''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>.


== Wichtige Erkenntnis ==
=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
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.


Bei der Groß-O-Notation interessieren nur:
* '''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>):


* das grundsätzliche Wachstum,
<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>
* die höchste Potenz.


Konstanten werden ignoriert.
Wir klammern <math>\frac{1}{2}</math> aus:


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


* <math>3n</math> → <math>\mathcal{O}(n)</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>\frac{1}{2}n^2</math> → <math>\mathcal{O}(n^2)</math>


Deshalb können zwei Algorithmen unterschiedlich schnell sein, aber trotzdem dieselbe Komplexitätsklasse besitzen.
<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:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:AHR_I_Informatik_LK]]
Abgerufen von „https://wiki.flbk-hamm.de/Laufzeitanalyse“