本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- quick-find分析
题目
1.5.8 用一个反例证明 quick-find 算法中的 union() 方法的以下直观实现是错误的。
1.5.8 Give a counterexample that shows why this intuitive implementation of union() for quick-find is not correct:
public void union(int p, int q)
{
if (connected(p, q)) return;
// Rename p’s component to q’s name.
for (int i = 0; i < id.length; i++)
if (id[i] == id[p]) id[i] = id[q];
count--;
}
分析
我们这里先贴出原来的union方法
public void union(int p, int q) { // Put p and q into the same component.
int pID = find(p);
int qID = find(q);
// Nothing to do if p and q are already in the same component.
if (pID == qID) return;
// Rename p’s component to q’s name.
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
我们可以看到主要的区别点在于for循环下面的这句话：
if (id[i] == pID) id[i] = qID;
我们知道，这里的pID和qID都是整形值，是固定的，但题目中给的
if (id[i] == id[p]) id[i] = id[q];
的id[p]和id[q]的值不一定固定。
在if后如果id[p]发生了改变，那么这个等式就可能出问题
答案
id 0 0 0 0 0 5 5 5 5 5
输入 0, 5
i = 0 时，id[i] == id[p]，此时 id[i] = id[q]。
数组变为 5 0 0 0 0 5 5 5 5 5
i = 1 时，id[i] != id[p]，算法出现错误。
如果在 id[p] 之后还有需要修改的元素，那么这个算法就会出现错误。
