Unformatted text preview:

1CISC320, F05, Lec10, Liao 1CISC 320 Introduction to AlgorithmsFall 2005Lecture 10Amortized Analysis CISC320, F05, Lec10, Liao2Amortized Cost Why use amortized cost?Remember, we use the number of (basic) operations as a measure of running time. However, how can such a measure be useful if same operation (e.g., each cFind) may cost differently, depending when it is applied in a sequence of operations?  In an amortized analysis, the time required to perform a sequence of data structure operations is averaged over all the operations performed. Amortized cost differs from average-case cost, because there is no probability involved. Amortized cost is the average performance of each operation in the worst-case.2CISC320, F05, Lec10, Liao3 Three techniques for amortized cost analysis Aggregate method Amortized cost = total actual cost / number of operations Accounting method Amortized cost = actual cost + accounting cost The sum of the accounting cost is nonnegative Potential method Amortized cost = actual cost + increment of potential Potential never below zeroCISC320, F05, Lec10, Liao4 A simple examplestack operationsPush(S,x)Pop(S)MultiPop(S,k): pop k top objects of S. If S has less than k objects, then pop all in S.a sequence of n Push, Pop and MultiPop operations on initially empty stack.Worst-case cost: For each operation:Push: O(1)Pop: O(1)MultiPop: O(n) since the stack size is at most nThere are n operations (possibly O(n) MultiPop operations), the upper bound is O(n2). Problem: O(n2) upper bound is not tight.3CISC320, F05, Lec10, Liao5 Aggregate methodAlthough a single MultiPop can be expensive, any sequence of n Push, Pop, and MultiPopoperations on an initially empty stack can cost at most O(n).Proof: Pop (either directly or from inside MultiPop) can be called n times since there can be at most n objects (by n Push operations). The amortized cost of an operation is the average:O(n)/n = O(1)CISC320, F05, Lec10, Liao6 Accounting method Data structure comes with a “bank account” Every operation allotted a fixed $ cost (its amortized cost) If actual cost less than allotted amount, the difference is deposited into bank If actual cost more than allotted amount, withdraw from bank to pay for the operation Catch: always have a non-negative balance Benefit: we can use an operation’s amortized cost, which is a fixed number, and we know that n times the amortized cost is the upper bound of the actual cost of n operations.4CISC320, F05, Lec10, Liao7Actual cost:Push 1Pop 1MultiPop min(k,s)Amortized cost:Push 2Pop 0MultiPop 0Will the bank account be balanced?Yes. A stack of plates in a cafeteria. We start with an empty stack. Push a plate on the stack and pop a plate off the stack cost $1 each. Now, when push, we pay $2. One dollar for the actual cost, and one dollar as a credit. Since every plate on the stack has a dollar of credit on it, pop is free. CISC320, F05, Lec10, Liao8 Potential method Prepaid work as potential that can be released to pay for future operations Initial data structure D0, on which n operations are to be performed. Diis the data structure after i-th operation. Potential Φ: Di→Φ(Di) Amortized cost ciof the i-th operation is its actual cost plus the increase in potential due to the operationci= ci+ Φ(Di) - Φ(Di-1) The total amortized cost of the n operations ∑ ci= ∑ (ci+ Φ(Di) - Φ(Di-1) )= ∑ (ci) + Φ(Dn) - Φ(D0)5CISC320, F05, Lec10, Liao9 Potential Φ: number of objects on the stack. D0is empty stack, and Φ(D0) = 0 Φ(Di) ≥ 0 = Φ(D0)  Amortized cost: Pushci= ci+ Φ(Di) - Φ(Di-1) = 1 + 1 = 2 MultiPop(S, k)ci= ci+ Φ(Di) - Φ(Di-1) = k’ – k’ = 0where k’ = min(k,s) is the actual number objects removed from the stack.CISC320, F05, Lec10, Liao10Amortized analysis of Build-heapTask: to build n elements into a max-heap.Without loss of generality, let’s assume n is a power of 2, so the n elements can be mapped into a complete binary tree. There are n/2 -1 interior nodes and heapify needs to apply to each one of them. Actual cost = lg(h) where h is the height of the node that heapify is applied.Amortized cost = 2.Use the accounting method.Deposit $2 to each node. Comparison of a pair of keys will cost $1. We will show by induction that the total amount of deposit (=2n) is sufficient to cover the cost of n/2 -1 heapify operations.Start with the lowest level (let’s call it level-1) of interior nodes. Each has two children nodes. There will be 2 comparisons, cost $2, and $4 will be left in this subheap of 3 nodes. This is true for each level-1 subheap. Once done with this level, move one level up. Each node has $2, plus 2 x $4 from two subheaps, there are $10, out of which $4 will cover the cost of heapify (worst-case). So, $6 is left for every level 2 subheap. Therefore, we do induction: each level-i subheap has $(2i+ 2). When we heapify a level-(i+1) heap, the total amount available is 2 x $(2i+ 2) + $2, which is $ (2i+1+ 6). The total cost for heapifying a level-(i+1) heap is 2 log(i+1) = i+1. Therefore, we always have enough to cover the expenses, i.e., the bank account will never go bankruptcy! So we can safely say each heapify only cost $2, in amortized sense, i.e., the actual cost exceeding $2 (the case when it is applied to higher level subheaps) will be covered by the savings from these nodes that are never got visited by the


View Full Document

UD CISC 320 - Introduction to Algorithms

Download Introduction to Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?