复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 07 Amortized analysis

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

MULTIPOP MULTIPOP(S, x) 1. while not STACK-EMPTY(S pS]=6→|3 andk≠0 2. do POP(s 12 k←k-1 8 5 my8=2→[6 MULTIPOP(S4 15

MULTIPOP 6 15 8 5 3 12 S top[S] = 6 MULTIPOP(S, x) 1. while not STACK-EMPTY(S) and k ≠ 0 2. do POP(S) 3. k ← k − 1 MULTIPOP(S, 4) top[S] = 2

Analysis of MULTIPOP A sequence ofn PUSH, POP, and MULTIPOP operations on an initially empty stack The worst-case cost of a MULTIPOP operation O(n) The worst-case time of any stack operation is therefore O(n) a sequence of n operations costs is O(n2 This bound is not tight/

Analysis of MULTIPOP y The worst-case cost of a MULTIPOP operation is O ( n ) y The worst-case time of any stack operation is therefore O ( n ) A sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack. y A sequence of n operations costs is O ( n 2 ) This bound is not tight!

Amortized analysis D An amortized analysis is any strategy for analyzing a sequence of operations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive a Even though were taking averages, however probability is not involved a An amortized analysis guarantees the average performance of each operation in the worst case

Amortized analysis ‡ An amortized analysis is any strategy for analyzing a sequence of operations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive. ‡ Even though we're taking averages, however, probability is not involved! ‡ An amortized analysis guarantees the average performance of each operation in the worst case

Types of amortized analyses Three common amortization arguments Aggregate metho Accounting method Potential method The aggregate method, though simple, lacks the precision of the other two methods. In particular, the accounting and potential methods allow a specific amortized cost to be allocated to each operation

Types of amortized analyses Three common amortization arguments: y Aggregate method y Accounting method y Potential method The aggregate method, though simple, lacks the precision of the other two methods. In particular, the accounting and potential methods allow a specific amortized cost to be allocated to each operation

Aggregate analysis We show that for all n, a sequence of n operation takes worst-case time T(n)in total Hence, the average cost, or amortized cost, per operation is T(n)/n

Aggregate analysis y We show that for all n, a sequence of n operation takes worst-case time T( n ) in total. y Hence, the average cost, or amortized cost, per operation is T( n)/ n

MULTIPOP (aggregate method Each object can be popped at most once for each time it is pushed. Therefore, the number of times that POP can be called on a nonempty stack including calls within MULtIPOP, is at most the number of push operations which is at most n Any sequence of n Push, POP, and MULtIPOP operations takes a total of o(n) time. The average cost of an operation is T(n)/n=O(1)

MULTIPOP (aggregate method) y Each object can be popped at most once for each time it is pushed. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP, is at most the number of PUSH operations, which is at most n. y Any sequence of n PUSH, POP, and MULTIPOP operations takes a total of O ( n ) time. The average cost of an operation is T( n)/ n = O(1 )

8-bit binary counter Counter Total Value p cost 000000000 00000001 200000010 300000011 400000100 013478 00000101 5678 00000110 10 00000111 00001000 5

8-bit binary counter 0000000 0 000000 0 1 0000001 0 00000 0 1 1 0000010 0 000001 0 1 0000011 0 0000 0 1 1 1 0000100 0 0 1 2 3 4 5 6 7 8 A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] 0 1 3 4 7 8 10 11 15 Counter Value Total cost

Incrementing a binary counter An array A[0..k-1] of bit, where length[a-k, as the counter i=0 A[i]·2 INCREMENT(A 1.i←0 2. while i length and ai= l 3.doA[←0 4. 5. if i length[A] then Ai

Incrementing a binary counter An array A[0 … k − 1] of bit, where length [A] = k, as the counter. 1 0 [] 2 k i i x A i − = = ∑ ⋅ INCREMENT (A ) 1. i ← 0 2. while i < length [A] and A [ i] = 1 3. do A [ i ] ← 0 4. i = i + 1 5. if i < length [A] 6. then A [ i ] ← 1

Binary counter(aggregate method For i=0,1., LIgnl, bit A(i] flips n/2 times in a sequence of n INCREMENT operation on an initially zero counter The total number of flips in the sequence is thus n 2n O(n) The amortized cost per operation is O(n)n=O(1)

Binary counter (aggregate method) For i = 0, 1 …, , bit A [ i ] flips times in a sequence of n INCREMENT operation on an initially zero counter. ⎢⎣lg n⎥⎦ / 2i ⎢n ⎥ ⎣ ⎦ The total number of flips in the sequence is thus lg 0 0 1 2 2 n i i i i n n ⎢ ⎥ ⎣ ⎦ ∞ = = ⎢ ⎥ < ⎢ ⎥ ⎣ ⎦ ∑ ∑ = 2 n = O ( n ) The amortized cost per operation is O ( n)/ n = O(1)