Science Fair Project Encyclopedia
Amortized analysis
In computational complexity theory, amortized analysis is the time per operation averaged over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.
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 method determines the individual cost of each operation.
- Potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details