均摊分析三连
又称“膜拜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
评论 (0)