CSCE 411 Lecture 15
« previous | Friday, September 28, 2012 | next »
Amortized Analysis (cont'd)
Accounting Method
Assign a cost, called the "amortized cost" to each operation.
Assignment must ensure that the sum of all amortized colsts in a sequence is at least the sum of all the actual costs (don't go bankrupt, but don't assign an excessive cost to each operation because people will get mad at us)
For each operation in the sequence:
- If amortized cost > actual cost, then store extra credit
- If amortized cost < actual cost, then use stored credits to make up the difference
Don't behave like a politician: we're never allowed to go into the red! We must have enough credits saved for each expensive operation.
Stack Example
Assign the following amortized costs:
- Push = 2
- Pop = 0
- Multipop = 0
When we push an operation (actual cost is 1; each operation stores 1 extra credit), we pay for the pop in advance!
Binary Increment Example
Assign amortized cost for increment operation = 2
Actual cost is number of bits flipped:
- Several 1s will be reset to 0
- A 0 is set to 1
We always flip the first bit, and that costs 1
| Sequence | Credits |
|---|---|
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 2 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 2 |
| 0 1 1 0 | 2 |
| 0 1 1 1 | 3 |
| 1 0 0 0 | 1 |