Contents

1. 1. 算法介绍
2. 2. 复杂度分析
   1. 2.1. 性质与引理
   2. 2.2. Hopcroft-Ullman Theorem
   3. 2.3. Tarjan’s Analysis
3. 3. 八卦环节

算法介绍

在普林斯顿算法课的第一课中，老师就讲解了这个经典的Union Find数据结构。它主要是用来解决动态连同性问题。在课上举的例子就是做聚类，初始化时每个点都是一个cluster，然后从距离最近的开始做union，同时减少cluster的数量，一直到聚类为所需要的cluster数目为止。在这个过程中有两个典型操作，一是判断目前选取的距离最近的两个点是否已经在同一个cluster中，另外一个是将两个不在同个cluster中的点union起来。我们就要根据这两个操作来设计数据结构及相应算法。

最直观的做法就是Quick Find。用一个数组存每个点（index）所在的组，一开始就初始化为本身即可。在做find时，只要看数组中对应index存的组id即可，时间复杂度为O(1)。而union时则要将其中一个组的所有id都改为另一个组当前的id，所以复杂度达到了O(N)，效率不太行。

Union Find则改进了Union过程，在union时不把所有组成员的id都改了，而只改“带头大哥”的id，形成一个类似树的结构。这样的话每次union时先要调用两次find找到两方的根，然后修改其中一方到另一方名下即可。如果每次只是随便定一方为新老大，这个树很可能变成又瘦又长，变成个链表，又是O(N)的复杂度。这里有个很自然的优化就是把size/height比较小的树并到大树底下去，让这棵树不至于太瘦长。另外在find过程中还可以做path compression，就是将find过程中一层层找上去的中间节点在最后都一起设成根节点的id！这样以后做find就是一步的事情了！整体的Python代码实现如下：

class UF(object):
    def __init__(self, size):
        self.parent = []
        self.rank = []
        self.count = size
        for i in range(0, size):
            self.parent.append(i)
            self.rank.append(0)
 
    def find(self, i):
        # with path compression
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
 
        # another impl
        # root = i
        # while root != self.parent[root]:
        #     self.parent[root] = self.parent[self.parent[root]]
        #     root = self.parent[root]
        # return root
 
    def connected(self, i, j):
        return self.find(i) == self.find(j)
 
    def union(self, i, j):
        p = self.find(i)
        q = self.find(j)
        if p == q: return
        if self.rank[p] < self.rank[q]:
            self.parent[p] = q
        elif self.rank[p] > self.rank[q]:
            self.parent[q] = p
        else:
            self.parent[q] = p
            self.rank[p] += 1
        self.count -= 1

复杂度分析

性质与引理

这里用的是rank，类似于height但在union过程中并不严格是树的height。初始化时我们把它设为0，可以暂时理解为从leaf跳到当前节点的hop数。后面算法分析中有关于这个rank的一些性质。

这个数据结构非常简单，算法过程本身也很容易懂，不过整个算法的复杂度分析可是相当碉堡……我们先来看一些直观的性质！

1. 任何节点的rank值在整个算法过程中只会增加，不会减少。这个应该一眼就能看穿吧！
2. 在整个算法过程中只有root节点的rank值会增加。这个也可以在代码中发现。另外一个节点如果不是root了，以后就永远不会再变成root。
3. 在find的整个路径上，节点的rank值只会单调增加。也是显而易见的。

接下来是rank lemma，需要证明一下，课上老师分了两个Claim：

1. 如果x, y两个节点具有相同的rank，那么它们的subtree必须是无重合的。
2. 一个rank为r的节点的subtree大小要 >= 2^r。

Claim 1可以用反证法，如果有重合，那么有个node z既可以到达x，又可以到达y。由于路径是单一的，所以x和y在路径上必须有先后，根据前面第3点的性质，有先后rank大小就必然不一致，所以得证。
Claim 2从base case看，如果rank为0，那么subtree size为1，很显然成立。在后续操作中又分两种情况： a) 在union时两方的rank都没变化，因为union之后subtree size只会更大，所以也是满足下界的。b) 如果有一方rank变大了，那么表示之前两方rank值相等，所以两方之前的size都至少为2^r，rank+1的那一方的size自然至少是这个值乘以2，也就是 >= 2^r+1啦！QED

Hopcroft-Ullman Theorem

证完这个只是开始……首先来看下最后复杂度计算中要用到的log*函数。这个函数的计算方法就是对一个数做以2为底的log运算直到结果<=1时总共做的运算的次数。这个函数增长极其缓慢，比如2²⁶⁵，据说是宇宙中所有粒子数之和？第一次log完265 -> 第二次 8 -> 第三次 3 -> 第四次 1多点 所以最后结果就是5了。

接下来根据这个运算来建立block，老师用的block分区为{0}, {1}, {2,3,4}, {5,…,2⁴}, {17,…,2¹⁶}…… 每个block中最大的数做log运算后正好是前一个block中最大的数，因此一共有O(log* n)个不同的block。之所以要设置这些block是为了记录我们在find过程中每一跳所能取得的rank进展。这里还有要注意的一点是我们同时用了path compression，由于path compression会将路径上所有的点直接指向root，所以在这个compression过程中parent的rank值是只会增加不会变小的！

接下来我们再来定义一下good node和bad node。好的节点呢有两个条件：

1. x或者x的parent就是root
2. rank[parent(x)]在比rank(x)更大的block中

只要满足其一即可。而不满足这两个条件的就是邪恶节点了。这里老师没有分析一开始的邪恶节点是如何出现的，我自己思索了下发现root节点在union时碰到一个rank相同的另一个root时会出现一方的rank+1，而没有+1的那一方的child可能因此变成了bad node。

考虑我们在m次find操作中，在整个path上碰到good node数最多为O(mlog* n)，如果是bad node，由于我们有path compression，而且根据parent rank只会增加以及非root节点的rank值再也不会变化这两个特性，我们可知任何节点一旦“从良”就永远是“良民”了！那么在成为良民前我们会在路径上access bad node几次呢？考虑在block k中的bad node，那么最多不超过2^k次（这里忽略了k这个比较小的数）。根据rank lemma，rank为r的节点的subtree size最小为2^r，所以rank为r的节点数最多为n/2^r。然后我们再计算block k中各rank的node数量之和，sum(n/2ⁱ) (k+1 <= i <= 2^k)这个值 <= n/2^k。这个值与之前access的次数乘一下，就得到了n。每个block都是n，总共log* n个block，最后的结果是O(nlog* n)，加起来的结果是O((m+n)log* n)。这个证明称为Hopcroft-Ullman Theorem。

Tarjan’s Analysis

上面这个分析过程已经让人看得有些迷茫了，不过还有更猛的……这里又引入了一个新函数，Ackermann Function：

设定个base case A₀(r) = r + 1，后面每递归一层，就是对前一层函数调用r次，比如A₁(r) = A₀(A₀(A₀(…A₀(r)…)))一共调用r次A₀，那就是r + r * 1也就是2r了！这样看起来也还好嘛……A₂(r)同理，就是r * 2^r，接下来A₃(r)就有点可怕了……光2^r那部分就会形成一个2的乘方的塔……这位老师说光想一想A₄(r)就开始头痛了，我们也到此为止吧。

这个Ackermann函数增长如此之快，真容易让人联想到魔兽里的大boss之一阿克蒙德啊……但是再Tarjan的分析中用的是它的反函数（r设为2），所以就成了一个增长比log*还慢的函数。基本上我们用到的数apply这个函数后都不会超过4。课上老师还比较了下这两个函数，虽然log*也很猛，但是见到阿克蒙德，真的就只能呵呵了……

Tarjan analysis过程与之前的Hopcroft-Ullman很像，之前是定义block，这里是用delta函数δ(x) = max k that rank[parent(x)] >= A_k(rank[x])，因为parent rank至少比x大，A₀(r) = r + 1，所以δ(x) >= 0。以此类推，当parent rank是x的两倍或更大时，δ(x) >= 1，当parent rank >= rank[x] * 2^rank[x] 时 δ(x) >= 2……

接下来在设定bad node条件时把跟parent在同一个block变成了跟它所有ancestors中的某个拥有node相同的delta值。还有个不太重要的附加条件，rank[x] >= 2。这样在每次path compression时，这个bad node x的parent被提升到的rank至少是A_k(rank[x])，这点是跟之前分析的主要不同之处！因为它改变了block的条件，所以access bad nodes时的情景也不一样了，其提升的gap也大大加强了！（我理解为加强了gap条件，再去分析access次数看是不是还能bound到一个数量以此来进一步降低这个总体复杂度的边界）在access r次之后，A_k(A_k(A_k(…(rank[x])…)))就成了下一层的A_k+1了，它终究成了一个forever good node，所以这里的access次数就成了 α(n)（A_k的反函数）。后面的分析就基本一致了！bad nodes的求和为α(n) * sum(r * n / 2^r) (r >= 0) = C * n * α(n)。而good node的access次数计算与之前也基本一致，总体次数为：1 root + 1 child of root + 1 object with rank 1 + (1 object with δ(x) = k for each k in (0, 1, 2, …, α(n))) = O(α(n))。最后又是O((m + n) * α(n))，由于α(n)增长比log*更慢，所以基本非常接近线性复杂度了。

八卦环节

这个老师自己也说这个Tarjan算法分析算是这个领域中的一颗明珠……的确各种匪夷所思，但冥冥中好像就是要定义一个这样的阿克蒙德函数的感觉啊！（至少我的直觉时path compression时每次rank应该不止加1）Tarjan本人也觉得这个东西挺复杂的。既然这么接近线性复杂度，那到底是不是可以做到线性呢？后来到了89年终于有人证明了union-find是没有linear time的算法的！

Tarjan的原论文在此。证明无线性时间算法的论文是89年Fredman和Saks的’The Cell Probe Complexity of Dynamic Data Structures’。

另外这门课也介绍过Tarjan合作写的另一个算法就是找一个无序list中第i大的element。神奇的是这篇牛逼闪闪的论文的五个合作者中有四个得过图灵奖……这就是传说中的全明星阵容吧…………