算法(4th ed)(205):基础——案例研究:union-find 算法 7.2.2

阅读数:15 2019 年 11 月 9 日 15:51

算法(4th ed)(205):基础——案例研究:union-find 算法 7.2.2

(实现:quick-find 算法的分析)

find() 操作的速度显然是很快的,因为它只需要访问 id[] 数组一次。但 quick-find 算法一般无法处理大型问题,因为对于每一对输入 union() 都需要扫描整个 id[] 数组。

命题 F。在 quick-find 算法中,每次 find() 调用只需要访问数组一次,而归并两个分量的 union() 操作访问数组的次数在 (N+3)(2N+1) 之间。
证明。由代码马上可以知道,每次 connected() 调用都会检查 id[] 数组中的两个元素是否相等,即会调用两次 find() 方法。归并两个分量的 union() 操作会调用两次 find(),检查 id[] 数组中的全部 N 个元素并改变它们中 1 到 N1 个元素的值。

假设我们使用 quick-find 算法来解决动态连通性问题并且最后只得到了一个连通分量,那么这至少需要调用 N1union(),即至少 (N+3)(N1)N2 次数组访问——我们马上可以猜想动态连通性的 quick-find 算法是平方级别的。将这种分析推广我们可以得到,quick-find 算法的运行时间对于最终只能得到少数连通分量的一般应用是平方级别的。在计算机上用倍率测试可以很容易验证这个猜想(指导性的例子请见练习 1.5.23)。现代计算机每秒钟能够执行数亿甚至数十亿条指令,因此如果 N 较小的话这个成本并不是很明显。但是在现代应用中我们也很可能需要处理几百万甚至数十亿的触点和连接,例如我们的测试文件 largeUF.txt。如果你还不相信并且觉得自己的计算机足够快,请使用 quick-find 算法找出 largeUF.txt 中所有整数对所表示的连通分量的数量。结论无可争议,使用 quick-find 算法解决这种问题是不可行的,我们需要寻找更好的算法。

评论

发布