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

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

Siehe auch: Komplexitätstheorie, Zeitkomplexität, Effizienz, Optimierung