splay 时间复杂度简要分析

    splay 时间复杂度简要分析

    splay 的复杂度分析

    势能分析

    在数据结构问题中,我们往往难以估计第 ii 次的实际时间开销 tit_i。

    所以我们要引入一些势能分析的概念:

    • 设 ϕi\phi_i 表示:第 ii 次操作过后,数据结构的势能值。
    • 记 ai=ti+ϕi−ϕi−1a_i = t_i + \phi_i - \phi_{i - 1},即第 ii 次操作的均摊时间。

    注意:确定势能值的势函数是需要我们自己确定的,寻找一个优秀的势函数往往可以更容易解决问题。

    假设执行了 mm 次操作,那么总的实际时间为:

    ∑1≤i≤mti=∑1≤i≤mai+ϕ0−ϕm\sum\limits_{1 \leq i \leq m} t_i = \sum\limits_{1 \leq i \leq m} a_i + \phi_0 - \phi_m

    所以知道了 ai,ϕa_i, \phi 的复杂度就可以求出总的实际时间了。

    在 splay 中,我们取这样的一个势函数:

    • 设当前状态下,节点 xx 的势能值 F(x)=log⁡sizexF(x) = \log \text{size}_x。
    • 设当前状态下,整棵 splay 的势能值 ϕ=∑1≤i≤nF(i)\phi = \sum\limits_{1 \leq i \leq n} F(i)。

    接下来要证明的结论是:

    ai≤3(F(x′)−F(x))+1=O(log⁡nsizex)=O(log⁡n)\begin{aligned}a_i & \leq 3(F(x') - F(x)) + 1 \\ & = \mathcal{O}\left(\log \frac{n}{\text{size}_x}\right) = \mathcal{O}(\log n)\end{aligned}

    其中 F(x),F(x′)F(x), F(x') 分别表示伸展 xx 前和伸展 xx 后节点 xx 的势能值。

    双旋 splay 的三种旋转

    来回顾一下双旋 splay 的三种旋转:

    1. 当 xx 的父亲 pp 是根节点时,直接 zig/zag xx。

    2. 当 xx 和上两代祖先位于一条链上:先 zig/zag pp,再 zig/zag xx。

    3. 当 xx 和上两代祖先分叉时:先 zig/zag xx,再 zig/zag xx。

    第一种旋转的均摊分析(以 zig 为例)

    单旋.png

    分析:

    • 时间开销:旋转了一次。

    • 势能变化:子树大小只有节点 x,yx, y 发生了变化,故只有节点 x,yx, y 的势能值发生了变化。

    所以可以得到:

    azig=1+F(x′)+F(y′)−F(x)−F(y)=1+F(y′)−F(x)\begin{aligned}a_{\text{zig}} & = 1 + F(x') + F(y') - F(x) - F(y) \\& = 1 + F(y') - F(x)\end{aligned}

    适当放缩得:

    azig≤3(F(x′)−F(x))+1a_{\text{zig}} \leq 3(F(x') - F(x)) + 1

    第二种旋转的均摊分析(以 zig-zig 为例)

    第二种旋转.png

    分析:

    • 时间开销:旋转了两次。
    • 势能变化:子树大小只有节点 x,y,zx, y, z 发生了变化,故只有节点 x,y,zx, y, z 的势能值发生了变化。

    所以可以得到:

    azig-zig=2+F(x′)+F(y′)+F(z′)−F(x)−F(y)−F(z)=2+F(y′)+F(z′)−F(x)−F(y)\begin{aligned}a_{\text{zig-zig}} & = 2 + F(x') + F(y') + F(z') - F(x) - F(y) - F(z) \\& = 2 + F(y') + F(z') - F(x) - F(y)\end{aligned}

    然后你发现这个多出来的 22 非常令人不爽。

    注意到:

    F(x)+F(z′)−2⋅F(x′)≤log⁡sizex⋅sizez′sizex′2≤−2F(x) + F(z') - 2 \cdot F(x') \leq \log \frac{\text{size}_x \cdot \text{size}_{z'}}{\text{size}^2_{x'}} \leq -2

    (均值不等式即可证明,大家都会。)

    然后将这两个式子合并可以得到:

    azig-zig≤2⋅F(x′)+F(y′)−2⋅F(x)−F(y)a_{\text{zig-zig}} \leq 2 \cdot F(x') + F(y') - 2 \cdot F(x) - F(y)

    适当放缩得:

    azig-zig≤3(F(x′)−F(x))a_{\text{zig-zig}} \leq 3(F(x') - F(x))

    第三种旋转的均摊分析(以 zig-zag 为例)

    第三种旋转.png

    分析:

    • 时间开销:旋转了两次。
    • 势能变化:子树大小只有节点 x,y,zx, y, z 发生了变化,故只有节点 x,y,zx, y, z 的势能值发生了变化。

    所以可以得到:

    azig-zag=2+F(x′)+F(y′)+F(z′)−F(x)−F(y)−F(z)=2+F(y′)+F(z′)−F(x)−F(y)\begin{aligned}a_{\text{zig-zag}} & = 2 + F(x') + F(y') + F(z') - F(x) - F(y) - F(z) \\& = 2 + F(y') + F(z') - F(x) - F(y)\end{aligned}

    注意到:

    F(x)+F(z′)−2⋅F(x′)≤log⁡sizex⋅sizez′sizex′2≤−2F(x) + F(z') - 2 \cdot F(x') \leq \log \frac{\text{size}_x \cdot \text{size}_{z'}}{\text{size}^2_{x'}} \leq -2

    然后将这两个式子合并可以得到:

    azig-zag≤2⋅F(x′)+F(y′)−2⋅F(x)−F(y)a_{\text{zig-zag}} \leq 2 \cdot F(x') + F(y') - 2 \cdot F(x) - F(y)

    适当放缩得:

    azig-zag≤3(F(x′)−F(x))a_{\text{zig-zag}} \leq 3(F(x') - F(x))

    顺次组合所有操作

    在伸展一个节点 xx 的时候,将每次旋转的贡献式子连接起来,消除相邻的项,可以得到:

    ai≤3(F(x′)−F(x))+1=O(log⁡nsizex)=O(log⁡n)\begin{aligned}a_i & \leq 3(F(x') - F(x)) + 1 \\& = \mathcal{O}\left(\log \frac{n}{\text{size}_x}\right) = \mathcal{O}(\log n)\end{aligned}
    • 因为 ai=O(log⁡n)a_i = \mathcal{O}(\log n),所以 ∑1≤i≤mai=O(mlog⁡n)\sum\limits_{1 \leq i \leq m} a_i = \mathcal{O}(m \log n)。
    • 因为 0≤ϕ≤nlog⁡n0 \leq \phi \leq n \log n,所以 ϕ0−ϕm=O(nlog⁡n)\phi_0 - \phi_m = \mathcal{O}(n \log n)。

    于是 splay 的时间复杂度即为 O((n+m)log⁡n)\mathcal{O}((n + m) \log n)。