Laufzeitanalyse: Unterschied zwischen den Versionen

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

Zeile 26:

== 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 26: / Zeile 26: @@
 == 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]]