2

我正在通过sedgewickquick-union algorithm书中的分析。作者给出了这段代码和注释Algorithms 4th ed

...
for(int i =0; i< N; i++){
    id[i] = i;
}
...
private int find(int p){
    while(p != id[p]){
        p = id[p];
    }
    return p;
}

public void union(int p, int q) {       
    int proot = find(p);
    int qroot = find(q);
    if (proot == qroot){
        return;
    }
    id[proot] = qroot;
    this.count--;
}

考虑最坏的情况，其中 p,q 对 (0,1),(0,2),(0,3),(0,4) 等被赋予union().autor 评论说对的数组访问union()次数0,i是完全正确2i+3（注意：在书中它打印为 2i+2，但勘误表说 2i+3）。站点 0 位于深度 i，站点 i 位于深度 0。

我试图为 call union(0,1) 解决这个问题

这涉及两个find()调用（以 0 和 1 作为输入）和一个数组修改id[proot]= qroot

考虑 find(0)

数组 id[] 是0,1,2,3,4..

在while循环中，p =0

测试 0 != id[0] 失败，因为 id[0]=0 。所以，在 find(0) 中只有 1 个数组访问

在 find(1) 中，test 1 != id[1] 失败，因此 find(1) 只访问 1 个数组。

然后 id[proot] = qroot 仅导致 1 次数组访问。

总共有 3 个数组访问。

但是当使用等式 2i+3 时（对于 (0,i) 对）

对 (0,1) 的数组访问次数 -> 2*1+3 = 5

我很困惑..有人可以告诉我我错在哪里了吗？

4

1 回答 1

1

我的分析似乎同意你的观点，原始解决方案和勘误表都是错误的。我的主张是2(i-1) + 3假设union(0, i)调用模式是union(0, 1), union(0, 2), ..., union(0, i). 我们可以通过归纳来证明。

特别是，我们证明了一个更强有力的主张，即union(0, i)进行2(i-1 + 3数组访问，并且id数组看起来像th1, 2, 3, ..., k-2, k, k, k+1, ..., N之后的样子。更强的声明使感应干净。kunion()

正如您所观察到的，在基本情况下，对于union(0, 1). 那时，通过检查，我们有一个看起来像[1, 1, 2, ..., N]所需的数组。在归纳步骤中，我们假设声明成立1 <= j <= k并考虑id数组在union(0, k+1). 此时它看起来像

[1, 2, 3, ..., k-2, k, k, k+1, ..., N]

由归纳假设。在这一点上，通过检查，我们有我们的主张。特别是，find(0)将进行2(k + 1 - 1)数组访问。find(k+1)需要两个。的分配id[0] = k+1是最后一个给我们2((k + 1) - 1) + 2 + 1 => 2((k + 1) - 1) + 3所需的。请注意，数组也会变成

[1, 2, 3, ..., k-2, k-1, k+1, k+1, k+2, ..., N]

因为我们需要进行归纳。

你在评论中提到的关于这个的后半部分Theta(n^2)来自一些代数。特别是让f(n)数组访问的次数来自调用数组union(0, 1), union(0, 2), ..., union(0, n)的n < N大小。然后上面的声明表明了f(n) - f(n-1) = 2(n - 1) + 1和f(1) = 3（我们的基本情况）。然后我们有

f(n) = f(n) - f(n-1) + 
       (f(n-1) - f(n-2)) + 
       (f(n-2) - f(n-3)) + 
       ... + 
       (f(2) - f(1)) + 
       f(1)
=>
f(n) = 2(n-1) + 3 +
       2(n-2) + 3 +
       2(n-3) + 3 +
       ... +
       2(1) + 3 + 
       2(0) + 3
=>
f(n) = Sum(2(i-1) + 3) from i = 1 to i = n

第一步是因为它“望远镜”并且通过检查是真实的。像这样计算算术有限级数有一个绝妙的技巧。您添加第一个和最后一个元素，然后添加第二个和倒数第二个元素，依此类推。你会注意到它们都是一样的，而且可以证明它们是一样的。我会让你搞砸的，但封闭的形式是

n^2 + 2

表明这Theta(n^2)是“留给读者的练习”呵呵。如果一切都失败了，你应该在你的教科书中看到一个等效的证明。

哦，我在上面的评论中提到，即使是这样，2i+2或者2i+3上面的证明也不会真正改变那么多。一定要花时间问这个问题，而不是几个小时……尤其是如果你对自己的答案有信心（通过像我在这里所做的那样证明它，或者在你的脑海中勾勒出证明）。几乎可以保证存在偏离 1 非常重要的情况（有些基本情况实际上很难看出为什么它们具有某些值！花时间知道为什么它是 0 而不是 1 可能很有价值），所以你必须做出自己的判断。祝你好运

于 2013-06-26T17:27:31.847 回答