数据结构和算法分析算法

『算法』摊还分析

2018-08-27 本文已影响0人 mbinary

聚合分析(aggregate analysis)

一个 n 个操作的序列最坏情况下花费的总时间为 $T(n)$ , 则在最坏情况下, 每个操作的摊还代价为 $\frac{T(n)}{n}$

如栈中的 push, pop 操作都是 $O(1)$ , 增加一个新操作 multipop,

def multipop(stk,k):
  while not stk.empty() and k>0:
    stk.pop()
    k-=1

multipop 的时间复杂度为 min(stk.size,k), 最坏情况为 $O(n)$ , 则 n 个包含 push pop multipop 的操作列的最坏情况是 $O(n^2)$ , 并不是这样, 注意到, 必须栈中有元素, 再 pop, 所以 push 操作与pop 操作(包含 multipop中的pop), 个数相当, 所以实际上应为 $O(n)$ , 每个操作的摊还代价为 $O(1)$

核算法 (accounting method)

对不同操作赋予不同费用 cost (称为摊还代价 $c_i'$ ), 可能多于或者少于其实际代价 $c_i$

当 $c_i'>c_i$ , 将 $c_i'-c_i$ ( credit) 存入数据结构中的特定对象.. 对于后续 $c_i'<c_i$ 时, 可以使用这些credit来支付差额.. 有要求
$\sum_{i}c_i' \geqslant \sum_{i}c_i$

如栈

op	$c_i'$	$c_i$
push	2	1
pop	0	1
multipop	0	min(s,k)

由核算法, 摊还代价满足要求, 所以 n 个操作总代价 $O(n)$ , 每个操作摊还代价为 $O(1)$

势能法(potential method)

势能释放用来支付未来操作的代价, 势能是整个数据结构的, 不是特定对象的(核算法是).

数据结构 $D_0$ 为初始状态, 依次执行 n 个操作 $op_i$ 进行势能转换 $D_i =op_i(D_{i-1}), i=1,2,\ldots,n$ , 各操作代价为 $c_i$

势函数 $\Phi:D_i\rightarrow R$ , $\Phi(D_i)$ 即为 $D_i$ 的势

则第 i 个操作的摊还代价
$c_i'=c_i+\Phi(D_i)-\Phi(D_{i-1})$

则
$\sum_{i=1}^{n}c_i'=\sum_{i=1}^{n}c_i+\Phi(D_n)-\Phi(D_0)$

如果定义一个势函数 $\Phi, st \ \Phi(D_i)\geqslant\Phi(D_0)$ , 则总摊还代价给出了实际代价的一个上界
可以简单地以 $D_0 \text{为参考状态}, then \ \Phi(D_0)=0$

例如栈操作,
设空栈为 $D_0$ , 势函数定义为栈的元素数
对于push, $\Phi(D_i)-\Phi(D_0)=1$
则 $c' = c +\Phi(D_i)-\Phi(D_0) = c+1 = 2$

对于 multipop, $\Phi(D_i)-\Phi(D_0)=- min(k,s)$
则 $c' = c - min(k,s) = 0$

同理 pop 的摊还代价也是0, 则总摊还代价的上界(最坏情况) 为 $O(n)$

上一篇下一篇

猜你喜欢

热点阅读