- Amortized analysis
computer science, especially analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst-case"sequence" of operations. Amortized analysis differs from average-case performance in that probabilityis not involved; amortized analysis guarantees the time per operation over worst-case performance.
The method requires knowledge of which series of operations are possible. This is most commonly the case with
data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.
As a simple example, in a specific implementation of the
dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O("n"). However, a "sequence" of "n" insertions can always be done in O("n") time, so the "amortized" time per operation is O("n") / "n" = O(1).
average-case analysisand probabilistic analysisare not the same thing as amortized analysis. In average-case analysis, we are averaging over all possible inputs; in probabilistic analysis, we are averaging over all possible random choices; in amortized analysis, we are averaging over a sequence of operations. Amortized analysis assumes worst-case input and typically does not allow random choices.
There are several techniques used in amortized analysis:
*Aggregate analysis determines the upper bound "T"("n") on the total cost of a sequence of "n" operations, then calculates the average cost to be "T"("n") / "n".
Accounting methoddetermines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.
Potential methodis like the accounting method, but overcharges operations early to compensate for undercharges later.
* In common usage, an "amortized algorithm" is one that an amortized analysis has shown to perform well.
* Online algorithms commonly use amortized analysis.
* cite book | author=
Allan Borodinand Ran El-Yaniv | title= [http://www.cs.technion.ac.il/~rani/book.html "Online Computation and Competitive Analysis"]
publisher= Cambridge University Press
date= 1998 | pages= 20,141
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. " Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 17: Amortized Analysis, pp.405–430.
Wikimedia Foundation. 2010.