Account-Methode
Die Account-Methode (oder auch Bankkonto-Paradigma) ist eine Verfahrensweise der amortisierten_Laufzeitanalyse.Bei der Account-Methode wird angenommen, dass die Laufzeiten, die benötigt werden um einzelne Operationen auszuführen, Geldbeträgen entsprechen, die an eine 'Kasse' bezahlt werden.
Wenn die Laufzeiten mit bezeichnet werden, dann enthält die Kasse
.
Die amortisierten Kosten pro Einzeloperation sind dann
.
Wird dem Algorithmus in jeder Runde ein 'Gehalt' gebilligt, so kann die Runde durchlaufen werden, wenn die Kosten sich mit dem Gehalt 'decken'; Ist eine Runde 'billiger', so wird der 'Restbetrag' auf einem 'Sparkonto' gespeichert und für Runden aufgehoben, wenn die Kosten das Gehalt übersteigen.
Gehalt : G, Kosten der i-ten Runde : ti, Kosten der j-ten Runde : tj
Ist ti < G, so kann G-ti 'gespart' werden.
Ist tj > G, so kann der Fehlbetrag tj - G aus dem Sparkonto bezahlt werden.
Legt man nun ein geeignetes Gehalt und eine geeignete Sparstrategie fest, welche sicherstellt, dass zu jedem Zeitpunkt alle Operationen bezahlt werden können, so ist
und die amortisierten Einzelkosten sind
