|
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.
|
