Laufzeitanalyse: Unterschied zwischen den Versionen

(4 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt)

Zeile 1:

== Einführung ==

[[Datei:Laufzeitanalyse asymptotisch.png|mini]]

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.

Zeile 11:

Zeile 12:

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.

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.

== Szenarien ==

Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

* 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 '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.

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

== 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]].

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>

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

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.

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:

[[Datei:Asymptote an quadratische Funktion2.png|mini]]

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:

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:

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>.

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:

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:

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>.

[[Kategorie:Programmierung]]

[[Kategorie:AHR_I_Informatik_LK]]

@@ Zeile 1: / Zeile 1: @@
 == Einführung ==
+[[Datei:Laufzeitanalyse asymptotisch.png|mini]]
 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.
@@ Zeile 11: / Zeile 12: @@
 In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.
+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.
+== Szenarien ==
+Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:
+* 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 '''average-case-Szenario''' (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
+* 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.
+== 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">
+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>
+Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:
+[11,7,5,3,2,0]
+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.
+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:
+<math>c⋅*(1+2+3+⋯+(n−1))</math>
+[[Datei:Asymptote an quadratische Funktion2.png|mini]]
+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:
+<math>c⋅*(n−1+1)*((n−1)/2)=c*n2/2 − c*n/2</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:
+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>.
+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>(v+c) * n2/2 − (v+c)* n/2</math>
+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:
+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>.
+[[Kategorie:Programmierung]]
+[[Kategorie:AHR_I_Informatik_LK]]