形式陈述

势能法为数据结构状态 $D_i$ 选取非负势函数 $\mathrm{\Phi }(D_i)$，定义第 $i$ 次操作的摊还成本 ${\hat{c}}_i=c_i+\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1})$。求和后势能项望远镜消去：$\sum c_i=\sum {\hat{c}}_i-\mathrm{\Phi }(D_m)+\mathrm{\Phi }(D_0)\le \sum {\hat{c}}_i+\mathrm{\Phi }(D_0)$。若令初始势为零，则摊还总成本上界直接控制真实总成本。势函数可看作过去便宜操作预存的“信用”。

直觉

昂贵操作往往消耗先前积累的结构复杂度。势能把状态中尚未支付的未来工作量量化，使每步“真实成本加势能变化”保持平稳。

例子与边界

动态数组扩容时可令势与已占用容量和空闲量相关，使普通插入积累势、整表复制时释放势，从而得到 $O(1)$ 摊还插入。二进制计数器可令势为 1 的位数：翻转许多 1 为 0 的昂贵递增同时大幅降低势。势能必须对所有可达状态满足所需下界；若允许最终势大幅为负，就会虚构不存在的信用。摊还界不是随机期望，也不保证每次操作都快。

推论与应用

势能法分析动态数组、堆、并查集、伸展树和在线算法，能系统设计数据结构不变量并证明长操作序列的平均成本。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995，Chs. 1–7。