# 摊还分析

1. 摊还分析是一组操作的最坏时间复杂度的平均，与问题的输入分布无关

2. 汇聚法：$n$ 次操作的时间之和为 $T(n)$，则每次操作的摊还时间为 $T(n)/n$

3. 栈的例子：MULTIPOP，但只有 PUSH 进去多少个，才能 POP 出来多少个，因此摊还时间为 $O(1)$

4. 计数器的例子：增加 1，可能需要变化数位，第 $i$ 位每提升 $2^{i}$ 次，翻转一次，也就是总代价为 $\sum_{i=0}^{\lceil\lg n\rceil}\lfloor\frac{n}{2^i}\rfloor<2n$，因此摊还时间复杂度为 $O(1)$

5. 会计法：保证 $\sum_{i=1}^n\hat c_i\geqslant\sum_{i=1}^nc_i$，其中 $c_i$ 为实际代价，$\hat c_i$ 为摊还代价，这样可以保证摊还代价的上界

6. 同样是栈的例子，对 PUSH 瘫痪代价取 2，POP 和 MULTIPOP 摊还代价取 0，则总的摊还复杂度为 $O(1)$

7. 计数器的例子，将一个数从零置一，取摊还代价为 2，用于平摊之后从一变零，后者取摊还代价为 0，每次操作代价最多为 2，因此总的摊还代价为 $O(1)$

8. 势函数法：在数据结构里定义一个势，保证势总为正值
   - 原始数据结构为 $D_0$
   - 第 $i$ 次操作将 $D_{i-1}$ 变为 $D_i$
   - 定义一个势函数 $\Phi:\{D_i\}\to \mathbb{R}$，且有 $\Phi(D_0)=0$，$\forall i,\Phi(D_i)\geqslant 0$
   - 第 $i$ 次的摊还代价为 $\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$
   - 因此有 $n$ 次操作的摊还代价为 $\sum_{i=1}^n\hat{c_i}=\sum_{i=1}^nc_i+\Phi(D_n)-\Phi(D_0)$，只需要 $\Phi(D_n)\geqslant \Phi(D_0)=0$ 即可

9. 栈的例子，取势大小为栈中元素的值，则每次 PUSH 的摊还代价为 2，POP 和 MULTIPOP 的摊还代价为 0，因此总的摊还代价为 $O(1)$

10. 计数器的例子，取势大小为计数器中 1 的个数，则第 $i$ 次操作复位了 $t_i$ 位，有 $\Phi(D_i)\leqslant \Phi(D_{i-1})-t_i+1$，则 $\hat{c_i}\leqslant(t_i+1)+(1-t_i)=2$