证明伸展树与动态树的时间复杂度

Splay时间复杂度证明

定理0

若x=y+z+1,那么$2\lg(x)-\lg(y)-\lg(z)\geq 2$

证明.

$2\lg(x)-\lg(y)-\lg(z)$
$=\lg((y+z+1)^2)-\lg(y)-\lg(z)$
$=\lg(\frac{(y+z+1)^2}{yz})$
$=\lg(\frac{2yz}{yz}+\frac{y^2+z^2+1+2y+2z}{yz})$
$\geq \lg(2+\frac{y}{z}+\frac{z}{y})$
$\geq \lg(2+2)$
$=2$

定理1

在一棵n个节点的Splay中,对一个节点进行splay操作的时间复杂度为均摊复杂度为$O(\log n)$

证明.

设size(x)表示节点x的子树大小。势能分析,设节点的势能$r(x)=\lg(size(x))$。

对于Zig-Zig或Zag-Zag的情况,势能的增量为
$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(x)+r'(z)-2r(x)$ 由于$size'(x)=size(x)+size'(z)+1$,根据定理0,加上2r'(x)-r'(z)-r(x)-2。
$\leq 3(r'(x)+r(x))-2$

对于Zig-Zag或Zag-Zig的情况,势能的增量为
$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(y)+r'(z)-2r(x)$,由于size'(x)=size'(y)+size'(z)+1,根据定理0,加上2r'(x)-r'(y)-r'(z)-2
$\leq 2(r'(x)-r(x))-2$

综上,k次旋转操作的势能的增量不超过$3(r'(x)-r(x))-k+1$,由于势能函数在任意一刻不会变负,而一开始整棵树的势能函数和为O(nlogn),所以操作m次的总时间复杂度不超过O(m+nlogn),均摊到每次操作上,每次操作的均摊复杂度是O(logn)的。

LCT时间复杂度证明

虚拟树

我们先要给出虚拟树模型(R.E.Tarjan原文:virtual tree)。我们把原先要操作的树(包括虚实边)称为原树,原树与虚拟树上的结点一一对应,但是边不同。我们重新定义每个结点的父亲:如果这个结点是其所在伸展树的根,那么它的父亲就其在原树中结点的父亲在虚拟树中的对应结点(如果没有它就是根),否则,其父亲就是其所在伸展树中的父亲。简单来说就是hzw大佬的LCT模板中用fa和ch建的树。举个例子:

它的虚拟树可以是这样子的:

势函数

设第i个时刻的LCT为$D_i$,$V_i$为$D_i$所对虚拟树中的点集。定义$s_i(x)$为第i个时刻在虚拟树中以结点x为根的子树中的结点个数,令$r_i(x)=log_2 s_i(x)$。我们在原树上按树链剖分中的定义定义重儿子与轻儿子。定义势函数:$\Phi(D_i)=\displaystyle\sum_{x\in V_i}(r_i(x)+2[此时x的偏爱儿子不是重儿子])$

可以发现,按照这个势能定义,第i个时刻在LCT上执行一次splay操作(不妨设从u旋到v),其摊还代价$\le 3(r_i(v)-r_i(u))+1 $

access操作的时间界

根据这个势能定义,我们可以证明一次access有$O(log_2 n)$的摊还时间界,一般地,对于任意一次splay+更换偏爱儿子的操作(设从u旋到v),我们可以得到当v为重儿子时,其摊还时间复杂度$\le 3(r_i(v)-r_i(u)) $,否则其摊还代价$\le 3(r_i(v)-r_i(u))+4$。
首先考虑$ 3(r_i(v)-r_i(u)) $的部分,一般情况下,我们设虚拟树上v的父亲为w,w所对伸展树根为x,则下一次splay+更换儿子的操作的前面部分摊还时间$\le 3(r_i(x)-r_i(w))$,把这两次的加起来,可以发现加起来的摊还代价$\le 3(r_i(x)-r_i(u))$,按这种方式合并所有splay+更换偏爱儿子摊还代价的前面部分,可以得到这部分摊还代价(设总操作为access(u))$\le 3(r_i(root)-r_i(u))=O(log_2 n)$。
然后我们考虑那个常数4,我们发现当要更换的儿子为轻儿子时,总更换次数不会超过$O(log_2 n)$次,因此,该部分摊还代价也是$O(log_2 n)$。
综上所述,一次access操作摊还代价为$O(log_2 n)$

其它操作的时间界

我们已经把最重要的操作解决了,接下来只需要解决一些零散的操作了。link操作时会改变势能,但易得其势能变化为$O(log_2 n)$,cut操作也是一样,势能变化为$O(1)$。这样我们就可以证明LCT大多数操作时间复杂度均为$O(log_2 n)$了。

1 thought on “证明伸展树与动态树的时间复杂度”

  1. Thanks for all your valuable hard work on this site. Gloria enjoys conducting investigations and it’s obvious why. My spouse and i know all about the powerful tactic you render practical guides via the blog and as well as boost contribution from people on this topic and my child is without question discovering a lot. Take advantage of the remaining portion of the new year. You have been carrying out a stunning job.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注