算法导论【摊还分析】—聚合分析、核算法、势能法

假定我们对一个数据结构执行一个由 n 个操作组成的操作序列，当 i 严格为 2 的幂时，第 i 个操作的代价为 i，否则代价为 1

聚合分析

总共有n个操作，$1,2,\mathrm{4.....},2^{\lfloor \lg n\rfloor }$，其中有至多$k=\lceil \lg n\rceil$个操作序号为2的幂，则
$$\begin{array}{rl}S& =\sum _{k=0}^{\lfloor \lg n\rfloor }{2}^k+(n-\lceil \lg n\rceil )\ast 1\\ & =\frac{1\ast (1-2^{\lfloor \lg n\rfloor +1})}{1-2}+n-\lceil \lg n\rceil \\ & =2^{\lfloor \lg n\rfloor +1}-1+n-\lceil \lg n\rceil \\ & =\le 3n-\lceil \lg n\rceil -1\\ & =O(n)\end{array}$$
所以每个操作的摊还时间代价为$$\frac{O(n)}{n}=O(1)$$

核算法

设每个操作的代价都为$3$
第$2^{k-1}+1到第2^k-1$个操作为非2的幂，多付的代价为$$2\ast (2^{k-1}-1-1+1)=2^k-2$$在第$2^k$个次操作付的代价为$3$，则可以用于支付第$2^k$次操作的信用为$$2^k-2+3=2^k+1>2^k$$大于第$2^k$次操作应该付的代价，故每个操作的摊还代价为$O(1)$

势能法

设势函数为
$$\begin{gathered} \Phi (D_0)=0 \\ \Phi (D_i)=2(i-2^{\lg \lfloor i\rfloor }) \end{gathered}$$

1. 当i为2的幂时，$2^{\lfloor \lg i\rfloor }=i,\lfloor \lg (i-1)\rfloor +1=\lfloor \lg i\rfloor$
   $$\begin{array}{rl}{\hat{c}}_i& =c_i+\Phi (D_i)-\Phi (D_{i-1})\\ & =i+2(i-2^{\lfloor \lg i\rfloor })-2(i-1-2^{\lfloor \lg i-1\rfloor })\\ & =i+2i-2i+2-2^{\lfloor \lg i\rfloor +1}+2^{\lfloor \lg i\rfloor +1}\\ & =i-i-2^{\lfloor \lg i\rfloor }+2^{\lfloor \lg i\rfloor +1}+2\\ & =2\end{array}$$
2. 当i不为2的幂时，$2^{\lfloor \lg (i-1)\rfloor }=2^{\lfloor \lg i\rfloor }$
   $$\begin{array}{rl}{\hat{c}}_i& =c_i+\Phi (D_i)-\Phi (D_{i-1})\\ & =1+2(i-2^{\lfloor \lg i\rfloor })-2(i-1-2^{\lfloor \lg i-1\rfloor })\\ & =1+2i-2i+2-2(2^{\lfloor \lg i\rfloor }-2^{\lfloor \lg i-1\rfloor })\\ & =1+2\\ & =3\end{array}$$
   故每个操作摊还复杂度为$O(1)$