1

我正在研究关于不相交集的算法。

和章节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 组中，等等。

要进行 Union(a, b) （假设 a 在集合 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)。无法想象我上面写的代码这样的复杂性。

4

1 回答 1

2

我们希望尽可能降低所有操作的总复杂度。

总复杂度 = 复杂度（FIND）+ 复杂度（UNION）

正如您所说，如果给定 n - 1 个联合序列在最坏的情况下需要 O(n^2) 时间。find 平均需要 O(1)。

因此，对于 n-1 个联合操作，我们可以在不增加大于 O(n^2) 的总复杂度的情况下提供多少个查找。

答案是可以支持 O(n^2) 查找操作。

所以只要 FIND 的数量是 <= O(n^2)并且 UNION 的数量是 <= O(n)。复杂性保持不变。

一般规则：较重的操作（较耗时）应少用较轻操作的重量，较轻的操作应与较重操作的重量一样多。

我希望这已经足够了。

于 2016-10-06T06:54:59.180 回答