Potential function method

Potential method is a redirect to this article. For the numerical method for solving transport problems, see the MODI method .

In complexity theory , the potential or potential function method is used to measure the amortized time and storage complexity of data structures . The complexity is calculated using a sequence of operations, which distributes the costs of rare but expensive operations over the sequence of operations and thus smooths them out.

The aim is to assign an average cost value to each operation on the data structure under consideration in order to use this to estimate the expected runtime of any sequence of operations upwards. In contrast to the bank account method , the costs of an operation are not set in advance, but are derived. For this purpose, a potential function is introduced. This assigns its potential to each internal state of the data structure. Let us now be the maximum real costs of the operation , the amortized effort results as: ${\displaystyle a_{i}}$ ${\displaystyle Op_{i}}$ ${\displaystyle \Phi \colon D_{i}\to \mathbb {R} }$ ${\displaystyle D_{i}}$ ${\displaystyle c_{i}}$ ${\displaystyle Op_{i}}$ ${\displaystyle a_{i}}$

${\displaystyle a_{i}=c_{i}+\Phi \left(D_{i}\right)-\Phi (D_{i-1})}$

It is now true that the potential of the initial state is never undershot for all operations in any sequence of operations: ${\displaystyle D_{0}}$ ${\displaystyle Op_{i}}$

${\displaystyle \forall i\in \{1,\dots ,n\}:\Phi (D_{0})\leq \Phi (D_{i})}$

Then the sum of the real costs is never higher than the amortized costs:

${\displaystyle \sum _{i=1}^{n}c_{i}\leq \sum _{i=1}^{n}a_{i}}$

For example, if there is a constant that indicates the upper limit of the amortized costs of each operation: ${\displaystyle C}$

${\displaystyle i\in \{1,\dots ,n\}:a_{i}\leq C}$

So the total cost of the sequence of operations can be calculated with operations with: ${\displaystyle n}$

${\displaystyle \sum _{i=1}^{n}c_{i}\leq n\cdot C}$

can be specified.

literature

• Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms . 2nd Edition. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 , pp. 412-415 .

swell

1. ↑ Kurt Mehlhorn , Peter Sanders : Algorithms and Data Structures , 2008 Springer-Verlag Berlin Heidelberg, Chapter 3.3.1 The Potential or Bank Account Method for Amortized Analysis , pp. 72–74