均摊分析三连

r_64 posted @ 2017年11月12日 12:50 in 未分类 , 1915 阅读

又称“膜拜Tarjan三连”。

(upd:完结撒花!

实际上是某算法课的一个笔记。不过我猜考试不考

首先介绍一下均摊分析。假设你有一个数据结构,支持一些操作,第$i$个操作耗时$t_i$。你发现$t_i$有大有小,但是它们的和应该不会很大,怎么证明它们的和不大呢?考虑给数据结构一个势能函数$\Phi$,第$i$次操作之后的势能为$\Phi_i$。把每次操作的“均摊代价”定义为$\Delta_i=t_i+\Phi_i-\Phi_{i-1}$,如果你能证明$\Delta_i=O(f(n))$都不大(比如说$f(n)=\log n$),且无论数据结构长什么样,$\Phi=O(g(n))$都不是很大(比如说$g(n)=n\log n$),那么可以得到$m$次操作的复杂度为

$$\sum_{i=1}^mt_i=\sum_{i=1}^m\Delta_i+\Phi_0-\Phi_m=O(g(n)+mf(n))$$


并查集

\(\def\textsc#1{\dosc#1\csod}\def\dosc#1#2\csod{{\rm #1{\small #2}}}\def\Union{\textsc{UNION}}\def\Find{\textsc{FIND}}\def\Link{\textsc{LINK}}\def\rank{\mathrm{rank}}\def\level{\mathrm{level}}\def\iter{\mathrm{iter}}\)
并查集支持两个操作(假设一开始$n$个集合已经造好了):$\Union$和$\Find$。在$\Union(x,y)$操作中,如果$x$和$y$属于同一集合,那么什么都不做;否则将$x,y$所属的两个集合合并。$\Find(x)$操作返回$x$所在集合的代表元。我们用树结构代表集合,$\Find$的返回值就是$x$所在树的树根。这样有一个好处就是我们不需要分析$\Union$了,转而分析一个叫$\Link$的操作:$\Link(x,y)$中,保证$x,y$都是树的根,将$x$和$y$中的某一个的父亲置为另一个。一个$\Union$就变成了两个$\Find$和一个$\Link$。

并查集的实现相信大家都很熟悉(虽然可能没人写启发式合并>_>):每个节点有个父亲$p(x)$还有个权重$\rank(x)$。

  • 在$\Link(x,y)$的时候,假设$\rank(x)\le\rank(y)$(否则交换$x,y$),让$y$成为$x$的父亲,并且如果$\rank(x)=\rank(y)$那么要把$\rank(y)$加$1$。
  • 在$\Find(x)$的时候,直接暴力从$x$往根跳就可以找到根节点。在这之后我们使用路径压缩:经过的所有节点的父亲都改成根。

接下来我们要证明的是:$m$次操作的复杂度为$O(m\alpha(n))$。这个$\alpha(n)$是家喻户晓的反阿克曼函数,让我们看看它的定义:(注:不同版本的证明可能会使用不同版本的$\alpha$,不过它们是同阶的。我参(chao)考(xi)的是CLRS版算导的证明)

阿克曼函数是这样定义的:$A_k(j)=\begin{cases}j+1&k=0\\A_{k-1}^{(j+1)}(j)&k\ge 1\end{cases}$。这里的$f^{(n)}(x)$的意思是把$f$用$n$次,即$\underbrace{f(f(\dots f(n)\dots))}_{n\text{ }f\text{'s}}$。可以看出来这是一个增长极快的函数。

反阿克曼函数:$\alpha(n)=\min\{k:A_k(1)\ge n\}$。

$\rank$函数有一些小性质,我们作为引理列举如下:

  • $\rank(x)<n$。因为每$\Link$一次,$\max\rank$顶多增加$1$。
  • $\rank(p(x))>\rank(x)$。思考一下$\Link$的过程就证明了。
  • 如果$x$不是根,那么$\rank(x)$以后不会变。也是$\Link$过程的直接推论。

现在我们可以来定义我们的势能函数$\Phi$了。我们对每个点$x$定义一个势能函数$\phi(x)$,然后$\Phi$取成所有点势能的和,即$\Phi=\sum_{i=1}^n\phi(x_i)$。在定义$\phi(x)$之前,我们需要两个函数:

  • $\level(x)=\max\{k:\rank(p(x))\ge A_k(\rank(x))\}$
  • $\iter(x)=\max\{i:\rank(p(x))\ge A_{\level(x)}^{(i)}(\rank(x))\}$

势能函数的定义是这样的:

$$\small\phi(x)=\begin{cases}\alpha(n)\cdot\rank(x)&\text{if }x\text{ is a root or }\rank(x)=0\\(\alpha(n)-\level(x))\cdot\rank(x)-\iter(x)&\text{otherwise}\end{cases}$$

我们可以看到$\level$和$\iter$的一些性质:

  • $0\le\level(x)<\alpha(n)$。这个很显然。那个小于号是因为$\rank$到不了$n$。
  • $1\le\iter(x)\le \rank(x)$。因为$$A_{\level(x)}^{(\rank(x)+1)}(\rank(x))=A_{\level(x)+1}(\rank(x))>\rank(p(x))$$
  • 如果$x$是某个树根或者$\rank(x)=0$,那么$\phi(x)=\alpha(n)\cdot\rank(x)$,否则$\phi(x)<\alpha(n)\cdot\rank(x)$。根据上面两条性质,这个不难推出来。
  • 考虑一个有父亲的$x$,$\rank(x)$不会再改变了,但是$\rank(p(x))$会改变(显然只能增大)。那么这种$x$的势能怎么变呢?容易发现,$\iter(x)$会慢慢变大,直到它变成$\rank(x)+1$的那一刻,它会被打回$1$,然后$\level(x)$增大。这样的话,我们可以把$(\level(x),\iter(x))$看成$\rank(x)$进制的两位数(这句话不严谨因为$\level(x)$可能大于$\rank(x)$),当$\rank(p(x))$增大的时候,$\level(x)$和$\iter(x)$会xjb变动,但是变动的趋势是这个两位数变大。这样看还能得到一个intuition:$\phi(x)$就是$\alpha(n)\cdot\rank(x)$减去这个两位数,所以$x$有父亲之后它的$\phi$值是不会增大的。

现在万事俱备,可以开始分析啦!

对于$\Link$操作,分析很简单:$x$的势能不会增加,$y$的势能顶多增加$\alpha(n)$,其他势能不会增加,实际耗时$t_i=O(1)$,故均摊代价是$O(\alpha(n))$。

对于$\Find$操作,设$x=x_0\to x_1\to\dots\to x_h=r$是从$x$到根$r$的序列(当然,这些点之后父亲都会变成$r$),那么实际耗时$t_i=r$。然而,除了$O(\alpha(n))$个点以外,所有的$\phi(x_i)$都会减少至少$1$,所以均摊代价仍然是$O(\alpha(n))$——接下来我们就要证明这个结论。不妨考虑两个点$x_i,x_j$,其中$i<j$且$\level(i)=\level(j)=k$。(注意:这里的$\level$、$\iter$、$\rank$都指路径压缩之前的值。)我们发现$\phi(x_i)$至少会减$1$。要证明这个,我们只需要证明

$$A_k^{(\iter(x_i)+1)}(\rank(x_i))\le\rank(r)$$

然而由于$x_j$的存在性,这个也很好证:

\[\begin{align*}
\rank(r)\ge&A_k(x_j)\\
\ge&A_k(A_k^{(\iter(x_i))}(\rank(x_i))\\
=&A_k^{(\iter(x_i)+1)}(\rank(x_i))
\end{align*}\]

对于哪些$x_i$,存在相应的$x_j$呢?如果$x_i$不是$\level(x_i)=k$的最后一个(离$x$最远)$i$,那么显然存在相应的$x_j$。这样,除了$x$(可能是$\rank=0$的叶子节点)和所有“离$x$最远的$\level(x_i)=k$的节点”$(k=1,2,\dots,\alpha(n))$以外,其他点的势能至少会减$1$。这也就证明了$\Link$的均摊代价是$O(\alpha(n))$的。

证毕。关于并查集其实还有若干个坑,如果我有时间的话可能会去学学:

  • $\alpha(n)$是紧的,也就是并查集做不了更好的复杂度了。见这篇
  • 在$\Link$的时候不记录$\rank$,而是随机选一个节点接在另一个节点上。这个期望复杂度仍是$O(\alpha(n))$。见这篇

Splay

$\def\Splay{\textsc{SPLAY}}$简单起见,这里的Splay只支持一个操作,就是$\Splay$。要加入$\textsc{INSERT}$之类的操作也很简单,对着Splay的势能函数去论证就好,像$\textsc{INSERT}$这样的操作一般都很好证(其实我没试过

一棵Splay树是一个$n$个点的二叉树,支持一种叫$\Splay$的操作。$\Splay(x)$即在不改变中序遍历的情况下让$x$转到根。当然这个$\Splay$操作有多种实现方法,我们只会讲能证复杂度的那个(还有一些Spaly之类的异端)。这个$\Splay$的实现细节是:首先找到$x$,然后每次根据$x$、其父亲、其祖父的位置关系,执行如下三种操作,直到$x$转到根。

  • zig:$x$的父亲是根(没有祖父),直接转:
        y        x
       / \      / \
      x   C => A   y
     / \          / \
    A   B        B   C
  • zig-zig:$x$与$x$的父亲类型相同。(这里我们定义一个点的类型表示它是它父亲的左儿子还是右儿子。)那么先转$x$的父亲,再转$x$:
          z        x
         / \      / \
        y   D    A   y
       / \    =>    / \
      x   C        B   z
     / \              / \
    A   B            C   D
  • zig-zag:$x$与$x$的父亲类型不同。直接转两次$x$:
          z
         / \        x
        y   D      / \
       / \    =>  y   z
      A   x      / \ / \
         / \     A B C D
        B   C

对于这个数据结构,我们的势能函数是这样定义的:对一个点$x$,记$S(x)$为$x$的子树内点的个数,定义$\phi(x)=\lfloor\log_2 S(x)\rfloor$,$\Phi=\sum_{i=1}^n\phi(x_i)$。

我们用如下引理来描述Splay的复杂度:一次Splay操作将$x$往上提若干步,设老的势能函数为$\mu$,新的为$\mu'$,则均摊代价不超过$3(\mu'(x)-\mu(x))+1$。因为$\mu(x)=O(\log n)$,所以一次操作的均摊代价是$O(\log n)$的。

为了证明这个引理,我们只需要分析每次往上转(即zig、zig-zig、zig-zag)的均摊代价。

  • zig:
        y        x
       / \      / \
      x   C => A   y
     / \          / \
    A   B        B   C
    均摊代价为$\mu'(y)-\mu(x)+1\le\mu'(x)-\mu(x)+1$;
  • zig-zig:
          z        x
         / \      / \
        y   D    A   y
       / \    =>    / \
      x   C        B   z
     / \              / \
    A   B            C   D
    均摊代价为$\Delta=\mu'(y)+\mu'(z)-\mu(x)-\mu(y)+1$。注意,在这里的分析中,我们不能将其放缩为$2(\mu'(x)-\mu(x))+1$,因为那个$+1$非常烦人——高度为$h$的话,一次Splay中就可以有$h$个$+1$,复杂度就崩了。我们需要利用$\log_2$函数的性质把$+1$给去掉。
    我们知道$\Delta\le 2(\mu'(x)-\mu(x))+1$,所以$\mu'(x)>\mu(x)$的时候这个$+1$是可以去掉的,即$\Delta\le 3(\mu'(x)-\mu(x))$。如果$\mu'(x)=\mu(x)$,那么有趣的事来了:令$X=S(A)+S(B)+1$,$Y=S(C)+S(D)+1$,则$\mu'(x)=\lfloor\log_2X\rfloor$,$\mu(x)=\lfloor\log_2(X+Y+1)\rfloor$,根据$\mu'(x)=\mu(x)$我们有$2Y<X+Y+1$,故$\mu'(z)<\mu(x)$,即$\Delta<2(\mu'(x)-\mu(x))+1$,也可以放缩成$\Delta\le 3(\mu'(x)-\mu(x))$。
  • zig-zag:
          z
         / \        x
        y   D      / \
       / \    =>  y   z
      A   x      / \ / \
         / \     A B C D
        B   C
    照上面的方法继续分析。代价$\Delta=\mu'(y)+\mu'(z)-\mu(x)-\mu(y)+1\le 2(\mu'(x)-\mu(x))+1$。如果$\mu'(x)\ne \mu(x)$则照样放缩;否则显然有$\mu'(y)+\mu'(z)<2\mu'(x)$,故那个$+1$照样是可以消掉的。

综上,一次Splay操作的均摊代价为$3(\mu'(x)-\mu(x))+1=O(\log n)$。

Fibonacci Heap

这个东西。。可能大部分oier都不知道实现细节?那就得讲讲了。。

$\def\Insert{\textsc{INSERT}}\def\Deletemin{\textsc{DELETE}\text{-}{\small\text{MIN}}}\def\Decreasekey{\textsc{DECREASE}\text{-}{\small\text{KEY}}}\def\Delete{\textsc{DELETE}}\def\Findmin{\textsc{FIND}\text{-}{\small\text{MIN}}}\def\trees{\text{trees}}\def\marks{\text{marks}}$首先作为一个堆,Fib-Heap支持如下的操作:

  • $\Insert$:往堆中插入一个元素,均摊$O(1)$
  • $\Deletemin$:删掉最小的元素,均摊$O(\log n)$
  • $\Decreasekey$:将堆中的某个元素变小,均摊$O(1)$
  • $\Delete$:删掉某个元素,这里不管它因为就是先$\Decreasekey$再$\Deletemin$;
  • $\Union$:合并两个堆,均摊$O(1)$
  • $\Findmin$:求堆中最小值,均摊$O(1)$

Fib-Heap的数据结构是这样的:堆中的元素组成若干棵树,每棵树都满足堆性质(父亲比儿子小);有一个双向链表将所有树根串起来;记录一个指针指向最小元素(显然是某个树根);一些点被mark了(染成了黑色;一般的点是白色的)。这个结构直接解释了$\Findmin$的复杂度为什么是$O(1)$的。(注:$\Findmin$不改变堆结构,所以$\Delta=1$)

定义:

  • $n$代表点数;
  • $\rank(x)$代表点$x$儿子数;
  • $\rank(H)$代表堆$H$中最大的$\rank$;
  • $\trees(H)$代表堆中树的个数(链表的大小);
  • $\marks(H)$代表堆中黑点的个数;
  • 势能函数$\Phi(H)=\trees(H)+2\cdot\marks(H)$。

现在考虑堆操作。

$\Insert$

直接新建一棵单点的树就好。可能要更新一下链表和最小值。显然$\Delta=O(1)$。

$\Deletemin$

这个$\min$肯定是某个树的根,我们把它删掉然后把它的子树分散到链表中。接着,我们把相同$\rank$的树根进行合并,直到没有$\rank$相同的树为止。

例:

  min pointer                              min pointer
        |                                        |
        v                                        v
13------6------9----7   => 13------8--14--12--9--7
|      /| \        / \     |      /|      |     / \
17    8 14 12     16 18    17   11 15     13   16 18
     /|    |
   11 15   13

                min pointer          min pointer
                      |                    |
                      v                    v
13------8--14--12--9--7   => 12------9-----7
|      /|      |     / \     | \     |    /| \
17   11 15     13   16 18    13 13   14 16 18 8
                                |            /|
                                17         11 15

复杂度分析:首先,实际耗时是可以做到$O(\trees(H))$的,用一些桶之类的数据结构。其次我们发现势能函数的$\marks$一项不变,而$\trees$一项减小到了$\rank(H)$。故$\Delta=O(\rank(H))$。

$\Decreasekey$

首先我们把$x$的key减小,如果不违反堆性质,那么就做完了,均摊代价$\Delta=O(1)$。否则我们把$x$切开形成单独的一棵树并放到双向链表中,更新最小值:(下例为$\Decreasekey(8\to 3)$)

  min pointer               min pointer
        |                         |
        v                         v
13------6------9----7   => 13-----3---6------9----7
|      /| \        / \     |     /|   | \        / \
17    8 14 12     16 18    17  11 15  14 12     16 18
     /|    |                             |
   11 15   13                            13

然而这还没完:我们需要把$x$的父亲标记一下,说明它已经失去了一个儿子。这又分两种情况:

1)$x$的父亲是白的,我们把它染黑就好;

2)否则,将$x$的父亲染白、割掉。此时$x$的祖父已经失去了一个儿子,我们需要将其染黑;如果$x$的祖父本身是黑的,我们又要将它割掉,然后重复上面的操作……直到$x$的某个祖先从白色染成黑色,或者我们走到根为止。走到根的时候就不用把根染黑了。下面是一个例子,其中7和8是黑的,我们$\Decreasekey(11\to 5)$,最终只有7是黑的(如果6不是根的话6也会是黑的)。

  min pointer            min pointer
        |                      |
        v                      v
13------6------9----7   => 13--5---8--6----9----7
|      /| \        / \     |       |  | \      / \
17    8 14 12     16 18    17      15 14 12   16 18
     /|    |                             |
   11 15   13                            13

(注:某个根有可能是黑的。可能是$\Deletemin$的遗留物。)

来分析均摊代价:将$x$切开后$\trees$加一;然后我们开始割$x$的祖先,设割了$k$个祖先,那么$\marks\gets\marks-k$,$\trees\gets\trees+k$,且我们用了$O(k)$的时间。算一下就会发现$\Delta=O(1)$。

$\Union$

直接把两个双向链表并起来,实际复杂度$O(1)$,$\Delta=0$。

$\rank(H)$的界

好像就讲完了?如果说还剩下什么的话,那就是$\rank(H)=O(\log n)$还没证了吧。事实上,考虑一个点$x$,设$k=\rank(x)$且$x$的$k$个儿子为$c_1,c_2,\dots,c_k$的话,则$\rank(c_i)\ge i-2$。这里的$c_i$是按照成为$x$的儿子的时间排的序,即$x$一开始没有儿子,后来$c_1$成了$x$的儿子,再后来是$c_2$,再后来是$c_3$,……

这个很好证:只有$\rank$相同的点才会合并,而$c_i$与$x$合并的时候$x$已经有$i-1$个儿子了,故$\rank(c_i)\ge i-1$。之后的时间中,$c_i$可能会被切掉一个儿子,但一定不会被切掉两个(否则$c_i$自己也会被切掉)。这样就有$\rank(c_i)\ge i-2$。

令$F_i$表示$\rank$为$i$的点子树至少有多少个点,则$F_i=F_{i-2}+F_{i-3}+\dots+F_0+1$。这样,我们有$F_i$是第$i$个Fibonacci数,故$\rank(H)=O(\log n)$。

这下是真讲完了。Fibonacci堆的名字也就是这么来的。

Extra: Minimum Spanning Tree

这个东西其实与均摊分析无关。。但是由于用到了Fibonacci Heap我就写一下(其实是课上讲了,复习一遍(其实是我炒鸡喜欢这个算法的!>_<

具体嘛,就是在Fibonacci Heap的那篇论文中提出的一个mst算法,复杂度$O(m\beta(m,n))$,其中$\beta(m,n)=\min\{i:\log^{(i)}n\le m/n\}$。对稍微稠密一点的图(如$m=O(n\log^{(3)}n)$)这个算法就是$O(m)$的;对$m=O(n)$的图,这个算法是$O(n\log^* n)$的。

这个算法其实是一个思路很暴力的算法,但是它结合了Prim和Boruvka两个经典算法,做到了更好的复杂度。

Prim大家都很熟悉:有一个集合$S$,对$x\not\in S$令$d(x)=\min\{w(y\to x):y\in S\}$,每次拿$d(x)$最小的点放入$S$。这个算法用Fibonacci Heap显然能优化到$O(m+n\log n)$。

Boruvka(应该)是最早的MST算法,它的复杂度是$O(m\log n)$。让每个点选择其邻边中权值最小的,这些边一定都在最小生成树中。我们根据这些边缩点,得到一个$O(m)$条边、$\le\frac{n}{2}$个点的新图,递归。

这个算法的思路:用Prim做Boruvka!我们的算法是一轮一轮的,每一轮复杂度都是$O(m)$。第$i$轮的时候我们有一个$n_0$个点的图,我们希望像Boruvka一样把$n_0$变小,而且每一次不是除以$2$而是除以更大的数。具体的一轮是这样的:令$k=2^{2m/n_0}$,我们每次找一个本轮中还没有遍历过的点$v$,以它为起点跑Prim。当堆的大小超过了$k$或者$S$中有之前遍历过的点时,Prim结束。这样我们一轮能够找出一些边,保证它们都在最小生成树中,我们就把这些边缩起来。注意在缩完点之后,每一个大点至少会包含$k$个小点,这样新的图的点数是$n_0/k$。点数的正确估计是$2m/k$,因为$k$只是堆的大小(访问过的点的个数)而不是已经取出的点的个数。这个$2m/k$是因为与一个块相连的边数只有$2k$,而$m$条边每条只会算两次。说起来我好像因为这里挂科了

这个算法每轮显然是$O(m)$的:Prim用$O(k\log k)=O(km/n_0)$的时间遍历$k$个点,那么遍历$n_0$个点当然只用$O(m)$的时间。那么它有多少轮呢?考虑新图中的$m'/n'$和原来图中的$m/n_0$,我们有:

$$m'/n'=\frac{m}{2m/2^{2m/n_0}}=\frac{1}{2}2^{2m/n_0}$$

这样,$m/n_0$这个量是$x\mapsto 2^x$疯狂增长的,且它不会超过$m/n$。这就证明了该算法的复杂度是$O(m\beta(m,n))$。

列举一些其他的MST算法,这个坑不准备填了:

  • 线性的随机MST算法,这里
  • 确定性的$O(m\alpha(m,n))$MST算法,这里
  • 最优的确定性MST算法。复杂度等于MST的决策树深度,但是这个深度还没人证出是线性的,故这个算法的复杂度还是open的。这里

最后祝您。。。身体健康。。。(我要挂科了QAQ

接下来

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter