《算法4》 1.5 并查集 算法分析

Question

关于《算法4》1.5 并查集这边，涉及3个算法分别是：

1. quick-find
2. quick-union
3. 加权quick-union

书中给出3种算法分析效率是:

• quick-find：

在quick-find 算法中,每次 find() 调用只需要访问数组一次,而归并两个分量的union()操作访问数组的次数在 (N+3) 到 (2N+1) 之间。

证明。由代码马上可以知道, 每次connected()调用都会检查id[]数组中的两个元素是否相等, 即会调用两次find()方法。归并两个分量的union()操作会调用两次 find(),检查 id[]数组中的全部 N 个元素并改变它们中 1 到 N-1 个元素的值。

• quick-union 算法

在最好的情况下,find()只需要访问数组一次就能够得到一个触点所在的分量的标识符;而在最坏情况下,这需要 2N+1 次数组访问

• 加权 quick-union 算法

对于N个触点,加权 quick-union 算法构造的森林中的任意节点的深度最多为lgN。
加权 quick-union 算法处理 N 个触点和 M 条连接时最多访问数组 cMlgN 次,其中 c 为常数。

---

问题是，这三个算法，"N+3","2N+1","2N+1","lgN"，"cMlgN"都是怎么推出来的。

Answer 1

• quick-find：

find 两次 1 + 1，循环外层n次，这是固定的，内层 至少一次 + 1，最多 n - 1,所以n-3到2n+1

• quick-union

 最坏的情况，总共:1个分量，第n次，n-1 次访问到达根索引，即索引指向自己的根位置，第n次访问次数(n-1)*2+1

• 加权 quick-union 算法

最坏的情况: 两个需要归并的树总是高度相同的，如果发生这种情况那么 其数量总是为 2的幂
数量：1 2 4 8 ***** 2^k=n
高度：0 1 2 3 ***** k

k = lgn

所以最高高度为lgn

数学归纳法:
n = 1 高度为0；
i<j , i + j = n, 当数量为i的树和数量为j的树归并时，如果用加权quick-union高度只会增加1, 数量依然为n,1+ lgi = lgi+i<=lg(i+j)=lgn 也证明了加权的quick-union最高高度为lgn成立。
M个链接，最高高度为lgn,直接Mlgn,当然不只一次，connected,find,union都有使用，当n非常大的时候，其他单次常量访问基本可以忽略（我觉得我可能每理解准确，欢迎指导），所以直接cMlgn了