Die Account-Methode (oder auch Bankkonto-Paradigma bzw. Buchungsmethode) ist eine Verfahrensweise der amortisierten Laufzeitanalyse. Nach der Account-Methode werden den realen Kosten einzelner Operationen eines Algorithmus amortisierte Kosten gegenübergestellt, und ihre Differenz auf ein Konto gebucht.

Beispiel

Mit der Account-Methode wird die Anzahl der Bitwechsel bei der Inkrementation eines Binärzählers analysiert.

Elementare Operationen sind das Setzen von einem Bit von 0 auf 1 bzw. das Setzen von einem Bit von 1 auf 0. Die realen Kosten für beide Operation werden auf 1 Einheit gesetzt. Im Gegensatz dazu werden die amortisierten Kosten auf 2 bzw. 0 Einheiten gesetzt. Wenn ein Bit auf 1 gesetzt wird, entstehen 2 Einheiten amortisierte Kosten von denen nur eine verbraucht und der Rest auf das Konto eingezahlt wird. Bei dem Bit-Wechsel von 1 nach 0 muss 1 Einheit amortisierte Kosten von dem Konto bezahlt werden.

Da nun bei jeder Inkrementation des Zählers genau ein Bit von 0 auf 1 gesetzt wird, enthält das Konto genug Einheiten um alle möglichen Wechsel von 1 auf 0 zu bezahlen. Also sind die amortisierten Gesamtkosten für n Inkrementation in O(n).

Siehe auch

• Aggregat-Methode
• Potenzialfunktionmethode

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, S. 410-412.