Amortisierte Laufzeitanalyse

In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die durchschnittlichen Kosten von Operationen in Folgen. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht nur die maximalen Kosten der einzelnen Schritte betrachtet, sondern es wird der Worst Case aller Operationen im gesamten Durchlauf des Algorithmus analysiert. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einer besseren oberen Schranke führen, da es häufig Operationen gibt, die zwar teuer sein können, dieser „teure“ Fall aber nur einmal oder wenige Male pro Ablauf des Algorithmus vorkommt und alle anderen Fälle relativ günstig sind.

Bei einer allgemeinen Laufzeitanalyse muss man vom teuersten Fall ausgehen, da dieser nicht insgesamt ausgeschlossen werden darf, aber da der Fall selten vorkommt, ist die damit berechnete Laufzeit schlechter als die tatsächlich anzunehmende.

Bei der amortisierten Laufzeitanalyse gibt es prinzipiell drei unterschiedliche Methoden:

Siehe auch

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Amortisierte Analyse — In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die durchschnittlichen Kosten von Operationen in Folgen. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht nur die maximalen Kosten der einzelnen Schritte… …   Deutsch Wikipedia

  • Asymptotische Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Laufzeitkomplexität — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Worst-Case-Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Amortisationsdauer — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

  • Amortisationsfrist — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

  • Amortisationszeit — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

  • Amortisieren — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

  • Amortisiert — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

  • Amortisierung — Der Begriff Amortisation (von französisch: amortir, tilgen) bezeichnet heute den Prozess, in dem anfängliche Aufwendungen für ein Objekt durch dadurch entstehende Erträge gedeckt werden. Die Dauer dieses Prozesses wird Amortisationszeit genannt.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”