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.^[1]

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.^[2]

Bei der amortisierten Laufzeitanalyse gibt es drei prinzipiell gleichwertige Methoden:

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

1. ↑ Blum & Mehlhorn
2. ↑ Rebecca Fiebrink