摊还分析

摊还分析给出了连续n个操作的平均时间上限，结合问题特性，而不是简单n*最坏情形

1. 聚合分析——T(n)/n，not worst T(1)
2. 核算法——每次操作的给一个摊还代价\(\overline{ci}\),减去操作实际代价ci,存入信用\(\overline{ci}\)-ci,保证\(\sum_{1}^{n}(\overline{ci}-ci)\geq0\)
3. 势能法——给过程中的数据结构赋予势能\(f(Di)\geq f(D_0)\),\(\sum_{1}^{n}\overline{ci}=\sum_{0}^{n}{ci}+f(D_i)-f(D_{i-1})=\sum_{1}^{n}ci+f(D_n)-f(D_0)\)