“quick-find 算法”和“加权 quick-union 算法”处理 N 个触点和 M 条连接时的成本
Higurashi · 2022-03-10 11:42:00 +08:00 · 902 次点击这是一个创建于 982 天前的主题，其中的信息可能已经有所发展或是发生改变。
在《算法（第四版）》 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 次。
是哪里理解错了吗？谢谢。
4 条回复 • 2022-03-10 15:06:37 +08:00
 |
1
YouRTBUG 2022-03-10 13:22:23 +08:00
举例中，原书上的话像是告诉你算法复杂度，而疑惑的次数是从实际访问数组的次数考虑的。就像刚接触算法复杂度那样，quick-find 单从 M 条边和每次访问 N 个点，推算出是 MN 。加权 quick-union ，需要再理解一下大树和小树的例子，比对为什么举例用 2^n 的树来模拟最坏情况，还有两棵 2^n 树合并。这样在最坏情况下 find 就是 lgN ，所以总共需要 clgN ，复杂度就是 cMlgN 或 ClgN (C 是和 M 有关的因子）。其实我不太懂你说的“最后剩下 M 条” 是指什么，不是总共 M 条？
|
 |
2
Higurashi OP @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 还是有差别。
|
Select Language