• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

使用均摊分析证明Splay复杂度

admin

11月 28, 2021

使用均摊分析证明Splay复杂度

(PS:终于知道了二叉搜索树((binary search tree))为什么叫(BST)。)
平衡树的一种,靠着旋转来保证复杂度。

怎么旋转?这已经说烂了,我比较关心的是(splay)的复杂度怎么证明,和为什么一定要使用双旋操作。

(PS:(Splay)居然是(Tarjan)发明的)
本篇博客证明思路提供于Splay复杂度的证明
但是我看不懂然后借鉴了伸展树(Splay)复杂度证明
但是我看不懂然后借鉴了均摊分析 学习笔记
但是我看不懂然后借鉴了均摊分析简介
吐了
算法导论yyds

######以下证明并不严谨######

均摊分析

(Splay)证明的核心是均摊分析中的势能分析(其他分析方法见均摊分析简介

(c_i)为第i次操作的实际代价。(phi_i)是第(i)次操作之后的势能。

(c_i+phi_i-phi_{i-1})是第(i)次操作的均摊代价。

(n)次操作的均摊代价为(a_i=sum_{i=1}^n(c_i+phi_i-phi_{i-1})=sum_{i=1}^nc_i+phi_n-phi_{0})

如果我们设的势能(phi_i)都是不小于0的数,那么(phi_n-phi_0>=0)。特别地一般令(phi_0=0)

如果我们算出了总均摊代价的上界,我们就可以得出真实代价的上界。

朴实地说:真实代价(<)均摊代价(leq)均摊代价上界。

这样看均摊代价的上界一定是比真实代价的上界好求的,为什么加了势能之后反而好求了呢?带着问题思考。

Splay的均摊分析

(mu_x=log_2(size(x)))其中(size(x))代表x子树的大小。

(phi_x=sum_{i=1}^nmu(i)),任何时候(phi_x)显然是小于(nlogn)的,这个上界十分宽松。

zig(zag)的分摊分析

因为两操作等价,这里只分析zig

显然均摊代价(a(i)=1+mu(x’)+mu(y’)-mu(x)-mu(y))

这里的1并不是真的1,而是代表这一次旋转操作的真实代价,是一个常数。(下面证明中出现的1也是一样的)

(ecause mu(y)=mu(x’) herefore a(i)=1+mu(y’)-mu(x))

(ecause mu(y’)<mu(x’) herefore a(i)<1+mu(x’)-mu(x))

zig-zig(zag-zag)的分摊分析

(a(i)=mu(x’)+mu(y’)+mu(z’)-mu(x)-mu(y)-mu(z)+1)

(ecause mu(z)=mu(x’) herefore a(i)=mu(y’)+mu(z’)-mu(x)-mu(y)+1)

(ecause mu(y’)<mu(x’) , mu(x)<mu(y) herefore a(i)<1+mu(x’)+mu(z’)-2mu(x))

先把式子放在这里,转去证明(mu(x)+mu(z’)-2mu(x’)<-1)

(mu(x)+mu(z’)-2mu(x’)=log(frac{size(x)}{size(x’)})+log(frac{size(z’)}{size(x’)})=log(frac{size(x)size(z’)}{size(x’)^2}))

由上图可知(size(x’)=size(x)+size(z’)+1)(size(x’)>size(x)+size(z’))

( herefore)原式(<log(frac{size(x)size(z’)}{(size(x)+size(z’))^2})<log(frac{size(x)size(z’)}{2size(x)size(z’)})=-1)

( herefore -1+2mu(x’)-mu(x)-mu(z’)>0)

(a(i))加上这个正数显然有(a(i)<1+mu(x’)+mu(z’)-2mu(x)-1+2mu(x’)-mu(x)-mu(z’))

这里注意了:式子中两个1不一样,第一个1是代表这个操作的真实代价是一个常数,第二个1就是实实在在的1,但是把这个1和势能的单位同时增大之后可以把前面的代表常数的1消掉。

(a(i)<3(mu(x’)-mu(x)))

zig-zag(zag-zig)的分摊分析

用跟上面几乎完全一样的方法可以得到:

(a(i)<2(mu(x’)-mu(x)))

因为zig(zag)操作一个splay操作中只会用一遍这样整个一次splay操作地均摊复杂度为:
(1+sum^n (mu(x’_i)-mu(x_i))=1+mu(root)-mu(x))近似为(logn)

所以均摊复杂度为(logn)

这也解释了为什么不能一直单旋,因为那个常数1处理不掉,会使复杂度爆掉。

PS:我感觉这个证明大有问题,但又不知道哪里有问题

发表回复

您的电子邮箱地址不会被公开。