证明任何求解不相交集的算法至少需要 nlog n

Question

不相交集问题

Let A and B be two sets , are they disjoint ?

问题

证明任何求解不相交集的算法至少需要 O(nlog n)。

我想到的想法是证明排序可以归结为不相交的集合问题。

我该怎么做？

Answer 1

我不太完全理解你的问题，有一些非常快速的线性排序算法采用 O(n)，比如基数桶和计数排序，根据你输入的性质，它们可能适合。

你的问题是你是否可以在多项式时间内将排序减少到不相交的集合，即使在这种情况下，这也很可能无法解决你的问题，因为如果你可以在多项式时间内将排序减少到不相交的集合，这将意味着不相交集合至少和排序一样难，这意味着解决不相交集合的算法可能比解决排序的算法花费更长的时间。