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 in mehreren Durchläufen 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, wobei dieser „teure“ Fall aber nur in einem oder wenigen Abläufen des Algorithmus vorkommt und alle anderen Fälle relativ günstig sind. Ziel ist also letztlich, die „durchschnittliche“ obere Schranke im Worst Case zu bestimmen; die obere Schranke, die im ungünstigst denkbaren Durchlauf im Worst Case gilt – und höher liegen kann –, bleibt davon jedoch unberührt.
Bei einer allgemeinen Laufzeitanalyse muss man vom teuersten Fall ausgehen, da dieser nicht insgesamt ausgeschlossen werden darf, aber wenn der Fall selten vorkommt, ist die damit berechnete Laufzeit bei mehreren Durchläufen schlechter als die (tatsächlich anzunehmende) durchschnittliche.
Bei der amortisierten Laufzeitanalyse gibt es prinzipiell drei unterschiedliche Methoden:
- die Aggregat-Methode
- die Account-Methode (auch Bankkonto-Paradigma genannt)
- die Potentialfunktionmethode
Siehe auch
Wikipedia.de
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 18.01. 2022