营员交流均摊分析简介.ppt

前(che)言(dan) 一天正水着 有一位少年提问： 我抱着“QAQ 同求！”的心态等了很久……还是木有人回答 前(che)言(dan) 当今世界 Spaly横行 随机提根的单旋党猖獗 相信很多同学当初学习Splay的过程是这样的： 看了会做法…… w 这很简单嘛！ 复杂度咋证？一看——“留给读者自行证明”、“可以证明是O(log n)”、“Tarjan证明了是……” 算了不管辣！ 不止是Splay，更为基础的并查集，复杂度也不知道咋证明。 前(che)言(dan) 不会复杂度分析，还是可以闷声做大题。 可是…… 作为一名OIER…… 应该反对迷信，崇尚科学。 →_→ 进入正题——均摊分析。 均摊分析 引用黑书上的一个例子进行说明： 均摊分析 “初始值为0的一个k位二进制计数器，只支持加一操作。” 每次确实是O(k)的，但均摊分析可以得到更好的上界。 累计分析 考虑n个操作的总时间T(n) 考虑第i位，每2^i次操作变一次，所以T(n)=n+n/2+n/4+...=O(n)，T(n)/n=O(1) 会计分析 把时间消耗看做金钱的消耗 把一个0变成1时投资2元，其中1元当时就用掉，另1元在1变成0的时候用掉 每次操作投资2元，n次操作投资O(n)，所以均摊时间复杂度O(1) 均摊分析 下面介绍一种更加通用的方法——势能分析。 把“势能”看做整个数据结构的一个状态函数 定义 Φ[i] 表示 i 次操作后整个结构的势能 定义第 i 次操作的均摊时间花费 a[i]=c[i]+Φ[i]-Φ[i-1]（其中 c[i] 表示第 i 次操作的实际消耗时间） 如果我们能设计出恰到好处的势函数，得到 Σa 和 Φ[0]-Φ[n] 上界就得到了T(n)的上界。 均摊分析 以“二进制计数器”为例，我们尝试一下势能分析。 定义势能 Φ=(二进制串中1的个数)。 设第 i 个操作有x个0-1、y个1-0，则此操作均摊复杂度 a[i]=c[i]+ΔΦ=(x+y)+(x-y)=2x=2 。 T(n) = Σa+Φ[0]-Φ[n] ≤ Σa ≤ 2n 所以是O(n) 我们发现，势能分析的关键是设计势函数。 在一个很快的操作时稍微增加一点 在一个耗时的操作时急剧减少 把势函数想象成一种“存储”，在不怎么耗时的时候存下，在非常耗时的时候取出来。 类似于钱，只要“自己掏的钱”和“挪用的存款”不超过某个界，那么花的钱一定不超过那个界。 Splay 先来回顾一下 Splay rotate操作 如果父亲是根，单旋一次 如果父亲和爷爷方向一致，先转父亲后转自己 如果父亲和爷爷方向不同，转两次自己 定义 v 的势能 R(v)=log(size[v])，势函数 Φ=ΣR(v) 。 显然任意时刻 0≤Φ≤n log n，这意味着 Φ[0]-Φ[n] = O(n log n) 。 两个不怎么重要的发现 一棵很平衡的树，不怎么耗时，势函数值较小。 一棵很畸形的树（比如一条链），容易耗时，势函数值较大。 我们来看看，在这种势函数下，三种操作的均摊复杂度分别是什么。 Splay - Zig Splay - ZigZig Splay - ZigZag Splay 综上所述，我们得到了三种情况下的均摊复杂度： 如果父亲是根，单旋一次 ≤ 1+ R(x)-R(x) 如果父亲和爷爷方向一致，先转父亲后转自己 ≤ 3（R(x)-R(x)） 如果父亲和爷爷方向不同，转两次自己 ≤ 2（R(x)-R(x)） 由于每次旋转后 x 的结束位置是下一次旋转开始时 x 的位置 我们把三种全放缩成 ≤ 3（R(x)-R(x)） 那么执行 Splay(v) 的均摊复杂度 a = 1 + 3（R(root)-R(v)） = O(log(n/size[v])) 至此，我们得到了 n 个点、m 次 Splay 操作的时间复杂度为：O(n log n + m log n) LCT 分析完 Splay，再看看 LCT。LCT 可以看作一群 Splay 拼起来的结构。 LCT 的主要操作是 access(v)，因此我们来分析 access 的时间复杂度。 《1》虚实边的切换 《2》Splay 中的复杂度 LCT 《1》虚实边的切换 若v是u的儿子且满足size[v]size[u]/2，称v是u的大儿子，否则为小儿子。对应的父边称大(小)边。 定义整个结构的势能 p=(大虚边的个数)，一次操作的均摊复杂度 a=c+Δp。 当经过一条小边时，c+=1；p可能+=1； # 考虑size的变化，可知路过的小边条数是O(log n)的 当经过一条大边时