势能法

势能法给数据结构状态赋一个非负“储蓄账户” $\mathrm{\Phi }$，把便宜操作积累的结构复杂度、即尚未支付的未来工作量，预付给昂贵操作，使每步“真实成本加势能变化”保持平稳。摊还成本定义为实际成本加势能变化；一串操作中间项望远镜消去，只剩初末势差。势函数不是物理能量，选择标准是让每类操作的摊还成本容易统一上界。

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

若初始势能不为零或最终势能可能为负，必须在总成本不等式中保留边界项；随意挑一个会剧烈负降的函数可能得到虚假的低摊还成本。摊还界是任意操作序列上的确定总界，不等于随机输入期望。

势能法建立在摊还分析公理库摊还分析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。它们都利用势的增量，却不把真实数据结构操作成本重新分摊，不能因此统称为摊还时间复杂度。