Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenFreitag, 14. August 2020 

Asymptotische Laufzeit


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
In der theoretischen Informatik speziell in der Komplexitätstheorie bezeichnet die asymptotische Laufzeit die Anzahl der Schritte die ein Automat (z.B. eine Turingmaschine ) zur Ausführung eines Algorithmus bei gegebener benötigt bis ein Endzustand erreicht und eine fertig berechnet ist. Die Laufzeit wird oft Abhängigkeit von der Größe <math>n</math> der Eingabe und für große <math>n</math> asymptotisch unter Verwendung des Landau-Symbols abgeschätzt.

Man unterscheidet die folgenden Varianten zur

  • Die worst case -Laufzeit ( engl. schlechtester Fall ) gibt an wie lang der Algorithmus braucht. Für viele Algorithmen gibt es nur Eingaben die diese worst case-Laufzeit erreichen weshalb nicht unbedingt eine realistische Abschätzung ist. Handelt sich aber um Echtzeit-Systeme so muss die worst case-Laufzeit natürlich werden.
  • Die average case -Laufzeit (engl. durchschnittlicher Fall ) gibt die erwartete Laufzeit bei einer Gleichverteilung der Eingaben an. Da man allerdings realen Programmen selten von der Gleichverteilung der ausgehen kann ist auch diese Abschätzung nur nutzbar.
  • Die best case -Laufzeit (engl. bester Fall ) gibt an wie lang der Algorithmus jedem Fall braucht also selbst für die auf denen er ideal arbeitet. Diese untere zur Lösung des Problems wird nur recht angegeben da sie nur für wenige Fälle und die best case-Laufzeit natürlich in der die schlechteren Fälle enthalten ist.

  • Für eine realistische Abschätzung der Laufzeit sich bei komplexen Algorithmen die amortisierte Analyse die Kosten des Algorithmus über die komplette betrachtet und nicht nur die Kosten einzelnen Bei Fibonacci-Heaps beispielsweise gibt es zwar Sortieroperationen die sein können aber diese kommen nur einmal Durchlauf des Algorithmus vor in allen folgenden ist der Heap bereits "fast sortiert" und Sortierschritt ist billig. Das Problem an der Analyse ist dass sie nicht einfach durchzuführen da man zunächst eine Funktion entwickeln muss das Verhalten der Datenstruktur möglichst genau modelliert.

In der praktischen Informatik bezeichnet Laufzeit ( runtime ) außerdem die Zeitspanne der Ausführung eines Programms siehe dazu Laufzeit (Informatik) .



Bücher zum Thema Asymptotische Laufzeit

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Asymptotische_Laufzeit.html">Asymptotische Laufzeit </a>