Union-Find性能解释

Question

参考了 Robert Sedgewick 和 kevin Wayne 合着的 Algorithm（第四版）一书

对于 Union-find 实现，find 和 union 的代码如下（第 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--;
}

然后是一个命题：

Proposition F. The quick-find algorithm uses one array access for each call to find() and between N + 3 and 2N + 1 array accesses for each call to union() that combines two components.

我想了解我们实际上是如何得出 N + 3 和 2N + 1 的。我对 N + 3 有一些想法，但对 2N + 1 没有想法。请帮忙。

Answer 1

对于 pID != qID 的情况，我们有：

2 次访问：

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

在 if 条件的循环中进行 N 次访问：

if (id[i] == pID)

到目前为止 N+2，但是由于 pID != qID 至少 p 有 pID!=qID 所以我们将在 if 语句中再访问一次： id[i] = qID; 所以我们将至少访问数组N=3次。

在最坏的情况下，所有 N 元素都有 id pID 我们将执行 id[i] = qID; N-1 次（不像以前那样只执行一次，N-1 因为 q 有 qID 所以我们不会为 q 访问数组）所以总的来说： 2 + N （如果在 for 循环中有条件访问所有 N 个元素）+ N-1 （对于 id[i] = qID; ）= 2N+1.

示例：

如果数组如下所示：qID qID qID pID qID（5 个元素）

然后调用union(1,4) //1 index 是第一个元素(with qID), 4 是第4(pID)

一开始您将有 2 次访问，如果条件为 5 次，如果条件为真则只有一次 - 对于 4，元素是唯一具有 pID 的元素，因此您有 2+5+1 =8= N+3 最小值。

现在以最大访问数为例，获取数组：qID pID pID pID pID 现在你将有 2+5 + 4（因为有四个条件为真）= 11 = 2N+1 (N=8).

Union-Find性能解释

Union-Find performance explanation

algorithm

union-find