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

阅读数:5 2019 年 11 月 9 日 15:52

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

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

quick-union 算法看起来比 quick-find 算法更快,因为它不需要为每对输入遍历整个数组。但它能够快多少呢?分析 quick-union 算法的成本比分析 quick-find 算法的成本更困难,因为这依赖于输入的特点。在最好的情况下,find() 只需要访问数组一次就能够得到一个触点所在的分量的标识符;而在最坏情况下,这需要 2N+1 次数组访问,如图 1.5.6 中的 0 触点(这个估计是较为保守的,因为 while 循环中经过编译的代码对 id[p] 的第二次引用一般都不会访问数组)。由此我们不难构造一个最佳情况的输入使得解决动态连通性问题的用例的运行时间是线性级别的;另一方面,我们也可以构造一个最坏情况的输入,此时它的运行时间是平方级别的(请见图 1.5.6 和下面的命题 G)。幸好我们不需要面对分析 quick-union 算法的问题,我们也不会仔细对比 quick-union 算法和 quick-find 算法的性能,因为我们下面将会学习一种比两者的效率都高得多的算法。目前,我们可以将 quick-union 算法看做是 quick-find 算法的一种改良,因为它解决了 quick-find 算法中最主要的问题(union() 操作总是线性级别的)。对于一般的输入数据这个变化显然是一次改进,但 quick-union 算法仍然存在问题,我们不能保证在所有情况下它都能比 quick-find 算法快得多(对于某些输入,quick-union 算法并不比 quick-find 算法快)。

定义。一棵树的大小是它的节点的数量。树中的一个节点的深度是它到根节点的路径上的链接数。树的高度是它的所有节点中的最大深度。
命题 G。quick-union 算法中的 find() 方法访问数组的次数为 1 加上给定触点所对应的节点的深度的两倍。union()connected() 访问数组的次数为两次 find() 操作(如果 union() 中给定的两个触点分别存在于不同的树中则还需要加 1)。
证明。请见代码。

同样,假设我们使用 quick-union 算法解决了动态连通性问题并最终只得到了一个分量,由命题 G 我们马上可以知道算法的运行时间在最坏情况下是平方级别的。假设输入的整数对是有序的 0-1、0-2、0-3 等,N1 对之后我们的 N 个触点将全部处于相同的集合之中且由 quick-union 算法得到的树的高度为 N1,其中 0 链接到 1,1 链接到 2,2 链接到 3,如此下去(请见图 1.5.6)。由命题 G 可知,对于整数对 0-i,union() 操作访问数组的次数为 2i+1(触点 0 的深度为 i1,触点 i 的深度为 0)。因此,处理 N 对整数所需的所有find() 操作访问数组的总次数为 3+5+6++(2N1)N2

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

图 1.5.6 quick-union 算法的最坏情况

评论

发布