这里是Coursera上Algrithm Part 1的笔记
并查集(Union-Find)
并查集是一种数据结构，可以用来描述多个实体之间的连接关系，至少在这个课程中，它是一个为了解决特定的问题而简化过的模型。
一开始是一堆互不连接的点，我们使用union操作可以将它们两两连接起来，但是在我们使用的数据结构中，我们无法判断是哪两个具体的点连在了一起，也不能使用断开连接的操作。我们只需要知道，这几个点是连在一起的，这种关系叫做connected。
也就是说在并查集中有两种操作，一种是connected,一种是union，connected只是一个判断两个节点是否连通的操作，union则是把两个点连接起来(如果它们已经连通了，就跳过)。我们需要解决的问题就是判断某些点是否互相连通。
此外还有一个在connected和union中的辅助操作find，用来获取某个实体对应的集合的id。
这里的连通关系(connected)有三个性质(非常常见的性质)：
- (自反)自己和自己是连通的
- (对称)如果p和q连通，那么q和p连通(if p is connected to q, q is connected to p)
- (传递)a和b连通，b和c连通，那么a和c连通。
此时我们需要来个图：
（对不起 好像不应该是这个图）
不过既然都放错了…
这个图是用在一类叫渗漏问题的问题上(percolation)。我们假设有$50*50$的方块，黑色的是不能通过的方块，白色的是可以通过的方块，那么如果我们在最上面浇层水，它能流到最下面一层我们就说它渗漏了。
然后我们想寻找一个比例$p$，当我们一个一个将黑色的方块打通时，大概到多少的比例时整个方块可以渗漏。
我们可以使用蒙特卡洛方法来寻找这个比例。就是不停地尝试最后得到一个稳定的结果。
并查集也可能会用在我们实现最小生成树的时候，如果我们使用Kruskal算法可能会需要它。
渗漏问题
上面的图是随机的，它可能可以让水渗到底，也可能不行，我们可以点一下下面的按钮倒一杯水试试，它应该能在$N+M\lg{*}N$的时间内把水倒进去。
如果感觉这几个按钮位置不太对也可以点挪上去。
上面的例子只是简单地判断一下上下是否连通，并没有帮我们去找出连通的阈值。也许我们应该把它找出来。
并查集的简单描述
我么可以实现一个在$O(\lg{*}N)$时间内完成connected或者union操作的并查集（当然还有find），这样我们可以在很多已经连接的实体中，快速地判断两个实体直接是否连通，或者将两个不同的连通集合连接在一起。我更喜欢这样子来描述union的作用。它不只是连接了两个实体，也让与他们连通的所有实体之间变得互相连通，就像合并了它们所在的两个集合一样。
因为在我们需要用并查集解决的问题中，是不需要让并查集知道具体哪两个实体之间有一条连线，也不需要断开它们之间的连接的。我们可以因为不用解决这些问题获得一些好处，就是可以快速地解决我们需要解决的问题。
我们也可以舍弃union操作的速度来提升connected操作的速度。
实现
quick-find
首先我们可以来一个简单的想法，我们使用一个id数组来表示每一个实体对应的集合的id。
假设有$10$个实体，我们使用$0-9$来表示他们，那么初始化时id数组中的数值和它们自身也是一样的，因为还没有进行过union操作。如下：
1 | id = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
在这里我们进行union(a, b)操作时，只需要把所有和id[b]相同的id，替换为id[a]就可以了。
我们进行union(1, 2), union(1, 4), union(5, 6)之后id数组会变成这样：
1 | id = [0, 1, 1, 3, 1, 5, 5, 7, 8, 9] |
那么find(a)操作就是返回对应的id[a]，而connected(a, b)操作就是判断find(a)==find(b)。它们只需要常数时间就可以完成。
当然如果我们这么干，就需要使用$O(N)$时间来解决union操作。
quick-union
咕咕咕
关于算法的复杂度
有几种需要区分开来的表示算法时间复杂度的标记方法。
第一个是~(tilde notation)，用来标记一个比较具体的近似的复杂度。
比如当一个算法的时间复杂度为$\frac{1}{6}N^3+2N^2+\log{N}时$，我们可以把它的时间复杂度标记为~$\frac{1}{6}N^3$,我们的理由如下：
$$
\lim_{x\to \infty}\frac{\frac{1}{6}N^3+2N^2+\log{N}}{\frac{1}{6}N^3}=1
$$
~(tilde notation)就是通过这种方式来表示一个算法的时间复杂度，当然它的具体的复杂度需要别的方法自行判断。
还有常见的方式是使用$O$, $\Theta$, $\Omega$来表示，这几种方式和~都是有差别的，其中：
- $O$表示的是上界，比如一个算法的复杂度小于$N^3$时我们都可以使用$O(N^3)$来表示
- $\Omega$则是下界，和大$O$相反。
- $\Theta$则只能表示确切的增长速度，很多时候我们应该用$\Theta(N^3)$来表示一个算法的时间复杂度增长类别是$N^3$
$O$, $\Theta$和$\Omega$是表示根据输入的大小的增长速度来分类的，我们可以在括号里填$1$, $N$, $\log{N}$, $N\log{N}$, $N^2$, $2^N$等…表示不同的增长速度，而~则是一个具体的表示。也就是在这一种分类表示方法的前面加上一个系数。
分析算法复杂度的方法
我们介绍一个常见有效的方法，有以下五个步骤
- Observe 就是，观察一个问题
- Hypothesize 然后我们假设一下
- Predict 用这个假设来预测
- Verify 验证我们的预测
- Validates 重复上述步骤直到假设和观测一致