type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jan 27, 2025 01:09 PM
课堂总结
课堂主要讲了QuickFind，quickUnion，WeightedQuickUnion和使用路径压缩的WeightedQuickUnion四种方法。
QuickFind就是一种blute force的解法。就是维护一个id数组，union操作
把所有连通分量的之改成同一个。
实现：
而QuickUnion的思想就是用了树的结构，根节点是一个就是同一个连通分量，这种union的时候比较方便，只要把一棵树的root的root指向另一棵树的root即可。
WeightedQuickUnion是对QuickUnion的优化，相当于始终把size更小的树或者height更低的树合并到更大更高的树，这样可以有效控制树的深度，从而减少connected check操作的时长，因为可以更快地找到根节点。树的深度最多logN，证明如下：
这里的证明的意思当T2合并到T1树的时候，T2数的大小肯定大于等于T1数的大小，
每合并一次，树的高度增加一，但是每次size会double，size总会用完，所以size最多double logN次，因此树的深度最大logN。
weighedUnionFind可以by size也可以by height，这里给出by height 的代码实现。
下为以上三种算法的复杂度分析：
而使用路径压缩（Path compression）的weightedQuickUnion则是进一步优化，你想，为啥要好几层，不直接一层指向了事？我在查找过程中，把访问路径中指向的点直接移到根节点就行。
实现方法很简单，只要修改root方法，加一行代码即可：
复杂度分析：
下面给出一个思路，来说明为什么带路径压缩（并使用按大小/按秩合并）的Union‐Find，其单次操作的摊还复杂度可以被限制在一个极缓慢增长的函数（ 或 之内。)
- （iterated log）定义为：对 反复取对数，直到结果不大于 1，需要几次迭代，就记为
- 如果N = 16，那么，再对 4 取对数是 2，再对 2 取对数是 1，总共 3 次迭代到 ，所以 。
- （inverse Ackermann function）则是另外一个更“缓慢增长”的函数；形式上它比 还要再小一些，在普通规模上一般不超过 4、5。
带路径压缩的Weighted Quick Union算法复杂度分析
因为不了解阿克曼函数，我这里只对单次find操作复杂度为进行简单的证明。用的方法是节点分层法。
用维基百科上的证明方法：
Lemma
引理 1：在执行 Find 的过程中，我们沿着从某节点到其根节点的路径访问到的各个节点，其秩是单调递增的。
证明思路
- 在算法初始化时，每个节点自成一棵树，且每个节点的秩都为 0，此时结论 trivially 成立。
- 只有在执行按秩合并（Union by Rank）时，可能会改变节点的秩。但按秩合并会将秩较小的树挂到秩较大的树下面。这样一来，被挂载到别的根上的那棵子树的根的秩一定小于或等于新的根的秩，不会破坏“沿路径秩递增”的性质。
- 在执行 Find(u) 时，路径压缩会将访问路径上的所有节点直接挂到最终找到的根上，而这个根在合并时已经保证它的秩是大于或等于子节点的秩，因此也不会破坏该性质。
因此，无论在初始化，还是在进行任何一次 Union 或路径压缩之后，“从任意节点出发，沿路径到达根节点的途中，各节点秩单调递增”这一事实始终得以保持。
引理 2：任何一棵秩为 的子树的根节点所代表的集合中，至少包含 个元素。
证明思路
- 初始化时，每个节点都是一棵秩为 0 的单节点树；此时根节点对应集合中只有 1 个元素，而 ，该结论显然成立。
- 假设对某个秩为 的根，集合中至少有 个节点。当我们执行按秩合并时，若有两棵秩都为 的树被合并，则新的根节点的秩变为 。而这两棵树各自至少包含 个元素，总共有不少于 个元素。因此新的树（秩为 ）至少有 个节点。
- 归纳可得：秩为 的子树至少包含 个节点。
引理 3：在任意时刻，秩为 的节点个数最多为 。
证明思路
- 根据引理 2，可知秩为 的任意根节点至少对应一个包含 个元素的子树。
- 若要“最大化”秩为 的节点数量，最理想的情况是：每个秩为 的节点都正好对应一棵大小恰好为 的子树。这样可以容纳更多的秩为 的根节点。
- 因为总共有 n 个元素，所以在这种理想情况下能够容纳的秩为 的根节点数量也就是 。
- 因此，秩为 的所有根节点个数不会超过 。
分桶（Bucketing）与秩区间的划分
为了分析 Find 操作，我们常使用“分桶”策略。具体做法是根据节点的秩（rank）将所有节点分到若干个桶（bucket）中，每个桶对应一定的秩区间。下面给出一个常见的划分方式：
- Bucket 0：包含秩为 0 的节点。
- Bucket 1：包含秩为 1 的节点。
- Bucket 2：包含秩在区间 的节点。
- 更一般地，若 第 B 个桶 包含秩在 区间内的所有节点，则 第 (B+1) 个桶 包含秩在 区间的节点。
换言之，如果我们定义一个“塔函数”（tower function），对于 ，
则第 个桶中包含的节点秩在
的范围内。
实际上，由于秩不会超过 n（更精确地说，不会超过 的某些函数，但理论上最大值有限），很容易看出，真正非空的桶数量至多是 （ 是 函数的逆函数）。
证明 的复杂度
令 表示所有 Find 操作的集合。将每次 Find(u) 的访问过程拆分为以下几部分，并用三类和来记数（每一类都是对所有 Find 操作的贡献之和）：
- 也就是每次 Find 都会“最终走”到根节点，这一条到根的链接只发生一次。
- 即，当我们从一个节点 u 访问它的父节点 v 时，如果 u 和 v 的秩分别落在不同的桶中，这样的边访问次数记到 中。
- 即，u 和 v 的秩在同一个桶里（且 v 不是根，否则会计入 ），则该访问记到 里。
设所有 m 次 Find 操作的总访问代价是
下面对这三个量分别进行估计：
- 的估计 每一次 Find 过程中，都恰有一次访问使节点到达根节点。因为共有 m 次 Find，所以 。也可以写作 。
- 的估计 跨桶访问对应的是从一个秩所处的桶跳到另一个更高秩（在后继桶中的秩）的过程。桶的总数至多是 。所以，每次 Find 最多跨越 个桶（从最初所在的桶一直到可能到达根的桶，或者在中途就已经到达根了）。 因此，累加所有 m 次 Find，在最坏情况下，每次跨桶次数都不超过 ，于是
- 的估计 这是同一桶内的边访问计数。假设我们在 Find(u) 中看到一个边 ，其中 u 和 v 的秩均在区间 。如果这条边在本次 Find 最终没有直接通向根（否则它会记到 而不是 ），那么 v 也不是根节点。我们关注固定的 u，看看有多少次会在不同的 Find 操作里访问到不同的 v（记作 ），并且每次访问时都在同一桶区间内。由于路径压缩的缘故，每当我们再次对 u 做 Find 时，如果 u 还没有变成根，它很可能已经直接挂到一个更高秩的节点上（或者最终挂到根上）。又由于引理 1（沿路径秩单调上升），在多次访问中，u 最多只能被“提升”到同一桶内的有限多级别。在区间 内，秩最多有 这么多可能的取值。所以对固定的 u 而言，它在同一个桶中只能被挂载到不同秩节点的次数最多为 次。超过这个次数后，u 的秩将会超过桶的上界，跨到下一个桶了（或者达到根）。 因此，对所有处于桶 的节点 u 累加，就能得到：
其中 表示桶内所有节点 u 的贡献之和。
上面那个东西其实就是在说明：
**同一个节点 在同一个桶里，能产生同桶访问边的最大次数是
接下来只要拿到节点的个数就可以。
那么桶 中的节点数量有多少？由引理 3 的推论可知，秩为 的节点数量至多 。如果把区间 的所有秩对应的节点数都相加，由于呈几何级数衰减，有
因此该桶中最多包含不超过 个节点。每个此桶中的节点在该桶里“横跳”或“挂载”到不同节点（同桶内）最多发生 次。于是此桶贡献的访问次数上界为
因为桶的数量最多是 个，所以在对所有桶求和之后，得到
综上所述
将 拆分为三部分：
我们已经分别得到了：
实际分析中，我们关注的是 m 次操作的总代价。当 m 与 n 在同一量级（例如 m ≥ n），则常见的结论是
如果我们着眼于平均/均摊代价（amortized cost），当 m 足够大（通常 m ≥ n）时， 可以被 所吸收（因为 m 与 n 同阶或更大），于是得到
所以，不相交集合（带按秩合并 + 路径压缩）结构在最坏情况下执行 m 次操作的总复杂度是 。因此，每次操作平均（摊还）仅需 的时间。
结合以上引理和分析，不相交集合结构在按秩合并与路径压缩两种优化策略下，可保证所有 m 次 Find 或 Union 操作的总复杂度为
时间复杂度总结
Interview Questions
[!NOTE] Q1 Social network connectivity. Given a social network containing members and a log file containing timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be or better and use extra space proportional to .
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
这个问题就是直接使用UnionFind，同时额外维护一个连通分量的数量即可。log里面的就相当于是进行union的指令。题目要求判断的边界是啥时候会全部连通。所以判断全部连通的方式可以为判断连通分量的数量。只要在原先UnionFind算法的基础上新增一个变量存储连通分量的数量即可。
关键代码：
connectionComponentCnt初始化为N。[!NOTE] Q2 2. Union-find with specific canonical element. Add a methodfind()to the union-find data type so thatfind(i)returns the largest element in the connected component containing . The operations,union(),connected(), andfind()should all take logarithmic time or better.
For example, if one of the connected components is {1, 2, 6, 9}, then the
find() method should return 9 for each of the four elements in the connected components.这道题目的解题思路是维护一个largestId数组，初始化为自身，根节点存每个连通分量的最大值，最后返回
largestId[root(i)]即可。关键代码：
[!NOTE] Q3 3. Successor with delete. Given a set of integers and a sequence of requests of the following form:
- Remove from
- Find the successor of : the smallest in such that .
DDesign a data type so that all operations (except construction) take logarithmic time or better in the worst case.
这道题直接的思路是弄一个数组，存储数字的后继。当数字被移除时，那么数字的后继等于数字的后继的后继即可。但是这样子的时间复杂度就是O(n),因为最坏情况下要遍历n次找到。
这道题需要稍微绕点弯子。要往UnionFind算法上面的思路靠，大概率就是第二题的基础上做。
Remove from 可以想象为把合并x和x的后一个元素，只要一个largestId数组来维护最大的后继即可。
关键代码：
在idea中使用assert断言的时候，需要设置VM option为-ea
Percolation
编程题就是关于Percolation系统的实现。官网题目描述
解题思路：虚拟一个topSite和bottomsite，如果topSite和bottomSite相连。那么系统percolates。重点在于open一个site的时候，需要同时union它和上下左右四个site。如果是第一行，自动和topSite连接。如果是最后一行，自动和bottomSite相连。
易错点：判断site full的时候，容易用和判断系统percolates一样的uf对象。以为直接判断uf.connected(topSite, curSite)就可以了。但是这样子会遇到washback问题。
假设我们有一个 3x3 的网格：
- 打开 (1,1)、(2,1)、(3,1) 这三个位于第一列的站点。
- 此时，系统已经渗透，因为顶部和底部通过第一列的站点连接起来。
- 然后再打开 (3,3) 这个位于右下角的站点。
由于系统已经渗透，底部虚拟节点和顶部虚拟节点已经连接。这样，尽管 (3,3) 并没有与顶部直接连接，但由于它与底部虚拟节点连接，通过并查集，isFull(3,3) 会错误地返回 true，这就是 Backwash 问题。
解决方法再用一个uf并查集，来专门解决backwash问题。
代码实现：
然后对于统计的，就是使用algs算法的统计包即可解决，只需要使用一个数组存放实验结果。在构造器里面进行实验，一直到系统percolates为止。
- 作者:很久不是自己
- 链接:https://weibo.com/article/algorithms-part1-module2
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。