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

阅读数:6 2019 年 11 月 9 日 15:59

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

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

图 1.5.8 显示了加权 quick-union 算法的最坏情况。其中将要被归并的树的大小总是相等的(且总是 2 的幂)。这些树的结构看起来很复杂,但它们均含有 2n 个节点,因此高度都正好是 n。另外,当我们归并两个含有 2n 个节点的树时,我们得到的树含有 2n+1 个节点,由此将树的高度增加到了 n+1。由此推广我们可以证明加权 quick-union 算法能够保证对数级别的性能。加权 quick-union 算法的实现如算法 1.5 所示。

复制代码
% java WeightedQuickUnionUF < mediumUF.txt
528 503
548 523
...
3 components
% java WeightedQuickUnionUF < largeUF.txt
786321 134521
696834 98245
...
6 components

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

图 1.5.8 加权 quick-union 算法的轨迹(森林)

算法 1.5(续) union-find 算法的实现(加权 quick-union 算法)
算法(4th ed)(210):基础——案例研究:union-find 算法 7.2.7
根据正文所述的森林表示方法这段代码很容易理解。我们加入了一个由触点索引的实例变量数组 sz[],这样union() 就可以将小树的根节点连接到大树的根节点。这使得算法能够处理规模较大的问题。

命题 H。对于 N 个触点,加权 quick-union 算法构造的森林中的任意节点的深度最多为 lgN
证明。我们可以用归纳法证明一个更强的命题,即森林中大小为 k 的树的高度最多为 lgk。在原始情况下,当 k 等于 1 时树的高度为 0。根据归纳法,我们假设大小为 i 的树的高度最多为 lgi,其中 i<k。设 iji+j=k,当我们将大小为 i 和大小为 j 的树归并时,quick-union 算法和加权 quick-union 算法中触点与深度示例如图 1.5.9 所示。小树中的所有节点的深度增加了 1,但它们现在所在的树的大小为 i+j=k,而 1+lgi=lg(i+i)lg(i+j)=lgk,性质成立。

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

图 1.5.9 quick-union 算法与加权 quick-union 算法的对比(100 个触点,88 次 union() 操作)

推论。对于加权 quick-union 算法和 N 个触点,在最坏情况下 find()connected()union() 的成本的增长数量级为 logN
证明。在森林中,对于从一个节点到它的根节点的路径上的每个节点,每种操作最多都只会访问数组常数次。

对于动态连通性问题,命题 H 和它的推论的实际意义在于加权 quick-union 算法是三种算法中唯一可以用于解决大型实际问题的算法。加权 quick-union 算法处理 N 个触点和 M 条连接时最多访问数组 cMlgN 次,其中 c 为常数。这个结果和 quick-find 算法(以及某些情况下的 quick-union 算法)需要访问数组至少 MN 次形成了鲜明的对比。因此,有了加权 quick-union 算法我们就能保证能够在合理的时间范围内解决实际中的大规模动态连通性问题。只需要多写几行代码,我们所得到的程序在处理实际应用中的大型动态连通性问题时就会比简单的算法快数百万倍。

图 1.5.9 显示的是一个含有 100 个触点的例子。从图中我们可以很明显地看到,加权 quick-union 算法中远离根节点的节点相对较少。事实上,只含有一个节点的树被归并到更大的树中的情况很常见,这样该节点到根节点的距离也只有一条链接而已。针对大规模问题的经验性研究告诉我们,加权 quick-union 算法在解决实际问题时一般都能在常数时间内完成每个操作(如表 1.5.3 所示)。我们可能很难找到比它效率更高的算法了。

表 1.5.3 各种 union-find 算法的性能特点

算法存在 N 个触点时成本的增长数量级(最坏情况下)
构造函数union()find()
quick-find 算法NN1
quick-union 算法N树的高度树的高度
加权 quick-union 算法NlgNlg
使用路径压缩的加权 quick-union 算法N非常非常地接近但仍没有达到(请见练习 1.5.13)1(均摊成本)
理想情况N11

评论

发布