主题

主题

 
   

势能分析与Splay单双旋的思考

  • 扯淡

很久以前想知道Splay的复杂度怎么证明。

今天终于有这个机会学习到了势能分析。于是做一下笔记。


  • 相关概念


这是一个能量守恒定律。

我们把式子累加,发现,


这样就可以计算出均摊复杂度,也就是我们需要的时间复杂度。

我们可以理解为:我们做的操作,一部分是用于调整势能(即势能的变化),另一部分是用于做操作(即c[i])。它们的总时间花费为均摊复杂度。


  • k位2进制计算器

给出一个二进制串,所有运算中数字不会超过k位。支持+1操作。

求这个计算器操作n次的复杂度。

分析:

构造势能函数。


假设一次操作,有x个0变为了1,y个1变为了0。

那么有:

所以可以得到a[i]=x+y+x-y=2x。由于一次只会+1,所以x=1,即a[i]=2。

又因为二进制中1的个数始终在[1,n],所以初始的势能-末状态的势能<=2n。

所以可以得到T(n)=2n+2n=O(n)。

通过这个例子,我们也不难理解为什么vector的使用时均摊O(n)的。


  • Splay双旋复杂度证明

Splay的双旋分为3部分:

  1. 如果x的父亲p为根,单旋x一次

  2. 如果x是父亲p的v儿子(v是0/1,即左/右)且父亲p是爷爷g的v儿子,先单旋p,在单旋x。

  3. 如果x是父亲p的v儿子且父亲p是爷爷g的v^1儿子,单旋两次x。

我们分别对这三个情况进行分析:

对于第一部分:


(图片来自《均摊分析简介》by delayyy)


对于第二部分:


(图片来自《均摊分析简介》by delayyy)


对于第三部分:



(图片来自《均摊分析简介》by delayyy)


于是我们得到了总的分析:

  1. a[i]<=1+R'(x)-R(x)

  2. a[i]<=3(R'(x)-R(x))

  3. a[i]<=2(R'(x)-R(x))

由于第1部分只会操作一次,那么我们可以得到:


即双旋一次Splay的复杂度为O(logn)。


  • Splay单旋的复杂度

我们看到,单旋即为part1部分。那么一次操作的复杂度为O(1+R'(x)-R(x)),所以总操作的复杂度为O(Depth[x]+logn)。

所以很多人认为单旋复杂度没有保证。

然后日益猖獗的单旋党仍然没有被大卡特卡。

在百度贴吧中看到有大佬说:


虽然接下来很多人就这样认为明白了,于是成为了双旋党。但是本蒟认为,人字形树和一条链是一个概念。我们很少见过Splay在使用中会变为一条链。那么自然也不太可能变为人字形树。

相关部分会在接下来的部分讨论。

曾经有十分著名的帖子不过被屏蔽了,找到一个类似的:

http://tieba.baidu.com/p/2324947479


蛤乎也有类似的问题,不过没有很满意的。很多人都是拿具体例子说事,感觉不太科学。

具体例子的话,一条链即可。

本蒟没有找到插入的时候卡单旋的例子,不过查询(即Splay操作)中卡单旋的例子倒是有——我们先插入一个顺序数组,之后我们再不断从最小的数字开始查询。

那么单旋的复杂度就变成了O(n^2)。


  • 本蒟的思考

在插入的过程中,我们消耗了O(Depth[x])的时间,让x旋转到了根。

在势能分析中,我们的常数项同样是O(Depth[x])的。同样效果是把x旋转到了根。

这两个部分应该一致的。如果“Splay插入旋转到根”的复杂度是可观的话,为什么势能分析多出来的这一部分O(Depth[x])是不是也是可观的?

后来被栋爷一句话敲醒:“势能分析这个O(Depth[x])与时间,没有什么关系吧。”

于是这样类比的想法是错误的。


  • 双旋复杂度与单旋复杂度的比较

最大的区别就是双旋保证了只有一次单旋。

那么双旋的常数项只有1,剩余的均可以用势能来表示。最后势能项相互抵消,得到上界。

但是单旋的常数项与深度有关,那么难以用势能分析来保证复杂度。

这就是Splay的双旋的原理所在。

 
 
评论
 
 
热度(1)