势能方法

概述

势能方法（Potential Method）是三种摊还分析方法中灵活性最高的方法。它将”信用”的概念从16.2 记账方法中的具体对象推广为整个数据结构的势能函数 $\Phi$，通过势能的变化量来调节每个操作的实际代价，得到摊还代价。核心公式为 ${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$。

定义

势能方法

设数据结构在第 $i$ 个操作后的状态为 $D_i$（初始状态 $D_0$），定义势能函数 $\Phi :D\to \mathbb{R}$，满足：

• 初始条件：$\Phi (D_0)=0$
• 非负条件：对所有 $i\ge 1$，$\Phi (D_i)\ge 0$

第 $i$ 个操作的摊还代价定义为： ${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$

其中 $c_i$ 为实际代价，$\Phi (D_i)-\Phi (D_{i-1})$ 为势能变化量（$\Delta {\Phi }_i$）。

则 $n$ 个操作的总代价满足： ${\sum }_{i=1}^n{c}_i={\sum }_{i=1}^n{\hat{c}}_i-\Phi (D_n)+\Phi (D_0)\le {\sum }_{i=1}^n{\hat{c}}_i$

核心性质

1. 全局势能视角：与记账方法将信用存储在具体对象上不同，势能方法将信用建模为整个数据结构的势能，是一个全局量。这使得势能方法能够处理信用在对象间转移的复杂场景。
2. 物理类比：势能方法可以直接类比物理学中的势能概念——当数据结构”状态升高”（势能增加）时，相当于存储能量；当状态”降低”（势能释放）时，释放的能量补偿了操作的高代价。这种直觉有助于设计合适的势能函数。
3. 灵活性最高：三种方法中，势能方法能够处理最复杂的场景。当信用需要在不同对象之间流动时，记账方法难以处理，而势能方法可以自然应对。
4. 势能函数设计是核心难点：势能方法的关键在于设计合适的势能函数 $\Phi$。好的势能函数需要满足非负条件，同时使得 ${\hat{c}}_i$ 尽可能小（即给出紧的界）。

核心公式推导

从摊还代价的定义出发：

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

这是一个望远镜求和（telescoping sum）：

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

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

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

经典应用

栈操作

定义势能函数 $\Phi (D_i)=$ 栈中当前元素个数。

• PUSH：$\hat{c}=1+(k+1)-k=2$
• POP：$\hat{c}=1+(k-1)-k=0$
• MULTIPOP(S, k')：$\hat{c}=k^{\prime }+(k-k^{\prime })-k=0$

每个操作摊还 $O(1)$。

二进制计数器

定义势能函数 $\Phi (D_i)=$ 计数器中 $1$ 的个数 $b_i$。

设 INCREMENT 翻转了 $t_i$ 位（其中 $t_i-1$ 位从 $1\to 0$，$1$ 位从 $0\to 1$）：

${\hat{c}}_i=t_i+b_i-b_{i-1}$

由于翻转 $t_i-1$ 个 $1\to 0$ 和 $1$ 个 $0\to 1$，所以 $b_i=b_{i-1}-(t_i-1)+1=b_{i-1}-t_i+2$。

代入得：${\hat{c}}_i=t_i+(b_{i-1}-t_i+2)-b_{i-1}=2$

每次 INCREMENT 的摊还代价恰好为 $2$。

高级应用

• Splay Tree：利用势能函数 $\Phi (T)={\sum }_{x\in T}\log (\text{size}(x))$（对数势能），证明每次操作的摊还代价为 $O(\log n)$

并查集（Union-Find）

在 不相交集合森林 中，利用势能方法分析按秩合并+路径压缩的组合复杂度。

定义势能函数 ${\Phi }_q={\sum }_{i=1}^n\alpha (n)\cdot \text{rank}(x_i)$（其中 $\text{rank}(x_i)$ 为节点 $x_i$ 的秩），通过分析 UNION 和 FIND-SET 操作中势能的变化，证明 $m$ 次操作的总摊还代价为 $O(m\alpha (n))$，其中 $\alpha (n)$ 是 反阿克曼函数。

这是势能方法处理”信用在对象间转移”场景的经典案例——路径压缩将深层节点的势能释放，补偿了遍历路径的代价。

• 斐波那契堆：利用度数相关的势能函数，证明 Decrease-Key 摊还 $O(1)$

三种方法对比

维度	聚合分析	记账方法	势能方法
信用存储	无显式信用	具体对象	整个数据结构
摊还代价	统一	可不同	可不同
灵活性	低	中	高
设计难度	低	中	高
适用范围	简单场景	中等场景	复杂场景

参见

• 摊还分析 — 势能方法所属的总体分析框架
• 16.1 聚合分析 — 最简单的摊还分析方法
• 16.2 记账方法 — 基于具体对象信用的方法
• 16.4 动态表 — 势能方法的典型应用案例
• 不相交集合森林 — 势能方法分析的经典案例
• 路径压缩 — 势能释放的关键操作
• 反阿克曼函数 — 分析结果中的关键函数