聯盟獲取廣告效果的解釋

Question

這是參照書算法（Fouth版）由羅伯特·塞奇威克&凱文·韋恩

對於聯盟找到實現中，發現代碼和工會給出（第222頁）作爲：

public int find(int p) 
{ 
    return id[p]; 
} 

public void union(int p, int q) 
{ 
// Put p and q into the same component. 

int pID = find(p); 
int qID = find(q); 

// Nothing to do if p and q are already in the same component. 

if (pID == qID) return; 

// Rename p’s component to q’s name. 

for (int i = 0; i < id.length; i++) 
     if (id[i] == pID) id[i] = qID; 
count--; 
} 

然後如下命題：

命題F.快速查找的算法使用每個 調用一個數組訪問找到（）和betwee對每個組合了兩個組件的union（）調用每個調用n + 3和2N + 1的數組。

我想了解我們是怎麼實際上是在N + 3和2N + 1到達。我對N + 3有一些想法，但對2N + 1不瞭解。請幫忙。

Answer 1

對於pID != qID我們的情況下：

2訪問爲：

int pID = find(p); 
int qID = find(q); 

和N在如果條件訪問在循環：

if (id[i] == pID) 

到目前爲止N + 2，但由於pID != qID至少p有pID!=qID因此我們將在if語句中再次訪問一次：id[i] = qID;所以我們將訪問數組至少N = 3 t輸入法。

在最壞的情況下，所有的N元素具有ID pID我們將執行id[i] = qID; N-1次（不只是一次以前一樣，N-1，因爲q的qID所以我們不會訪問爲Q陣列），這樣整體： + ñ（如果條件在for循環所有N個元素的訪問權限）+ N-1（對於id[i] = qID;）= 2N + 1。

實施例：

如果陣列看起來像：qID qID qID pID qID（5元素）

然後調用union(1,4) // 1索引是第一元件（帶QID），4是第4（PID）

你將在開始時有2次訪問，如果條件爲真，則只有一次，如果條件爲真，則只有一次 - 對於只有pID的元素，因此您有2+5+1 =8= N+3最小值。

現在例如具有最大訪問採取陣列：qID pID pID pID pID 現在你將有2+5 + 4（因爲四個條件爲真）= 11 = 2N+1（N = 8）。