摊还分析

摊还分析分类

聚合分析
核算法
势能法

聚合分析

栈操作

栈有两个基本操作
PUSH(S, x):将对象x压入栈S中。
POP(S): 将栈S的栈顶元素弹出，并返回该对象。对空栈执行此操作会报错。
上述两个操作都是O(1)时间，假定花费为1。因此一个n个PUSH和POP操作的写列的总代价为n，而n个操作的实际运行时间为$\Theta(n)$。
现增加一个新的操作MULTIPOP(S，k),它删除栈S栈顶的k个对象，如果栈中对象少于k，则将整个栈的内容都弹出。
分析由n个PUSH、POP和MULTIPOP组成的操作序列在一个空栈上的执行情况。虽然一个MULTIPOP操作的代价可能更很高，但是均摊下来，上述操作序列的代价至多是$O(n)$。我们从MULTIPOP的角度出发，在执行MULTIPOP的操作的时候，栈中肯定右k个元素，也就是说肯定执行了k次PUSH操作，则这k次PUSH操作(代价为$k1$)和一次MULTIPOP操作(代价为$k$)均摊下来的操作时间为$(k1+k)/k=\Theta(1)$。所以，在此例中，所有操作的摊还代价为$O(1)$。

特别注意的是，当在栈中继续增加一个MULTIPUSH操作时，此时的均摊代价已不是$O(1)$了，因为进行n次操作，花费可能最坏达到$\Theta(nk)$,这种情况是MULTIPUSH与MULTIPOP交替执行，每次操作的花费都是k，则n次的总花费就是$n*k$。

二进制计数器

k位二进制计数器，计数器的初始值为0.用位数组$A[0\ldots k-1]$作为计数器，要表示某数则为$x = \sum_{i=0} ^{k-1} {A[i]*2^i}$.将1加到计数器的值上，使用如下的过程

INCREMENT(A)
    i = 0
    whil i < A.length and A[I] == 1
        A[i] = 0
        i = i+1
    if i < A.length
        A[i] = 1

加1操作中各位置上的变化如下表：

计数器值	A[4]	A[3]	A[2]	A[1]	A[0]	每步代价	总代价
0	0	0	0	0	0	0	0
1	0	0	0	0	1	1	1
2	0	0	0	1	0	2	3
3	0	0	0	1	1	1	4
4	0	0	1	0	0	3	7
5	0	0	1	0	1	1	8
6	0	0	1	1	0	2	10
7	0	0	1	1	1	1	11
8	0	1	0	0	0	4	15
9	0	1	0	0	1	1	16
10	0	1	0	1	0	2	18
11	0	1	0	1	1	1	19
12	0	1	1	0	0	3	22
13	0	1	1	0	1	1	23
14	0	1	1	1	0	2	25
15	0	1	1	1	1	1	26
16	1	0	0	0	0	5	31

对于一个初值为0，执行n次INCREMENT操作，显然，A[0]位变化n次，A[1]位变化$ \left \lfloor \dfrac n 2 \right \rfloor $,…A[i]会变化$ \left \lfloor \dfrac n {2^i} \right \rfloor $,因此总的变换次数为$$ \sum_ {i=0} ^{k-1} \left \lfloor \dfrac n {2^i} \right \rfloor<n\sum_{i=0}^\infty \dfrac 1 {2^i} = 2n $$
每个操作的摊还代价为$ O(n)/n = O(1) $.

核算法(Accounting method)

在核算法中，对不同的操作赋予不同的费用，赋予某些操作的费用可能大于或等于实际操作的代价。将赋予一个操作的费用称为摊还代价。当一个操作的摊还代价爱超出其市集代价时，我们将差额存入数据结构中的特定对象，存入的差额被成为信用。对于后续操作中摊还代价小于市集代价的情况，信用可以用来支付差额。

算法描述

对第i步操作，收取虚拟的费用cost:$c_i$(例如对每个单元收取\$1）
每个操作花费
没有用的额度将被存到银行，为以后的操作做准备
银行的余额不能为负
必须保证$$\sum_{i=1} ^n c_i \leq \sum_{i=1} ^n \widehat{c_i} \qquad\forall i$$
动态表

对第i次操作预先收取费用 $\widehat {c_i}=\$\ 3 (i =2,\ldots,n) $, n=1时收取的费用为\$2
- 对每次操作花费\$1
- 结余\$2
当表的容量翻倍时
- 将以前的元素移到新表时，每移一次以前的元素花费\$1
- 加入新元素时花费\$1
  动态表的扩展过程为
  插入第一个元素时，预先收费 \$2,花费\$1,剩余\$1
  插入第二个元素时，表将翻倍，银行中剩余的\$1用来支付移动第一个元素的费用，对第二个元素，预先收费\$3,花费\$1,剩余\$2
  表中的数字表示剩余的钱，0表示已经插入元素
  可以发现每次当表需要翻倍时，银行中的结余刚好够支付表翻倍时转移old元素的费用

1
0	2
0	0	2	2
0	0	0	0	2	2	2	2
0	0	0	0	0	0	0	0	2	2	2	2	2	2	2	2

势能法

将银行结余表示为势,势能的释放用来支付未来的操作。

数据结构开始于$ D_0 $
第i次操作，变化为$ D_{i-1}\longrightarrow D_i $,这次操作的花费为$ c_i $
定义势能函数$ \Phi(D_i) \rightarrow \mathbb{R} $
$ \Phi(d_0)=0 $且$ \Phi(D_i)\geq0 $
摊还代价$ \hat {c_i} $
$$ \hat {c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1}) $$
$$ \Delta \Phi_i = \Phi(D_i)-\Phi(D_{i-1}) $$

如果 $ \Delta \Phi_i > 0 $,则$ \hat c_i > c_i $,第i此操作将储存剩余的量到数据结构中
如果$ \Delta \Phi_i < 0 $,则$ \hat c_i < c_i $,则第i次操作将消耗储存的能量

n次操作的总的摊还代价为
$$\begin{eqnarray*} \sum\_{i=1} ^n {\hat c\_i} &=& \sum\_{i=1} ^n(c\_i+\Phi(D\_i)-\Phi(D\_{i-1})) \\&=& \sum\_{i=1} ^n c\_i + \Phi(D\_n)-\Phi(D\_0) \\& \geq & \sum\_{i=1}^n c\_i \end{eqnarray*}$$
现举例说明：
定义 $ \Phi(D_0) = 0 $
$$\begin{eqnarray*} \Phi(D\_i) &=& \sum\_{i=1}^n(\hat{c\_i}-c\_i)+\Phi(D\_0) \\&=&2i- 2^{\left \lceil \log i \right \rceil} \end{eqnarray*}$$
则$\Phi(D_i) = 2i-2^{\lceil\log i \rceil}$
那么
$$\Phi(D\_i) = \left \{ \begin{array}{ll} i & \mbox{} \\ 0 & \mbox{} \end{array} \right.$$
值得注意的是：
$$\Phi(D_0) = 0 \ \forall i $$
$$\Phi(D_i) \geq 0\ \forall i $$
现在，算出第i次操作的摊还代价为
$$\begin{eqnarray*} \hat{c\_i} &=& c\_i+\Phi(D\_i)-\Phi(D\_{i-1}) \\& = & \left \{ \begin{array}{ll} i & \mbox{如果i-1是2的幂}\\ 1 & otherwise \end{array} \right. +(2i-2^{\left \lceil \log i\right \rceil})-(2(i-1)-2^{\left \lceil \log{i-1}\right \rceil}) \end{eqnarray*}$$
第一种情况 i-1是2的幂$$\begin{eqnarray*} \hat{c\_i} &=&i+2 -2^{\left \lceil \log i\right \rceil} +2^{\left \lceil \log{i-1}\right \rceil} \\&= &i+2-2(i-1)+(i-1) \\ & = & 3 \end{eqnarray*}$$
第二种情况$$\begin{eqnarray*} \hat{c\_i} &=&i+2 -\overbrace{2^{\left \lceil \log i\right \rceil} +2^{\left \lceil \log{i-1}\right \rceil}}^{相等} \\& = & 1+2 \\& = & 3 \end{eqnarray*}$$ 因此可以得到，在最坏的情形下，插入n次花费$ \Theta(n) $