Laufzeitanalyse: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 1: / Zeile 1: @@
 == 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 reale Ausführungszeit stark von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine, hardwareunabhängige Betrachtung die Anzahl der [[Anweisung|Befehle]] (Operationen) analysiert, die ein Algorithmus zur Lösung eines Problems benötigt. Diese Anzahl ist abhängig von der Eingabe, deren Umfang auch als '''Problemgröße''' (oft <math>n</math>) bezeichnet wird.
+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.
-Für kleine Eingabemengen ist die Analyse häufig von geringerer Bedeutung, da auch ineffiziente [[Algorithmus|Algorithmen]] hier oft befriedigend schnelle Ergebnisse liefern. Entscheidend ist die Betrachtung für sehr große Problemgrößen, insbesondere unter ungünstigen Startbedingungen (Worst-Case). 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]]).
+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]]).
 Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise:
@@ Zeile 18: / Zeile 18: @@
 Sie misst nicht den tatsächlichen Zeitaufwand (in Sekunden) eines implementierten Algorithmus auf einem spezifischen Computer für eine konkrete, endliche Eingabemenge.
-== Szenarien ==
+== Szenarien der Laufzeitabschätzung ==
 Man unterscheidet bei der Laufzeitabschätzung klassischerweise drei Varianten:
-* Das '''Worst-Case-Szenario''' (schlechtester Fall): Beschreibt die Startanordnung der Daten, die zu einer maximalen Durchlaufzeit des Algorithmus führt. Dies entspricht der oberen Schranke des Problems.
+* 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 die Problemgröße und Datenanordnung, die zu einer mittleren (erwarteten) Durchlaufzeit führt.
+* 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 die Datenanordnung, die zu einer minimalen Durchlaufzeit führt (z. B. eine bereits sortierte Liste). Dies entspricht der unteren Schranke.
+* 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.
 == Beispiel: Laufzeitanalyse von Insertion Sort ==
-Im Folgenden wird die Laufzeitanalyse beispielhaft anhand des [[Insertion-sort|Insertion Sorts]] 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]].
+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">
@@ Zeile 47: / Zeile 47: @@
 </syntaxhighlight>
-Ein Worst-Case-Szenario für den Insertion Sort ist eine Liste, die in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise:
+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>.
-<code>[11, 7, 5, 3, 2, 0]</code>
+=== 1. Best-Case-Szenario (Bester Fall) ===
+Ein Best-Case-Szenario liegt vor, wenn die Liste bereits aufsteigend sortiert ist, beispielsweise:
+<code>[0, 2, 3, 5, 7, 11]</code>
-Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Wir bezeichnen diesen konstanten Zeitverbrauch für einen einzelnen Vergleich allgemein mit <math>c</math>. Die Anzahl der zu sortierenden Elemente sei <math>n</math>.
+* '''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.
+* '''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>.
-* Beim ersten Durchlauf der äußeren [[Schleife]] vergleichen wir nur die 7 mit der 11. Aufwand: <math>c \cdot 1</math>. Die 7 wird einsortiert.
+=== 2. Worst-Case-Szenario (Schlechtester Fall) ===
-* Beim zweiten Durchlauf müssen wir das nächste Element mit den beiden bereits sortierten Elementen vergleichen. Aufwand: <math>c \cdot 2</math>.
+Ein Worst-Case-Szenario liegt vor, wenn die Liste in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise:
-* Dies setzt sich fort bis zum letzten Durchlauf, der <math>n - 1</math> Vergleiche erfordert. Aufwand: <math>c \cdot (n - 1)</math>.
+<code>[11, 7, 5, 3, 2, 0]</code>
-Der Gesamtaufwand für die Vergleiche lautet also:
+* '''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.
-<math>c \cdot (1 + 2 + 3 + \dots + (n - 1))</math>
+* '''Aufwand:'''
+  * 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>.
-[[Datei:Asymptote an quadratische Funktion2.png|mini]]
+Der Gesamtaufwand für die Vergleiche entspricht einer [[Arithmetische-reihe|arithmetischen Reihe]] (Gaußsche Summenformel):
-Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]] (angelehnt an den Gaußschen Summensatz), die bis <math>n - 1</math> läuft. Unter Verwendung der entsprechenden Summenformel erhalten wir:
+<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>
-<math>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]]
+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:''' Der Aufwand wächst quadratisch. Der Insertion Sort hat im Worst-Case somit eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.
-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>. Daraus folgt:
+=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
+Das Average-Case-Szenario geht von einer völlig zufälligen Verteilung der Werte im Array aus.
-Für sehr große <math>n</math> verhält sich der Aufwand <math>C(n)</math> asymptotisch wie <math>n^2</math>. Anders ausgedrückt: <math>C(n)</math> liegt in der Komplexitätsklasse <math>\mathcal{O}(n^2)</math>.
+* '''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.
+* '''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 (Lesen/Schreiben):'''
+=== Einfluss weiterer Operationen ===
-Wie beeinflussen Lese- und Schreiboperationen (das Verschieben der Werte) 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 Funktion lautet dann:
+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>
-Auch hier gilt: Für sehr große <math>n</math> können der niederwertige Term <math>\frac{v+c}{2}n</math> und der konstante Faktor <math>\frac{v+c}{2}</math> ignoriert werden. Es bleibt bei der Erkenntnis:
+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>.
-Das Laufzeitverhalten <math>C(n)</math> liegt asymptotisch weiterhin in der Klasse <math>\mathcal{O}(n^2)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]