1

这是参考 Robert Sedgewick 和 kevin Wayne 所著的《算法（第四版）》一书

对于 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--;
}

然后是一个命题：

命题 F。快速查找算法对 find() 的每次调用使用一次数组访问，对结合两个组件的 union() 的每次调用使用 N + 3 到 2N + 1 次数组访问。

我想了解我们实际上是如何到达N + 3和2N + 1的。我对 N + 3 有一些想法，但对 2N + 1 不知道。请帮忙。

4

1 回答 1

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 元素都有 idpID我们将执行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 索引是第一个元素（带有 qID），4 是第 4 个（pID）

一开始您将有 2 个访问权限，5 个用于 if 条件，只有一个 if 条件为真 - 对于 4 个元素，它是唯一具有 pID 的元素，因此您拥有2+5+1 =8= N+3最小值。

现在例如使用最大访问次数获取数组：qID pID pID pID pID 现在您将拥有2+5 + 4（因为四个条件为真）= 11 = 2N+1（N = 8）。

于 2017-09-26T11:30:07.323 回答