这两种查找算法有何区别？

Question

3

我有两种查找算法，它们看起来很相似。有人能帮我解释一下它们实际上有什么不同吗？

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

vs

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

对我来说，它们完全相同。

- Joe

3

移除Java标签 - x.parent <- Find(x.parent) 不是Java。 - Bohemian

1

x.parent <- Find(x.parent) 修改了 x.parent，而第一个没有这样做。 - Blender

2个回答

2

第二个会通过find的结果作为副作用改变x.parent的值。

- user1655424

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kilotaras · 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。