算法
title: 摊还分析
categories: 数据结构与算法

---

在摊还分析中，我们通过求数据结构中一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。

---

摊还分析分类

• 聚合分析
• 核算法
• 势能法

聚合分析

栈操作

栈有两个基本操作
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操作(代价为$k*1$)和一次MULTIPOP操作(代价为$k$)均摊下来的操作时间为$(k*1+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[7]	A[6]	A[5]	A[4]	A[3]	A[2]	A[1]	A[0]	每步代价	总代价
0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	1	1	1
2	0	0	0	0	0	0	1	0	2	3
3	0	0	0	0	0	0	1	1	1	4
4	0	0	0	0	0	1	0	0	3	7
5	0	0	0	0	0	1	0	1	1	8
6	0	0	0	0	0	1	1	0	2	10
7	0	0	0	0	0	1	1	1	1	11
8	0	0	0	0	1	0	0	0	4	15
9	0	0	0	0	1	0	0	1	1	16
10	0	0	0	0	1	0	1	0	2	18
11	0	0	0	0	1	0	1	1	1	19
12	0	0	0	0	1	1	0	0	3	22
13	0	0	0	0	1	1	0	1	1	23
14	0	0	0	0	1	1	1	0	2	25
15	0	0	0	0	1	1	1	1	1	26
16	0	0	0	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$$

动态表

1. 对第i次操作预先收取费用 $\widehat c_i=\$\ 3 (i =2,\ldots,n)$, n=1时收取的费用为$2
   
   • 对每次操作花费$1
   • 结余$2

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)$