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

这对我来说完全一样。

Answer 1

这看起来像 Disjoint-set data structure .

现在回答问题:

为了清楚起见，第一个版本是 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。