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