势能方法

概述

势能方法（Potential Method）是摊还分析的三种方法之一。它定义一个势能函数 $\Phi$，将数据结构的状态映射为一个非负实数，代表”预存的势能”。第 $i$ 步操作的摊还代价等于实际代价加上势能变化。通过合理设计势能函数，可以将高代价操作的代价”分摊”到低代价操作上。

定义

势能方法（Potential Method）

设数据结构在第 $i$ 次操作后的状态为 $D_i$，第 $i$ 次操作的实际代价为 $c_i$。定义势能函数 $\Phi :D\to {\mathbb{R}}_{\ge 0}$，满足 $\Phi (D_0)=0$（初始势能为零）。

第 $i$ 次操作的摊还代价定义为：

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

即：摊还代价 = 实际代价 + 势能增量。

对 $n$ 次操作求和：

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

由于 $\Phi (D_n)\ge 0$ 且 $\Phi (D_0)=0$，有：

${\sum }_{i=1}^n{\hat{c}}_i\ge {\sum }_{i=1}^n{c}_i$

因此，摊还代价的总和是实际代价总和的上界。

核心性质

性质	描述	备注
势能非负	$\Phi (D_i)\ge 0$ 对所有 $i$	保证摊还代价是实际代价的上界
初始势能为零	$\Phi (D_0)=0$	确保总摊还代价不小于总实际代价
势能可增可减	操作后势能可能增加或减少	增加时”存钱”，减少时”花钱”
灵活性	势能函数的设计空间大	比记账方法更灵活

势能方法的直觉

势能方法类似于物理中的势能概念：

• 当操作的实际代价低于摊还代价时，势能增加（“存入”多余的能量）
• 当操作的实际代价高于摊还代价时，势能减少（“消耗”之前存储的能量）
• 关键约束：势能永远不能为负（不能”透支”）

经典应用：动态表扩容

动态表的势能分析

动态表满时容量加倍。定义势能函数：

$\Phi (T)=2\cdot T.\text{num}-T.\text{size}$

其中 $T.\text{num}$ 为当前元素数，$T.\text{size}$ 为表容量。

• 不触发扩容的插入：${\hat{c}}_i=1+2=3=O(1)$
• 触发扩容的插入：${\hat{c}}_i=1+n+(0-(2n-2n))=1+n+0-0$… 经详细计算得 ${\hat{c}}_i=O(1)$

因此，每次插入的摊还代价为 $O(1)$。

摊还分析三种方法对比

方法	核心思想	优点	缺点
聚合分析	直接求总代价再平均	最简单	不给出单个操作的摊还代价
记账方法	为操作赋予”信用”	直观	信用分配需要技巧
势能方法	定义势能函数	最灵活、最强大	势能函数设计需要经验

参见

• 摊还分析 — 势能方法所属的分析框架
• 散列表 — 动态表扩容的势能分析应用