Splay 时间复杂度证明

· · 个人记录

设 w(x) 为 x 的子树大小的对数。

初始势能：\varphi(0)=\sum \log_{2}(sz(x))\le\sum\log_{2}n=n\log_{2}n。

一下假设 x 为 rotate 的点，p 为 father，g 为祖先。

1、Zig 操作

时间：\mathcal O(1)

显然有 w'(x)=w(p)（自己画个图就知道了）。

势能变化：\Delta_{\varphi_{Zig}}=w'(x)-w'(p)-w(x)-w(p)\le w'(p)-w(x)。

2、Zig-Zag 操作

时间：\Theta(1)。

势能变化：\Delta_{\varphi_{Zig-Zag}}=w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)=w'(x)+w'(g)-w(x)-w(p)\le w'(p)+w'(g)-2w(x)。

如果 sz(p)\ge sz(g)，有 2sz'(g)\le sz(x)\Rightarrow 1+w'(g)\le w'(x)。

如果 sz(p)<sz(g)，有 2sz'(p)\le sz'(x)\Rightarrow 1+w'(p)\le w'(x)。

有 w'(p)<w'(x),w'(q)<w'(x) 代入可得 \Delta_{\varphi_{Zig-Zag}}\le2w'(x)-w(x)-1。

假设一共执行 k 次操作，那么 \hat c=c+\Delta\phi=\sum2w'(x)-w(x)+\mathcal O(k)-\mathcal O(k)=\sum w'(x)-w(x)。

3、Zig-Zig 操作

时间：\mathcal O(1)

势能变化：\mathcal O_{\varphi_{Zig-Zig}}=t_{Zig-Zig}+w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)=w'(p)+w'(g)-w(x)-w(p)\le w'(x)+w'(g)-2w(x)\le 2(w'(x)-w(x))。

由于一次 Splay 操作中可能多次进行 Zig-Zag 操作，为了摊还实际代价，需存在常数 -1。qwq

因此 $2w'(x)-w'(g)-w(x)=\log_{2}(\frac{sz(x)^2}{sz(x)sz(g)})=\log_{2}(\frac{(sz(g)+sz(x)+2)^2}{sz(x)sz(g)})\le \log_{2}(\frac{2sz(x)sz(g)}{sz(x)sz(g)})=1$。 所以 $\Delta_{Zig-Zig}\le 3(w'(x)-w(x))-1$。 假设有 $k$ 次操作，$\hat c=c+\Delta\phi=\Theta(k)+\sum w'(x)-w(x)-\Theta(k)=\sum w'(x)-w(x)$。 得证。