| Potential Method |
Article Index for Potential |
Website Links For Potential |
Information AboutPotential Method |
| CATEGORIES ABOUT POTENTIAL METHOD | |
| algorithms | |
|
THE METHOD Similar to Potential in physics, a potential function is a real valued function from states of the data structure in question. Assume a data structure goes through a series of states after n different operations, and is a potential function. If is the runtime of operation number i, we define its amortized runtime to be . The total runtime of the n operations equals . If satisfies then the runtime of all n operations is less or equal the sum of all amortized times. SAMPLE APPLICATIONS Table Expansion The problem of Table Expansion can be solved using the potential method. Choose as potential function the number of occupied cells minus the number of vacant cells. Every regular inserts increases the potential by O(1). An insert that causes reallocation decreases the potential by n, which is the exact amount of work done in the reallocation, thus getting O(1) amortized time for insert. SEE ALSO EXTERNAL LINKS |
|
|