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

Question

不相交集问题

让 A 和 B 成为两个集合，它们是不相交的吗？

问题

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

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

我怎么做 ？

Answer 1

我不太清楚你的问题，有一些非常快速的线性排序算法需要 O(n) 像基数桶和计数排序，这可能取决于你输入的性质。

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