文档介绍：Overview
第六讲:分摊分析法 Aggregate analysis
The accounting method
Amortized Analysis The potential method
宋斌恒 Example:
Dynamic tables
清华大学宋斌恒 1 清华大学宋斌恒 2
Overview 聚集分析法
由分摊分析法解决的问题 A sequence of n operations takes worst-
Sequence of operation on a dada structure case time T(n) in total
Average cost per operation The average cost T(n)/n is called the
【比如网站的整体效率问题与此问题的关系】 amortized cost,
三类主要分析手段 the amortized cost applies to each
Aggregate, worst case + average operation, even they are different.
Accounting, Amortized cost
Potential, is a whole index for the data
structure
清华大学宋斌恒 3 清华大学宋斌恒 4
Stack operation 粗略分析
Let S be a stack object, it has two basic In the worst case of these operations, the
operations: worst cost is n, the size of the dada
Pop() structure;
Push() A sequence of m operations cost at most
Adding another operation m*n
MultiPop(k), which pops k elements at once,
its cost is at most k pop()’s cost The amortized cost of the operations is
Attention: what it occurs when less than O(n)
()<k? It is right but not tight!
清华大学宋斌恒 5 清华大学宋斌恒 6
1
聚集分析法示例:计数器
Consider the entire sequence of operations: Consider the problem of incrementing a k-
A MultiPop(k) takes at most m = min{k, bit binary counter that counts upward from
()} operations 0.
It has at least m push operation had taken Array A=[0,1,