Splay 复杂度分析

众所周知，Splay 的复杂度分析需要用一个叫做“势能分析法”的东西。

所以首先得解释一下这个势能分析是个什么来头。

势能分析法

简介

我们在某些时间复杂度是均摊的问题上，往往进行草率的感性理解，虽然理解了复杂度是从何而来，但严谨证明却比较麻烦。

我们可以考虑在单次操作复杂度不好分析，可能复杂很大的时候（例如 splay 操作），为数据结构引入势能概念，当时间松时存储势能，当时间紧时释放势能。

可以理解为“存款”和“取款”。在某次操作耗时较少时，将盈余的时间分摊给其他耗时较长的操作。

一些定义

设一个数据结构为 $D_0$，进行 $m$ 次操作，分别为 $c_1, c_2, \ldots, c_m$。定义第 $k$ 次操作后的数据结构为 $D_k$。定义势函数 $\Phi(D_k)$ 表示数据结构 $D_k$ 的势能，这个函数将一个数据结构映射到一个实数上。

我们定义一次操作的摊还代价为 $\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i - 1})$，即本次操作的实际代价加上操作前后数据结构势能的变化量。

这样，$m$ 次操作的总摊还代价为

$$\sum_{i = 1}^{m} \hat{c_i} = \sum_{i = 1}^{m} c_i + \Phi(D_m) - \Phi(D_0)$$

因此，

$$\sum_{i = 1}^{m} c_i = \sum_{i = 1}^{m}\hat{c_i} + \Phi(D_0) - \Phi(D_m)$$

这样，我们通过得出 $\sum_{i = 1}^{m} \hat{c_i}$ 和 $\Phi(D_0) - \Phi(D_m)$ 的上界，就可以求出 $\sum_{i = 1}^{m} c_i$ 的上界了！

Splay 的势能分析

首先通过观察可以发现，Splay 的所有操作的代价都可以理解为常数倍的 splay 操作。

因此我们只需考虑 splay 操作。

设一个 Splay 中共 $n$ 个点，每个点对应的子树大小为 $s(i)$，每个点的势能 $\phi(i) = \left\lceil\log_2 s(i)\right\rceil$。

整个 Splay 的总势能为 $\Phi(D) = \sum_{i = 1}^{n} \phi(i)$。

splay 操作有三种情况，下面分类讨论。

zig (zag)

当 $x$ 的父节点为根时，我们通过一次单旋将 $x$ 旋转到根。

$$\Delta\Phi = \phi(x') + \phi(y') - \phi(x) - \phi(y)$$

$$\because \phi(x') = \phi(y)$$

$$\therefore \Delta\Phi = \phi(y') - \phi(x)$$

$$\because \phi(x') \ge \phi(y')$$

$$\therefore \Delta\Phi = \phi(y') - \phi(x) \le \phi(x') - \phi(x)$$

因为 zig 操作需要 rotate 一次，rotate 是 $O(1)$ 的，所以

$$\hat{c}_{\mathrm{zig}} = \Delta\Phi + 1 \le \phi(x') - \phi(x) + 1$$

同理可证 zag 的摊还代价，因为 zig 和 zag 是对称的。

zig-zig (zag-zag)

当 $x$ 与父节点的儿子类型相同的时候，先旋转 $x$ 的父节点，再旋转 $x$。

则

$$\Delta\Phi = \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z)$$

$$\because \phi(x') = \phi(z)$$

$$\therefore \Delta\Phi = \phi(y') + \phi(z') - \phi(x) - \phi(y)$$

$$\because \phi(x') \ge \phi(y'), \phi(x) \le \phi(y)$$

$$\therefore \Delta\Phi \le \phi(x') + \phi(z') - 2\phi(x)$$

我们知道，当 $x, y > 0, x + y \le 1$ 时，

$$\begin{aligned} \because (x - y)^2 & \ge 0\\ \therefore x^2 - 2xy + y^2 & \ge 0\\ \therefore x^2 + 2xy + y^2 & \ge 4xy\\ \therefore (x + y)^2 & \ge 4xy \\ \therefore xy & \le \frac{(x + y)^2}{4}\\ \log_2 x + \log_2 y & = \log_2 xy \\ & \le \log_2 \frac{(x + y)^2}{4} \\ \end{aligned}$$

取等当且仅当 $x = y$。

当 $x + y$ 取最大值 $1$ 时，$\log_2\frac{(x + y)^2}{4}$ 取最大值 $-2$。

因此

$$\log_2 x + \log_2 y \le -2$$

那么，

$$\begin{aligned} \phi(x) + \phi(z') - 2\phi(x') & = (\phi(x) - \phi(x')) + (\phi(z') - \phi(x')) \\ & = (\log_2 s(x) - \log_2 s(x')) + (\log_2 s(z') - \log_2 s(x')) \\ & = \log_2 \frac{s(x)}{s(x')} + \log_2 \frac{s(z')}{s(x')} \\ \end{aligned}$$

$$\because s(x) + s(z') \le s(x') \\$$

$$\therefore \frac{s(x)}{s(x')} + \frac{s(z')}{s(x')} \le 1 \\$$

$$\because \frac{s(x)}{s(x')} > 0 , \frac{s(z')}{s(x')} > 0$$

$$\therefore \log_2 \frac{s(x)}{s(x')} + \log_2 \frac{s(z')}{s(x')} \le -2$$

$$\therefore \phi(x) + \phi(z') - 2\phi(x') \le -2$$

$$\begin{aligned} \therefore \Delta\Phi & \le \phi(x') + \phi(z') - 2\phi(x) \\ & = (3\phi(x') - 3\phi(x)) + (\phi(x) + \phi(z') - 2\phi(x)) \\ & \le 3\phi(x') - 3\phi(x) - 2 \end{aligned}$$

因为 zig-zig 操作需要 rotate 两次，所以

$$\hat{c}_{\mathrm{zigzig}} = \Delta\Phi + 2 \le 3\phi(x') - 3\phi(x)$$

同理可证 zag-zag 的摊还代价，因为 zag-zag 和 zig-zig 是对称的。

zig-zag (zag-zig)

当 $x$ 与父节点的儿子类型不同时，旋转两次 $x$ 节点。

则

$$\Delta\Phi = \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z)$$

$$\because \phi(x') = \phi(z)$$

$$\therefore \Delta\Phi = \phi(y') + \phi(z') - \phi(x) - \phi(y)$$

$$\because \phi(x) \le \phi(y)$$

$$\begin{aligned} \therefore \Delta\Phi & \le \phi(y') + \phi(z') - 2\phi(x) \\ & = (2\phi(x') - 2\phi(x)) + (\phi(y') + \phi(z') - 2\phi(x')) \\ \end{aligned}$$

$$\because \frac{s(y')}{s(x')} > 0, \frac{s(z')}{s(x')} > 0, s(y') + s(z') \le s(x')$$

$$\therefore \phi(y') + \phi(z') - 2\phi(x') \le -2$$

$$\therefore \Delta\Phi \le 2\phi(x') - 2\phi(x) - 2$$

因为 zig-zag 操作需要 rotate 两次，所以

$$\hat{c}_{\mathrm{zigzag}} = \Delta\Phi + 2 \le 2\phi(x') - 2\phi(x)$$

可以再放缩一下，便于下一步计算。

$$\because \phi(x') - \phi(x) \ge 0$$

$$\therefore \hat{c}_{\mathrm{zigzag}} \le 3\phi(x') - 3\phi(x)$$

同理可证 zag-zig 操作的摊还代价，因为 zag-zig 和 zig-zag 是对称的。

一次 splay 操作

回顾一下，我们有：

$$\hat{c}_{\mathrm{zig}} \le \phi(x') - \phi(x) + 1 \le 3(\phi(x') - \phi(x)) + 1 \\ \hat{c}_{\mathrm{zigzig}} \le 3(\phi(x') - \phi(x)) \\ \hat{c}_{\mathrm{zigzag}} \le 3(\phi(x') - \phi(x))$$

因此，我们将 $x$ 这个点旋转到根的时候，一路抵消，最后

$$\begin{aligned} \hat{c_i} & \le 3(\phi(\mathrm{root}) - \phi(x)) + 1 \\ & = 3\log_2 \frac{n}{s(x)} + 1 \\ & \le 3\log_2 n + 1 \\ & = O(\log n) \end{aligned}$$

所有操作

$$\sum_{i = 1}^{m}\hat{c_i} = O(m\log n)$$

又因为

$$0 \le \Phi(D) \le n\log_2 n$$

所以

$$\Phi(D_0) - \Phi(D_n) = O(n\log n)$$

因此

$$\begin{aligned} \sum_{i = 1}^{n} c_i & = \sum_{i = 1}^{n}\hat{c_i} + \Phi(D_0) - \Phi(D_n) \\ & = O(m\log n) + O(n\log n) \\ & = O((n + m)\log n) \end{aligned}$$

证毕。