合并至少共享两个元素的集合的算法

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

我的头是说这是关于秩序(2n ln n)。 把它和一粒盐一起吃。

如果可以对集合中的元素进行排序,则可以使用 Mergesort 在集合上。唯一需要的修改是在合并阶段检查重复项。如果找到了,只需丢弃副本。由于mergesort是O(n*log(n)),与naive O(n^2)算法相比,这将提供潜在的速度。

但是,为了真正有效,您应该维护一个排序集并保持它的排序,这样您就可以跳过排序阶段并直接进入合并阶段。

一个旁注:这取决于这种情况发生的频率。如果大多数集合对 做 至少共享两个元素,在进行比较的同时构建新的集合可能是最有效的,如果它们不匹配条件,则将其丢弃。如果大多数配对 不 共享至少两个元素,然后推迟新集合的构建,直到确认条件可能更有效。

我不明白这是如何在小于0(n^2)的时间内完成的。

每个集合都需要与其他集合进行比较,以查看它们是否包含2个或更多共享元素。这是n*(n-1)/2比较,因此o(n^2),即使检查共享元素需要恒定的时间。

在排序中,幼稚的实现是O(n^2),但您可以利用有序比较的传递性(例如,您不知道Quicksort的下分区中的任何内容都需要与上分区中的任何内容进行比较,因为它已经与Pivot进行了比较)。这就是排序结果是O(n*log n)。

这里不适用。所以,除非集合中有一些特殊的东西,可以让我们根据之前的比较结果跳过比较,一般来说它是O(n^2)。

保罗。

如果您的元素本质上是数字的,或者可以自然排序(例如,您可以指定一个值,如1、2、42等),我建议对合并集使用基数排序,并进行第二次传递以获取唯一的元素。

该算法应该是O(N),您可以使用位移位运算符和位掩码对基数排序进行相当大的优化。我为一个我正在做的项目做了类似的工作,它的工作方式很有魅力。