【教程】势能分析法与 Splay 时间复杂度证明

ID: 600

客观题

尝试: 1

已通过: 1

难度: 7

上传者:

boya

标签>

教程

一、为什么我们需要势能分析法？

在《均摊复杂度》中，我们学习了聚合分析和记账法，它们能很好地分析vector、单调栈这类简单数据结构。但当我们面对Splay 树、Link-Cut Tree、斐波那契堆这些复杂数据结构时，这两种方法就显得力不从心了：

聚合分析需要直接计算总时间，对于操作之间相互影响极强的数据结构几乎不可能

记账法需要为每个操作分配虚拟费用，对于复杂操作很难找到合适的费用值

势能分析法是均摊分析中最强大、最通用的方法。它通过定义一个 "势能函数" 来量化数据结构的 "状态"，将昂贵操作的成本分摊到之前导致数据结构 "变差" 的操作上。对于信息竞赛选手来说，掌握势能分析法不仅能让你深刻理解高级数据结构的性能本质，更能培养你严谨的算法分析思维 —— 这是区分金牌选手和普通选手的关键能力之一。

二、势能分析法的核心原理

2.1 基本定义与公式

我们先严格定义势能分析法的所有概念，这是后续所有推导的基础：

数据结构状态：设 $S_0$ 是数据结构的初始状态， $S_i$ 是执行第 $i$ 个操作后的状态。
势能函数： $\Phi$ 是一个将数据结构状态映射到非负实数的函数，即 $\Phi(S_i) \geq 0$ 对所有 $i$ 成立。
- 直观理解： $\Phi(S_i)$ 表示数据结构在状态 $S_i$ 下"积累的可用于支付未来昂贵操作的能量"
- 势能越高，数据结构的状态越"差"（越不平衡、越无序），未来可能需要更昂贵的操作
实际时间： $c_i$ 是执行第 $i$ 个操作的实际时间（即基本操作的次数）
均摊时间：第 $i$ 个操作的均摊时间 $a_i$ 定义为：
$a_i = c_i + \Phi(S_i) - \Phi(S_{i-1})$
即：均摊时间 = 实际时间 + 势能变化量

2.2 为什么这个定义是有效的？

我们来计算 $n$ 个操作的总均摊时间：

$$\sum_{i=1}^n a_i = \sum_{i=1}^n [c_i + \Phi(D_i) - \Phi(D_{i-1})]$$

这是一个特殊求和，中间项全部抵消，得到：

$$\sum_{i=1}^n a_i = \sum_{i=1}^n c_i + \Phi(S_n) - \Phi(S_0)$$

因为我们要求 $\Phi(S_i) \geq 0$ 且通常取 $\Phi(S_0)=0$ （初始状态势能为 $0$ ），所以：

\sum_{i=1}^n a_i \geq \sum_{i=1}^n c_i

核心结论：总均摊时间是总实际时间的一个上界。如果我们能证明每个操作的均摊时间 $a_i = O(f(n))$ ，那么任意 $n$ 个操作的总实际时间一定是 $O(nf(n))$ 。

2.3 势能分析法的一般步骤

选择一个合适的势能函数（这是最关键也是最难的一步）
对每个操作，计算其实际时间 $c_i$
计算操作前后的势能变化量 $\Delta\Phi = \Phi(S_i) - \Phi(S_{i-1})$
代入公式 $a_i = c_i + \Delta\Phi$ ，求出均摊时间的上界

更好理解势能分析法，可参考【教程】均摊复杂度

四、Splay树的基本操作回顾

在分析 Splay 树的复杂度之前，我们必须先明确 Splay 树的核心操作——伸展(Splay)。Splay 树的所有其他操作（查找、插入、删除）都基于伸展操作。

4.1 伸展操作的目标

将指定节点 $x$ 通过一系列旋转操作移动到根节点。

4.2 三种基本旋转方式

Splay 操作由以下三种基本旋转组成，根据 $x$ 、 $x$ 的父节点 $p(x)$ 、 $x$ 的祖父节点 $g(x)$ 的位置关系分类：

Zig（单旋）：当 $p(x)$ 是根节点时，执行一次单旋
- 若 $x$ 是左孩子，执行右旋；若 $x$ 是右孩子，执行左旋
- 实际时间： $c=1$ （一次旋转）
Zig-Zig（同方向双旋）：当 $p(x)$ 不是根节点，且 $x$ 和 $p(x)$ 同为左孩子或同为右孩子时 (一字型旋转)
- 先旋转 $p(x)$ ，再旋转 $x$
- 实际时间： $c=2$ （两次旋转）
Zig-Zag（反方向双旋）：当 $p(x)$ 不是根节点，且 $x$ 和 $p(x)$ 一个是左孩子一个是右孩子时 (之字型旋转)
- 先旋转 $x$ ，再旋转 $x$ （此时 $x$ 已经是 $p(x)$ 的父节点）
- 实际时间： $c=2$ （两次旋转）

重要性质：每次旋转操作只会改变 $O(1)$ 个节点的子树大小。

五、Splay树的势能函数选择

这是整个 Splay 复杂度分析中最巧妙、最关键的一步。我们需要选择一个势能函数，它能：

准确衡量树的"不平衡程度"
使得每次旋转的均摊时间有一个紧的上界

5.1 节点的秩(Rank)

对于 Splay 树中的任意节点 $x$ ，定义 $siz(x)$ 为以 $x$ 为根的子树的大小（包括 $x$ 本身）。

定义节点 $x$ 的秩为：

r(x) = \log_2 siz(x)

5.2 Splay树的势能函数

定义整个 Splay 树的势能为所有节点的秩之和：

\Phi = \sum_{x \in \text{树中所有节点}} r(x)

为什么选择这个势能函数？

对于一棵完全平衡的二叉树，每个节点的秩大约是 $\log n$ ，总势能是 $O(n \log n)$
对于一棵退化成链的二叉树，根节点的秩是 $\log n$ ，下一个节点的秩是 $\log(n-1)$ ，...，叶子节点的秩是 $\log 1=0$ ，总势能是 $O(\log {n!})$ = $O(n \log n)$
当树变得更平衡时，大多数节点的秩会增加，势能会增加；当树变得更不平衡时，势能会减少
最重要的是：这个势能函数能让我们推导出 Splay 操作的均摊时间是 $O(\log n)$

六、Splay树时间复杂度的完整推导

我们的目标是证明：将任意节点 $x$ 伸展到根节点的均摊时间是 $O(\log n)$ 。

6.1 关键引理：对数不等式

在推导之前，我们先证明一个后续会反复用到的对数不等式：

如果 $\text{size}(p)\ge\text{size}(x)+\text{size}(y)$ ，那么有 $2r(𝑝) −r(𝑥) −r(𝑦) ≥2r(p) - r(x) - r(y) \geq 2$

证明：$2r(𝑝)−r(𝑥)−r(𝑦)=\log {\frac{⁡{size(𝑝)}^2}{size(𝑥)⋅size(𝑦)}}>\log⁡{\frac{(size(𝑥)+size(𝑦))^2}{ size(𝑥)⋅size(𝑦)}}≥log{⁡4}=2$

6.2 分析单次旋转的均摊时间

我们分别分析三种旋转方式的均摊时间。为了方便，我们用不带撇的符号表示旋转前的状态，带撇的符号表示旋转后的状态。

情况1：Zig（单旋）

首先看单旋示意图：

单旋示意图

单旋对应两条性质：

1. $siz(p)=siz'(x)$ ，即 $r(p)=r'(x)$
1. $siz'(p)\le siz'(x)$ ,即 $r'(p)\le r'(x)$
实际时间 $c=1$
旋转后，只有 $x$ 和 $p(x)$ 的子树大小发生了变化，其他节点的秩不变
因此势能变化 $\Delta\Phi = [r'(x) + r'(p(x))] - [r(x) + r(p(x))]$
代入均摊时间公式：
$a = 1 + r'(x) + r'(p(x)) - r(x) - r(p(x))$ $= 1 + r'(p(x)) - r(x)$ $\le 1 + r'(x) - r(x)$ $\le 1 + 3(r'(x) - r(x))$

情况2：Zig-Zig（同方向双旋）

首先请查看同方向双旋示意图：

同方向双旋示意图

同方向双旋两条性质：

1.注意到旋转后 $x$ 变成了原来 $g(x)$ 的位置，所以 $siz'(x) = siz(g(x))$ ，即 $r'(x) = r(g(x))$
1. $siz'(x) \le siz(x)+siz(g)$ ，得到 $2 \le 2r'(x)-r(x)-r'(g)$
证明：$siz'(x)=3+siz(A)+siz(B)+siz(C)+siz(D)=(1+siz(A)+siz(B))+(1+siz(C)+siz(D))+1 \le siz(x)+siz'(g)$ ，也就是 $siz'(x) \le siz(x)+siz(g)$ ，由不等式得到 $2r'(x)-r(x)-r'(g)\ge 2$ ，得证。
实际时间 $c=2$
旋转后，只有 $x$ 、 $p(x)$ 、 $g(x)$ 的子树大小发生了变化
势能变化 $\Delta\Phi = [r'(x) + r'(p(x)) + r'(g(x))] - [r(x) + r(p(x)) + r(g(x))]$
现在计算均摊时间：
$$a = 2 + [r'(x) + r'(p(x)) + r'(g(x)) - r(x) - r(p(x)) - r(g(x))]$$
代入 $r'(x) = r(g(x))$ ：
$a = 2 + [r'(p(x)) + r'(g(x)) - r(x) - r(p(x))]$
由性质2，将 $2$ 替换掉，得到

a = 2 + [r'(p(x)) + r'(g(x)) - r(x) - r(p(x))]

$$a \le [2r'(x)-r(x)-r'(g(x))] + [r'(p(x)) + r'(g(x)) - r(x) - r(p(x))]$$

得到 $a \le 3(r'(x)-r(x))$

情况3：Zig-Zag（反方向双旋）

首先请查看反方向双旋示意图：

反方向双旋示意图

反方向双旋两条性质：

1.注意到旋转后 $x$ 变成了原来 $g(x)$ 的位置，所以 $r'(x) = r(g(x))$
2. $siz'(p(x)) + siz'(g(x)) \leq siz'(x)$ 得到
$r'(p) + r'(g) \leq 2r'(x) -2$
证明：$siz'(x)=3+siz(A)+siz(B)+siz(C)+siz(D)=(1+siz(A)+siz(B))+(1+siz(C)+siz(D))+1$ 得到 $siz'(x)>siz'(p)+siz(g)$ ，根据对数不等式性质得证。
实际时间 $c=2$
同样，只有 $x$ 、 $p(x)$ 、 $g(x)$ 的子树大小发生了变化
势能变化 $\Delta\Phi = [r'(x) + r'(p(x)) + r'(g(x))] - [r(x) + r(p(x)) + r(g(x))]$
计算均摊时间：
$$a = 2 + [r'(x) + r'(p(x)) + r'(g(x)) - r(x) - r(p(x)) - r(g(x))]$$
代入 $r'(x) = r(g(x))$ ：
$a = 2 + [r'(p(x)) + r'(g(x)) - r(x) - r(p(x))]$
由性质2 ， $r'(p)+r'(x) \ge 2r'(x)-2$ ,替换掉上式中 $r'(p(x)) + r'(g(x))$ 得到
$$a \leq 2r'(x) - 2r(x) = 2[r'(x) - r(x)] \leq 3[r'(x) - r(x)]$$

6.3 汇总单次旋转的均摊时间

我们得到了一个统一的结论：对于 Splay 操作中的任意一次旋转（Zig、Zig-Zig、Zig-Zag），其均摊时间不超过 $3[r'(x) - r(x)]$ ，其中 $r(x)$ 是旋转前 $x$ 的秩， $r'(x)$ 是旋转后 $x$ 的秩。

6.4 整个Splay操作的均摊时间

Splay操作是由一系列旋转组成的，直到 $x$ 成为根节点。设整个Splay操作包含 $k$ 次旋转，第 $i$ 次旋转前 $x$ 的秩为 $r_i(x)$ ，旋转后为 $r_{i+1}(x)$ 。

则整个 Splay 操作的总均摊时间为：

$$a_{\text{总}} = \sum_{i=1}^k a_i \leq \sum_{i=1}^k 3[r_{i+1}(x) - r_i(x)]$$

这又是一个特殊求和！中间项全部抵消，得到：

a_{\text{总}} \leq 3[r_{k+1}(x) - r_1(x)]

注意上面是忽略最后一次单旋，如果最后多一次单旋，那么式子变为：

a_{\text{总}} \leq 3[r_{k+1}(x) - r_1(x)]+1

并不会影响时间复杂度。

其中：

$r_1(x)$ 是 Splay 操作开始前 $x$ 的秩，最小值为 $\log_2 1 = 0$
$r_{k+1}(x)$ 是 Splay 操作结束后 $x$ 的秩，此时 $x$ 是根节点，所以 $r_{k+1}(x) = \log_2 n$

因此：

$$a_{\text{总}} \leq 3(\log_2 n - 0) = 3\log_2 n = O(\log n)$$

核心定理：将任意节点 $x$ 伸展到根节点的均摊时间复杂度是 $O(\log n)$ 。

七、Splay树其他操作的复杂度分析

Splay树的所有其他操作都基于伸展操作，因此它们的均摊时间复杂度也都是 $O(\log n)$ 。

7.1 查找操作

步骤：从根节点开始，按照二叉搜索树的规则查找目标节点 $x$
无论是否找到，都将最后访问的节点伸展到根
查找过程的实际时间等于从根到 $x$ 的路径长度，而伸展操作的均摊时间是 $O(\log n)$
可以证明，整个查找操作的均摊时间是 $O(\log n)$

7.2 插入操作

步骤：按照二叉搜索树的规则插入新节点 $x$ ，然后将 $x$ 伸展到根
插入过程的实际时间是 $O(h)$ （ $h$ 是树的高度），伸展操作的均摊时间是 $O(\log n)$
总均摊时间： $O(\log n)$

7.3 删除操作

步骤：将待删除节点 $x$ 伸展到根，然后删除 $x$ ，将左子树的最大值节点伸展到根，再将右子树接上去
两次伸展操作的均摊时间都是 $O(\log n)$
总均摊时间： $O(\log n)$

八、竞赛中的 Splay 树：注意事项与常见误区

8.1 关于常数因子

我们推导的 Splay 操作均摊时间是 $3\log_2 n$ ，常数因子约为 3
相比之下，线段树的常数因子约为 2，Treap 的常数因子约为 2.5
因此，在竞赛中，如果能用线段树或 Treap 解决的问题，一般不用 Splay
但 Splay 有其独特的优势：支持区间操作（如区间翻转、区间删除）和访问局部性优化

8.2 常见误区

误区1：Splay 树的最坏时间复杂度是 $O(log n)$
- 错误！Splay 树的单次操作最坏时间复杂度是 O(n)（当树退化成链时）
- 但任意 $m$ 个操作的总时间复杂度是 $O(m log n)$ ，这是均摊复杂度保证的
误区2：势能函数可以随便选
- 错误！势能函数的选择是分析的关键。如果选择不当，可能得到一个很松的上界，甚至无法证明复杂度
- Splay树的势能函数是经过精心设计的，是整个分析的精髓
误区3：Splay树的旋转顺序不影响复杂度
- 错误！Zig-Zig 和 Zig-Zag 的旋转顺序是严格规定的。如果改变旋转顺序（比如先旋转 x 再旋转 p(x) 对于 Zig-Zig 情况），均摊复杂度将不再是 $O(log n)$

九、总结

势能分析法是均摊分析中最强大的方法，通过定义势能函数将昂贵操作的成本分摊到之前的操作上
Splay树的势能函数是所有节点的秩之和，其中秩是子树大小的对数
Splay操作的均摊时间复杂度是O(log n)，这是通过分析三种旋转方式的均摊时间并望远镜求和得到的
Splay树的所有操作（查找、插入、删除）的均摊时间复杂度都是O(log n)
竞赛中，Splay树虽然常数较大，但在某些特定问题上具有不可替代的优势

掌握了Splay树的复杂度分析，你就已经掌握了信息竞赛中最难的算法分析之一。这不仅能让你更自信地使用Splay树，更能为你后续学习Link-Cut Tree等更高级的数据结构打下坚实的基础。

学习完毕

{{ select(1) }}

#edu3062. 【教程】势能分析法与 Splay 时间复杂度证明

一、为什么我们需要势能分析法？