Laufzeitanalyse: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) |
Thomas (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
== Einführung == | == 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. | 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. | 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]]. | |||