聚合分析(aggregate analysis)
一个 n 个操作的序列最坏情况下花费的总时间为, 则在最坏情况下, 每个操作的摊还代价为
如栈中的 push, pop 操作都是 , 增加一个新操作
multipop,
def multipop(stk,k):
while not stk.empty() and k>0:
stk.pop()
k-=1
multipop 的时间复杂度为 min(stk.size,k), 最坏情况为 , 则 n 个包含 push pop multipop 的操作列的最坏情况是
, 并不是这样, 注意到, 必须栈中有元素, 再 pop, 所以 push 操作与pop 操作(包含 multipop中的pop), 个数相当, 所以 实际上应为
, 每个操作的摊还代价 为
核算法 (accounting method)
对不同操作赋予不同费用 cost (称为摊还代价 ), 可能多于或者少于其实际代价
当 , 将
(
credit) 存入数据结构中的特定对象.. 对于后续 时, 可以使用这些credit来 支付差额.. 有要求
如栈
| op | ||
|---|---|---|
| push | 2 | 1 |
| pop | 0 | 1 |
| multipop | 0 | min(s,k) |
由核算法, 摊还代价满足要求, 所以 n 个操作总代价 , 每个操作摊还代价为
势能法(potential method)
势能释放用来支付未来操作的代价, 势能是整个数据结构的, 不是特定对象的(核算法是).
数据结构 为初始状态, 依次 执行 n 个操作
进行势能转换
, 各操作代价为
势函数 ,
即为
的势
则第 i 个操作的摊还代价
则
如果定义一个势函数, 则总摊还代价给出了实际代价的一个上界
可以简单地以
例如栈操作,
设空栈为 , 势函数定义为栈的元素数
对于push,
则
对于 multipop,
则
同理 pop 的摊还代价也是0, 则总摊还代价的上界(最坏情况) 为
