algorithm - 这两种查找算法有什么区别？

Question

我有这两个查找算法，对我来说看起来相同。谁能帮我弄清楚为什么它们实际上不同？

Find ( x ) :
    if x.parent = x then 
        return x
    else 
        return Find ( x.parent )

对比

Find ( x ) :
    if x.parent = x then 
        return x
    else 
        x.parent <- Find(x.parent)
        return x.parent

我将第一个解释为

 int i = 0;    
 return i++;

而第二个作为

int i = 0;
int tmp = i++;
return tmp

这对我来说完全一样。

score 4 · Accepted Answer

现在的问题：

为了清楚起见，第一个版本是FindA，第二个是FindB。

假设你有结构：

 0
 |
 1
 |
 2
 |
...
 n

第一次调用FindA(n)将在 O(n) 中返回 0，第二次调用将在 O(n) 中返回 0，依此类推。

如果调用FindB(n)它将在 O(n) 中返回 0，但也会修改结构：

    0
 / /|\
1 2...n

现在第二次调用 FindB(n) 将在 O(1) 中返回 0。超过 FindB(k) 将在 O(1) 中返回 0。

score 2 · Accepted Answer

2

第二个会将 x.parent 的值更改为 find 结果的副作用

于 2012-09-09T02:42:17.750 回答

2 回答 2