不相交集查找和聯合操作的複雜性

Question

我正在研究有關不相交集合的算法。

和Fast FIND Implementation (Quick Find)

的數據結構的章節如下：

例如）

int array[5] 

[0] = 3, 
[1] = 5, 
[2] = 7, 
[3] = 1, 
[4] = 2, 

在[number] = set name（上面的例子），數量是在該組名稱的元素。

所以，編號0是在該組3，編號1是在該組5，...，等等

要做到聯盟（A，B）（假定是集合I和B在集合j）中，它需要O（n）操作。我知道這個。原因如下（僞代碼）：

void Union(a, b) { 
     int set1 = Find(a); /* set 1 will be 'i' */ 
     int set2 = Find(b); /* set 2 will be 'j' */ 

     if(set 1 != set2) 
      for(int i = 0; i < sizeof(array); i++) { /* O(n) operation */ 
       if(array[i] == set1) 
        array[i] = set2; 
      } 
} 

但是，在書中，我不明白這一點：

N的序列 - 1個工會採取爲O（n^2）時間在最壞的情況下。如果有O（n^2）個FIND操作，則此性能很好，因爲每個UNION或FIND操作的平均時間複雜度爲O（1）。如果FIND較少，則這種複雜性是不可接受的。

我不明白這些句子的含義是什麼，爲什麼複雜度是O（n^2）。無法想象像我上面寫的代碼這樣的複雜性。

Answer 1

我們希望儘可能降低所有操作的總體複雜度。

總複雜=複雜性（FIND）+複雜（UNION）

正如你所說，如果我們考慮到的N序列 - 1工會採取爲O（n^2）在最壞情況下的時間。並找到平均O（1）。

因此，對於n-1聯合操作，我們可以承擔多少發現而不會增加大於O（n^2）的總複雜度。

答案是O（n^2）查找操作可以被支持。

所以只要FIND的數目是< = 爲O（n^2）和UNION的數目是< = 爲O（n）。複雜性保持不變。

一般規則：較重操作（更耗時）應作爲較少的次數作爲打火機操作的重量，而較輕的操作應該被用作許多的次數作爲較重操作的重量。

我希望這已經足夠。