势能法

设计势函数时，可以先问：昂贵操作会消耗哪一种积累下来的结构？若一次批量删除会清掉许多元素，就让这些元素事先各携带一点信用；若一次重建会清掉许多待处理标记，就让势记录标记数。势函数不是物理能量，而是把将来要付的工作对应到当前状态上，使昂贵操作发生时恰有足够的势下降。

动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。可令势与长度、容量的差额相关，让普通追加积累的势支付下一次整体复制；具体扩缩阈值和常数摊还界集中在对应条目。二进制计数器可令势为 $1$ 的位数：翻转许多 $1$ 为 $0$ 的昂贵递增同时大幅降低势。栈的 multipop(k) 则取势为当前元素数，弹出每个元素的实际成本由势能下降抵消。

以栈为例，先只数元素写入与删除：push 成本为 $1$，批量弹出 $r$ 个元素的成本为 $r$；函数调用和停止检查另加常数。先试 $\mathrm{\Phi }(D)=\alpha |D|$：push 的摊还成本是 $1+\alpha$，弹出 $r$ 个元素则为 $(1-\alpha )r$。要让后者不随 $r$ 增长，必须选 $\alpha \ge 1$；取最小的 $\alpha =1$，就得到 push 成本 $2$、批量弹出成本至多一个常数。这展示了势的系数如何由所需不等式反推出来。

从空栈连续压入三个元素，再执行一次弹出三项，实际成本依次为 $1,1,1,3$，势依次为 $0\to 1\to 2\to 3\to 0$，摊还成本为 $2,2,2,0$。总实际与总摊还成本都是 6。若从已有三个元素的栈直接开始弹出，摊还成本仍为 0，实际却是 3；差额恰由初始势 $\mathrm{\Phi }(D_0)=3$ 支付，不能在总界中省略。

二进制计数器的完整逐位计算见摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。。其昂贵进位会消耗末尾的 $1$，所以适合数 $1$ 的个数；若改用“位串的数值”，递增反而总使势增加 $1$，无法抵消长进位。非负性只保证账本合法，能否得到有用的界还取决于势与操作结构是否匹配。

非负势是方便的充分条件，并非唯一合法选择。更一般地，只要所有可能终态满足 $\mathrm{\Phi }(D_m)\ge L$，总成本就不超过总摊还成本加 $\mathrm{\Phi }(D_0)-L$；这个差额须由已声明的初态与模型统一控制。给势整体加一个常数不改变任何单步摊还成本，也不改变这个差额。随意挑一个能无限下降的函数，则可能靠不断透支制造虚假的低成本。摊还界是任意操作序列上的确定总界，不等于随机输入期望。

势能法建立在摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。与状态上的势函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。之上。先让势函数表达需要长期维护的不变量，再逐类核对操作如何改变它，便能系统地设计证明并界定任意长操作序列的总成本，而不是只解释某一个昂贵步骤。

伸展树理路伸展树splay tree · 伸展树每次访问后把目标旋至根，并以势能获得序列敏感摊还界的自调整搜索树。把辅助树形状编码进势，Fibonacci 堆理路Fibonacci 堆Fibonacci heap以延迟合并和级联切断取得常数摊还插入、合并与减键的可并优先队列。用根数与标记节点数为延迟合并和级联切断记账；两页分别给出具体势函数，本页不重复其旋转或堆操作。栈的批量弹出、动态数组和并查集也使用同一望远镜机制，会计法则可视为把总势拆成存放在各对象上的 credits。这样的摊还结论控制操作序列总成本，却不承诺每次操作的尾延迟。

算法分析中的“势”还有别的量词。竞争分析理路竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。常令势比较在线算法与离线最优的两个状态，用单步不等式累积竞争比；乘法权重更新理路乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。与Hedge理路指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。跟踪总权重或对数配分函数，以界定累计 regret。它们都利用势的增量，却不把真实数据结构操作成本重新分摊，不能因此统称为摊还时间复杂度。