Amortisierte Laufzeitanalyse

In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht die maximalen Kosten einzelner Schritte betrachtet, sondern es wird die obere Schranke aller Summen der Laufzeiten mehrerer Durchläufe der Operation analysiert und diese Summen durch die Anzahl der Operationen im Durchlauf dividiert, so dass ein Durchschnitt herauskommt, der als Aufwand für die untersuchte Operation genommen wird. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einem besseren Wert führen, da es häufig Operationen gibt, die zwar im Einzelfall teuer sein können, wobei aber ein „teurer“ Fall verglichen mit den anderen (günstigeren) Fällen in einem Ablauf relativ selten vorkommt. Ein anderes Beispiel, dessen Untersuchung 1978 (noch vor der Namensgebung «amortized») stattfand, beschreibt die Anzahl der Rebalancierungsoperationen in BB[α]-Bäumen als amortisiert konstant.

Damit wird die amortisierte Laufzeitanalyse («amortized analysis») als dritte Technik neben die bekannten Laufzeitanalysen der maximalen Kosten («worst-case analysis») und des durchschnittlichen Verhaltens («average-case analysis») gestellt.

Bei der amortisierten Laufzeitanalyse gibt es drei prinzipiell gleichwertige Methoden:

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

Siehe auch

• Komplexitätstheorie
• Graphentheorie
• Zeitkomplexität
• Effizienz
• Programmoptimierung

Literatur

• Robert Endre Tarjan: Amortized Computational Complexity (= SIAM Journal on Algebraic and Discrete Methods. Band 6, Nr. 2). April 1985, S. 306–318, doi:10.1137/0606031 (duke.edu [PDF]). 
• Norbert Blum, Kurt Mehlhorn: On the Average Number of Rebalancing Operations in Weight-Balanced Trees. 1978 (uni-saarland.de [PDF]): „There is a constant c (depending on α) such that: The total number of rebalancing operations required for executing an arbitrary sequence of n insertions and deletions in an empty Weight-balanced tree is bounded by c·n.“ 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 405–430 (englisch). 
• Rebecca Fiebrink: Amortized Analysis Explained. 2007 (archive.org [PDF] archiviert am 20. Oktober 2013): „Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis.“