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
 
(18 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini]]
[[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]]
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe.  Die Eingabe wird auch als Problemgröße bezeichnet.
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 Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.
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.


Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math>
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.


Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an.
Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
<math>f(x) = \frac{1}{x} + x</math>


Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.  
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.


In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.
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.
Abgrenzung
Abgrenzend kann gesagt werden, dass die Laufzeitanalyse folgendes nicht betrachtet:


Den Zeitaufwand eines implementierten Algorithmus auf einem bestimmten Computer für eine konkrete endliche Eingabemenge.  
=== 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.


== Szenarien ==
== Szenarien der Laufzeitabschätzung ==
Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:
Da Algorithmen je nach Vorsortierung der Daten unterschiedlich schnell arbeiten, unterscheidet man drei klassische Fälle:


* Das '''worst-case-szenario''' (engl. schlechtester Fall) beschreibt die Problemgröße, die zu einer maximal langen Durchlaufzeit eines Algorithmus führt und entspricht der oberen Schranke zur Lösung eines Problems.
* 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 '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
* Das '''Best-Case-Szenario''' (Bester Fall): Die Daten liegen optimal vor (z. B. bereits sortiert). Der Algorithmus ist minimal schnell fertig.
* Das '''best-case-Szenario''' (engl. bester Fall)   beschreibt die Problemgröße die zu einer minimalen Durchlaufzeit eines Algorithmus führt. Dies entspricht der untere Schranke zur Lösung eines Problems.
* 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.
 
== 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.
 
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}^{|F|} p_i \cdot t_i</math>
 
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.
 
Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.
 
=== 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.
 
* '''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) = \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>
 
Wir klammern <math>\frac{1}{n}</math> aus:
 
<math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math>
 
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} = \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>.
 
== Laufzeitanalyse von Insertion Sort ==
Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort|Insertion Sort]] (Sortieren durch Einfügen) an.  


== Beispiel ==
Im Folgenden wird die Laufzeitanalyse anhand des [[Insertion-sort|Insertionsorts]] praktisch durchgeführt. Wir betrachten den Insertionsort anhand einer möglichen 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">
<syntaxhighlight lang="java">
public void sortierenEinfuegen_MC() {
public void sortierenEinfuegen_MC() {
     int v, i, j;
     int v, i, j;
     for (i = 1; i < zSortfeld.length; i++) {
     for (i = 1; i < zSortfeld.length; i++) {
        c++; // Zähler für Vergleiche
         if (zSortfeld[i] < zSortfeld[i - 1]) {
         if (zSortfeld[i] < zSortfeld[i - 1]) {
             v = zSortfeld[i];
             v = zSortfeld[i];
Zeile 45: Zeile 79:
</syntaxhighlight>
</syntaxhighlight>


Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:
Wir analysieren eine Liste mit <math>n</math> Elementen. Den Zeitverbrauch für einen einzelnen Vergleich nennen wir <math>c</math>.


[11,7,5,3,2,0]
=== 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>.


Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Diesen Zeitverbrauchen kennen wir nicht und geben ihn allgemein durch die Konstante c an. Die Anzahl der zu sortierenden Elemente entspricht der Variablen n.  
=== 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>.


Beim ersten äußeren [[Schleife]]ndurchlauf gilt für den Zeitaufwand c*1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe [[Insertion-sort|InsertionSort]]) der Datenstruktur.  Beim zweiten Durchlauf der äußeren [[Schleife]] benötigen wir zwei Vergleiche, c * 2. Beim dritte Mal, c * 3 bis zum letzten Mal, wenn <math> c * n-1 </math>. Es gilt also:
Wie bei der linearen Suche hilft uns hier die Gaußsche Summenformel:
<math>c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n</math>


<math>c⋅*(1+2+3+⋯+(n−1))</math>
[[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>.


[[Datei:Asymptote an quadratische Funktion2.png|mini]]
=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:
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.


<math>c⋅*(n−1+1)*((n−1)/2)=c*n​2​​/2 − c*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>.
* '''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>):


Für sehr große n können  wir den niederwertigen Term n/2 und die konstanten Faktoren c und  1/2 verwerfen, so dass gilt:
<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>


Für sehr große n verhält sich <math> C(n)</math> asymptotisch wie n2. Oder anders ausgedrückt <math> C(n)</math> liegt in der Klasse <math>O(n2)</math>.
Wir klammern <math>\frac{1}{2}</math> aus:


Und wie beeinflussen die anderen Operationen wie Lesen und Schreiben, die zum Vertauschen der Werte benötigt werden die Zeitkomplexität? Für das Vertauschen der Werte würde nur ein konstanter Aufwand je Vergleich hinzukommen. Wir nennen ihn v und passen unsere Funktion entsprechend an:
<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>


<math>(v+c) * n​2​​/2 − (v+c)* n/2</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:


Und wieder gilt, für sehr große n können wir den niederwertigen Term <math>(v+c)* n/2 </math>und die konstanten Faktoren v,c und 1/2 verwerfen, so dass immer noch gilt:
<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>


Für sehr große n verhält sich <math>C(n) </math>asymptotisch wie n2. Oder anders ausgedrückt <math>C(n) </math>liegt in der Klasse <math>O(n2)</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“