splay 时间复杂度简要分析
splay 的复杂度分析
势能分析
在数据结构问题中,我们往往难以估计第 i 次的实际时间开销 t_i。
所以我们要引入一些势能分析的概念:
- 设 \phi_i 表示:第 i 次操作过后,数据结构的势能值。
- 记 a_i = t_i + \phi_i - \phi_{i - 1},即第 i 次操作的均摊时间。
注意:确定势能值的势函数是需要我们自己确定的,寻找一个优秀的势函数往往可以更容易解决问题。
假设执行了 m 次操作,那么总的实际时间为:
所以知道了 a_i, \phi 的复杂度就可以求出总的实际时间了。
在 splay 中,我们取这样的一个势函数:
- 设当前状态下,节点 x 的势能值 F(x) = \log \text{size}_x。
- 设当前状态下,整棵 splay 的势能值 \phi = \sum\limits_{1 \leq i \leq n} F(i)。
接下来要证明的结论是:
其中 F(x), F(x') 分别表示伸展 x 前和伸展 x 后节点 x 的势能值。
双旋 splay 的三种旋转
来回顾一下双旋 splay 的三种旋转:
-
当 x 的父亲 p 是根节点时,直接 zig/zag x。
-
当 x 和上两代祖先位于一条链上:先 zig/zag p,再 zig/zag x。
-
当 x 和上两代祖先分叉时:先 zig/zag x,再 zig/zag x。
第一种旋转的均摊分析(以 zig 为例)

分析:
-
时间开销:旋转了一次。
-
势能变化:子树大小只有节点 x, y 发生了变化,故只有节点 x, y 的势能值发生了变化。
所以可以得到:
适当放缩得:
第二种旋转的均摊分析(以 zig-zig 为例)

分析:
- 时间开销:旋转了两次。
- 势能变化:子树大小只有节点 x, y, z 发生了变化,故只有节点 x, y, z 的势能值发生了变化。
所以可以得到:
然后你发现这个多出来的 2 非常令人不爽。
注意到:
(均值不等式即可证明,大家都会。)
然后将这两个式子合并可以得到:
适当放缩得:
第三种旋转的均摊分析(以 zig-zag 为例)

分析:
- 时间开销:旋转了两次。
- 势能变化:子树大小只有节点 x, y, z 发生了变化,故只有节点 x, y, z 的势能值发生了变化。
所以可以得到:
注意到:
然后将这两个式子合并可以得到:
适当放缩得:
顺次组合所有操作
在伸展一个节点 x 的时候,将每次旋转的贡献式子连接起来,消除相邻的项,可以得到:
- 因为 a_i = \mathcal{O}(\log n),所以 \sum\limits_{1 \leq i \leq m} a_i = \mathcal{O}(m \log n)。
- 因为 0 \leq \phi \leq n \log n,所以 \phi_0 - \phi_m = \mathcal{O}(n \log n)。
于是 splay 的时间复杂度即为 \mathcal{O}((n + m) \log n)。