形式陈述

摊还分析给一串操作的总成本作确定性上界，再把它分配到单次操作；它不对输入分布取期望。三种等价常用方法是聚合法、记账法和势能法。势能法选取状态势能 $\Phi(D_i)$$\mathrm{\Phi }(D_i)$，定义第 $i$$i$ 次摊还成本

$$ \hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1}). $$$${\hat{c}}_i=c_i+\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1}).$$

于是

$$ \sum_{i=1}^n c_i=\sum_{i=1}^n\hat c_i-\Phi(D_n)+\Phi(D_0). $$$$\sum _{i=1}^n{c}_i=\sum _{i=1}^n{\hat{c}}_i-\mathrm{\Phi }(D_n)+\mathrm{\Phi }(D_0).$$

若 $\Phi(D_n)\ge0$$\mathrm{\Phi }(D_n)\ge 0$ 且 $\Phi(D_0)=0$$\mathrm{\Phi }(D_0)=0$，摊还总成本上界实际总成本。

直觉

便宜操作提前“存钱”或积累势能，支付偶尔昂贵的重组；保证针对整段任意操作序列，而不是假设昂贵情况概率很低。

例子与边界

动态数组容量满时翻倍：某次扩容复制 $\Theta(n)$$\mathrm{\Theta }(n)$ 个元素，但每个元素只在容量倍增时被复制，连续 $m$$m$ 次追加总成本 $O(m)$$O(m)$，故每次摊还 $O(1)$$O(1)$。栈的 multipop 也可用记账法分析。摊还 $O(1)$$O(1)$ 不表示每次实际延迟常数，也不提供高概率尾界；实时系统仍可能不能接受单次峰值。

推论与应用

摊还分析用于动态数组、并查集、伸展树、Fibonacci 堆和垃圾回收。选择势能函数实质上是在寻找对未来必要工作的可守恒记账。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 16, aggregate, accounting, and potential methods。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，§1.4, amortized cost in dynamic data structures。