“quick-find 算法”和“加权 quick-union 算法”处理 N 个触点和 M 条连接时的成本

[Higurashi]

在《算法（第四版）》 1.5 节对“加权 quick-union 算法”进行分析中，有这样一段话（中文 P147 ，英文 P230 ）：

加权 quick-union 算法处理 N 个触点和 M 条连接时最多访问数组 cMlgN 次，其中 c 为常数。这个结果和 quick-find 算法（以及某些情况下的 quick-union 算法）需要访问数组至少 MN 次形成了鲜明的对比。

我不明白为什么“加权 quick-union 算法”最多访问数组 cMlgN 次，“quick-find 算法”至少访问数组 MN 次：

因为，最后剩下 M 条连接至少需要调用 union 函数 (N-M) 次，对于“quick-find 算法”，union 操作至少访问 (N+3) 次数组（中文 P141 ），所以总共至少访问数组 (N-M)(N+3) 次。类似地，因为“加权 quick-union 算法”的 union 函数最多访问数组 lgN 次（中文 P147 ），所以最多访问数组 (N-M)lgN 次。

是哪里理解错了吗？谢谢。

[YouRTBUG]

举例中，原书上的话像是告诉你算法复杂度，而疑惑的次数是从实际访问数组的次数考虑的。就像刚接触算法复杂度那样，quick-find 单从 M 条边和每次访问 N 个点，推算出是 MN 。加权 quick-union ，需要再理解一下大树和小树的例子，比对为什么举例用 2^n 的树来模拟最坏情况，还有两棵 2^n 树合并。这样在最坏情况下 find 就是 lgN ，所以总共需要 clgN ，复杂度就是 cMlgN 或 ClgN (C 是和 M 有关的因子）。其实我不太懂你说的“最后剩下 M 条” 是指什么，不是总共 M 条？

[Higurashi]

@YouRTBUG #1 感谢回复。因为我理解“处理 N 个触点和 M 条连接”的意思是：开始输入 N 个触点，互不相连（有 N 个分量），然后算法依照输入将触点逐个相连，连接到最后只剩 M 个分量。所以我说“最后剩下 M 条连接”。现在看来它实际的意思应该是：输入 N 个触点，且 N 个触点组成 M 个分量。将 M 个分量连起来需要调用 M 次 union ，加权 quick-union 的 union 函数最多访问数组 lgN 次，所以最多总共最多访问数组 MlgN 次，quick-find 的 union 函数至少访问 (N+3) 次数组，所以总共至少访问数组 M(N+3) 次。和书本上的说明接近，只是不知道为什么 MlgN 前面有一个常数 c ？另外 M(N+3) 次的总次数与 MN 还是有差别。

[YouRTBUG]

@Higurashi “ MlgN 前面有一个常数 c” 最坏情况因为都是等量的 2^n 树合并，find 我觉得可以这样看假如 2^m = N, lg2^n = nlg2 = c1 m lg 2 = c1 lg 2^m = c1 lg N, 我觉得你说得 M(N+3) 次有点道理的，也赞同你这样想，感觉这里就把这两个算法的设计思路吸收下就可以了！

[Higurashi]

@YouRTBUG #3 嗯，再次感谢！