不相交集查找和联合操作的复杂性

Question

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

以及Fast FIND Implementation (Quick Find)的章节

数据结构如下图：

例如）

int array[5]

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

在[number] = set name（上例）中，number是集合名称中的元素。

因此，数字 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)。无法想象我上面写的代码这么复杂。

Answer 1

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

总复杂度 = 复杂度(FIND) + 复杂度(UNION)

如您所说，如果给定 n - 1 个并集序列，在最坏情况下需要 O(n^2) 时间。并且 find 平均花费 O(1)。

那么对于 n-1 个并集运算，我们可以在不增加大于 O(n^2) 的总复杂度的情况下找到多少个。

The answer is O(n^2) find operations can be supported.

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

一般规则：大的操作（耗时多）次数越少，操作越轻，操作越轻，次数越多次作为重量较重的操作。

我希望这足够了。

不相交集查找和联合操作的复杂性

Disjoint set find & union operation's complexity

c

algorithm

union-find