Overview 第六讲:分摊分析法 E Aggregate analysis The accounting metho Amortized Analysi 啼 The potential method 宋斌恒 啼 Example dYnamic tables Overview 聚集分析法 噜由分摊分析法解决的问题 mA sequence of n operations takes worst Sequence of operation on a dada structure case time t()in total 4Average cost per operation 团【比如网站的整体效率问题与此问题的关系】 a The average cost T(n)/n is called the amortized cost 类主要分析手段 mthe amortized cost applies to each AGgregate, worst case average operation, even they are different. ACcounting, Amortized cost aPotential, is a whole index for the data structure Stack operation 粗略分析 w Let s be a stack object, it has two basic c In the worst case of these operations, the operations worst cost is n. the size of the dada pUshy rA sequence of m operations cost at most Adding another operation AMultiPop(k), which pops k elements at once its cost is at most k popos cost w The amortized cost of the operations is e Attention: what it occurs when less than O( cIt is right but not tight!1 清华大学 宋斌恒 1 第六讲：分摊分析法 Amortized Analysis 宋斌恒 清华大学 宋斌恒 2 Overview Aggregate analysis The accounting method The potential method Example: Dynamic tables 清华大学 宋斌恒 3 Overview 由分摊分析法解决的问题 Sequence of operation on a dada structure Average cost per operation 【比如网站的整体效率问题与此问题的关系】 三类主要分析手段 Aggregate, worst case + average Accounting, Amortized cost Potential, is a whole index for the data structure 清华大学 宋斌恒 4 聚集分析法 A sequence of n operations takes worst￾case time T(n) in total The average cost T(n)/n is called the amortized cost, the amortized cost applies to each operation, even they are different. 清华大学 宋斌恒 5 Stack operation Stack operation Let S be a stack object, it has two basic operations: Pop() Push() Adding another operation MultiPop(k), which pops k elements at once, its cost is at most k pop()’s cost Attention: what it occurs when S.getSize()<k? 清华大学 宋斌恒 6 粗略分析 In the worst case of these operations, the worst cost is n, the size of the dada structure; A sequence of m operations cost at most m*n The amortized cost of the operations is less than O(n) It is right but not tight!