Amortisierte Laufzeitanalyse
- 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
