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 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:

• die Aggregat-Methode
• die Account-Methode (auch Bankkonto-Paradigma genannt)
• die Potentialfunktion-Methode

Siehe auch: Komplexitätstheorie, Graphentheorie, Zeitkomplexität, Effizienz, Programmoptimierung

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 17: Amortized Analysis, pp.405–430.