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

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

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

(练习)

1.5.1 使用 quick-find 算法处理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。对于输入的每一对整数,给出 id[] 数组的内容和访问数组的次数。

1.5.2 使用 quick-union 算法(请见 1.5.2.3 节代码框)完成练习 1.5.1。另外,在处理完输入的每对整数之后画出id[] 数组表示的森林。

1.5.3 使用加权 quick-union 算法(请见算法 1.5)完成练习 1.5.1。

1.5.4 在正文的加权 quick-union 算法示例中,对于输入的每一对整数(包括对照输入和最坏情况下的输入),给出 id[]sz[] 数组的内容以及访问数组的次数。

1.5.5 在一台每秒能够处理 109 条指令的计算机上,估计 quick-find 算法解决含有 109 个触点和 106 条连接的动态连通性问题所需的最短时间(以天记)。假设内循环 for 的每一次迭代需要执行 10 条机器指令。

1.5.6 使用加权 quick-union 算法完成练习 1.5.5。

1.5.7 分别为 quick-find 算法和 quick-union 算法实现 QuickFindUF 类和 QuickUnionUF 类。

1.5.8 用一个反例证明 quick-find 算法中的 union() 方法的以下直观实现是错误的:

复制代码
public void union(int p, int q)
{
if (connected(p, q)) return;
// 将 p 的分量重命名为 q 的分量
for (int i = 0; i < id.length; i++)
if (id[i] == id[p]) id[i] = id[q];
count--;
}

1.5.9 画出下面的 id[] 数组所对应的树。这可能是加权 quick-union 算法得到的结果吗?解释为什么不可能,或者给出能够得到该数组的一系列操作。

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

1.5.10 在加权 quick-union 算法中,假设我们将 id[find(p)] 的值设为 q 而非 id[find(q)],所得的算法是正确的吗?

:是,但这会增加树的高度,因此无法保证同样的性能。

1.5.11 实现加权 quick-find 算法,其中我们总是将较小的分量重命名为较大的分量的标识符。这种改变会对性能产生怎样的影响?

评论

发布