algorithm - これら 2 つの検索アルゴリズムの違いは何ですか?

Question

私には同じように見えるこれら2つの検索アルゴリズムがあります。なぜそれらが実際に異なるのか、誰かが私を助けることができますか?

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++;

2番目のものは

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

私とまったく同じです。

Answer 1

これはDisjoint-set data structure のように見えます。

今質問に：

わかりやすくするために、最初のバージョンはFindA、2 番目のバージョンは ですFindB。

次の構造があるとします。

 0
 |
 1
 |
 2
 |
...
 n

への最初の呼び出しFindA(n)は O(n) で 0 を返し、2 番目の呼び出しは O(n) で 0 を返します。

呼び出すFindB(n)と、O(n) で 0 が返されますが、構造も変更されます。

    0
 / /|\
1 2...n 

FindB(n) への 2 回目の呼び出しは、O(1) で 0 を返します。さらに、FindB(k) は O(1) で 0 を返します。