聚集分析法 示例:计数器 w Consider the entire sequence of operations a Consider the problem of incrementing a k- 中 A MultiHop(k) takes at most m=mn化k bit binary counter that counts upward from S. getSizeO operations e It has at least m push operation had taken c Array A=[O,1,. k-1]represents the k bits before the pops. w On an initial empty Stack, a sequence of n operations of push, pop, multipop takes at most O(n)steps of operations m Amortized cost =O(n)/n=O(1) AJ]A[2 A[T]A[O] Algorithm 1.i0 2. while i length(a] and A0==1 5. if i length (A] then A0<1 Analysis the algorithm Total cost - The most costing operation is k, the length cThe total number of flips of the bits the worst cost will not O(nk)where n is the operation numbers 啼 A tighten analysis aHalf the operations take 1 operation 岁1<n81/2<2n aQuarter of the operations takes 2 operations 2-of operations takes i operations2 清华大学 宋斌恒 7 聚集分析法 Consider the entire sequence of operations: A MultiPop(k) takes at most m = min{k, S.getSize()} operations It has at least m push operation had taken before the pops. On an initial empty Stack, a sequence of n operations of push, pop, multipop takes at most O(n) steps of operations. Amortized cost = O(n)/n = O(1) 清华大学 宋斌恒 8 示例：计数器 Consider the problem of incrementing a k￾bit binary counter that counts upward from 0. Array A=[0,1,…,k-1] represents the k bits 清华大学 宋斌恒 9 Algorithm Increment(A) 1. i Å 0 2. while i < length[A] and A[i]==1 3. { 1. A[i]Å0; 2. i++; 4. } 5. if i < length[A] then A[i]Å1 清华大学 宋斌恒 10 16 0 1 0 0 0 0 31 15 0 0 1 1 1 1 26 14 0 0 1 1 1 0 25 13 0 0 1 1 0 1 23 12 0 0 1 1 0 0 22 11 0 0 1 0 1 1 19 10 0 0 1 0 1 0 18 9 0 0 1 0 0 1 16 8 0 0 1 0 0 0 15 7 0 0 0 1 1 1 11 6 0 0 0 1 1 0 10 5 0 0 0 1 0 1 8 4 0 0 0 1 0 0 7 3 0 0 0 0 1 1 4 2 0 0 0 0 1 0 3 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 Total cost Counter A[5] A[4] A[3] A[2] A[1] A[0] value 清华大学 宋斌恒 11 Analysis the algorithm The most costing operation is k, the length of the bits, the worst cost will not exceed O(nk) where n is the operation numbers; A tighten analysis Half the operations take 1 operation Quarter of the operations takes 2 operations 2-i of operations takes i operations 清华大学 宋斌恒 12 Total cost Total cost The total number of flips. ⎣ ⎦ n n i i i n i i 1 / 2 2 2 0 lg 0 ∑ < ∑ < ∞ = =