[关闭]
@Jerusalem 2015-11-09T23:27:20.000000Z 字数 2387 阅读 7284

在这里,我们给出势函数(potential function)的定义,并展示如何通过势函数给出Splay操作的均摊时间复杂度的一个上界,尽管这上界并不是紧的。




势函数Φ定义为数据结构到实数集的一个映射。

在这里,我们假设势函数Φ已经良定义,设T(i)为第i次操作的实际耗时,Φ(i)代表第i次操作结束时系统的势函数值。定义A(i)=T(i)Φ(i1)+Φ(i)

移项,得A(i)+Φ(i1)+Φ(i)=T(i),即

求和,得T(i)=A(i)+Φ(n)Φ(0)

于是,若Φ良定义,我们只需给出A(i)Φ(n)Φ(0)的一个上界,即可给出T(i)的一个上界。




这部分我们显式地给出势函数,定义S(x)代表以x为根的子树,μ(V)=log|V|μ(x)=log|S(x)|,定义势函数Φ=vmu(v)

显然,Φ(n)Φ(0)=O(nlogn),于是我们只需要给出A(i)的一个上界。

以下我们也将μΦ




考虑Zig操作Zig

在这里我们仅仅讨论Zig,所有的推论可以等价地推广到Zag上。我们称x节点Zig后的点为X'。

Zig的T(i)显然是1,而

ΔΦ=Φ(x)+Φ(y)Φ(x)Φ(y)=Φ(y)Φ(x)Φ(x)Φ(x)

于是A(i)=1+ΔΦ1+3[Φ(x)Φ(x)]




接下来我们考虑Zig-Zag与Zig-Zig

Zig-Zag

对于一次Zig-Zag,ΔΦ=Φ(x)+Φ(y)+Φ(z)Φ(x)Φ(y)Φ(z)

于是ΔΦ=Φ(y)+Φ(z)Φ(x)Φ(y)Φ(y)+Φ(z)2Φ(x)

我们又有Φ(z)+Φ(y)2Φ(x)2,这是因为对数函数是凸的。

于是立即推得一次Zig-Zag对应的A有

2+ΔΦ2+(2)[Φ(z)+Φ(y)2Φ(x)]+Φ(y)+Φ(z)2Φ(x)成立。

即一次操作对应的A(i)2Φ(x)2Φ(x)3Φ(x)3Φ(x)成立。


考虑Zig-Zig

Zig-Zig

对于一次Zig-Zig,ΔΦ=Φ(x)+Φ(y)+Φ(z)Φ(x)Φ(y)Φ(z)

于是ΔΦ=Φ(y)+Φ(z)Φ(x)Φ(y)Φ(y)+Φ(z)2Φ(x)依然成立。

类似地,就可推得一次操作对应的A(i)2Φ(x)2Φ(x)3Φ(x)3Φ(x)成立。




我们已经论述了三种操作的上界,同时注意到,每次操作结束后的x'恰是下次操作的x,于是不考虑Zig/Zag的情况下,我们可以对Zig-Zag和Zig-Zig的操作分别求和,即3[Φ(xSonofroot)Φ(xbegin)]

又仅有一次Zig/Zag操作,于是A(i)3[Φ(xroot)Φ(xbegin)]+1=O(logn)

于是显然,m次操作下的A(i)=O(mlogn)

那么T(i)=O(mlogn+nlogn




参考文献:

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注