是分区比排序更容易？ [英] Is partitioning easier than sorting?

问题描述

这是一个问题，一直萦绕在我的脑海里有一段时间了...

This is a question that's been lingering in my mind for some time ...

假设我有一个项目列表和它们的等价关系，并比较两个项目需要一定的时间。 我想返回的项目分区，例如联列表的列表，每个都包含所有等效项。

Suppose I have a list of items and an equivalence relation on them, and comparing two items takes constant time. I want to return a partition of the items, e.g. a list of linked lists, each containing all equivalent items.

这样做的一种方法是将等价延伸到排序上的项目，并命令它们（用排序算法）;那么所有的等价物品将毗邻。

One way of doing this is to extend the equivalence to an ordering on the items and order them (with a sorting algorithm); then all equivalent items will be adjacent.

但可以把它比排序进行更有效？这方面的问题比排序的较低的时间复杂？如果不是，为什么不呢？

But can it be done more efficiently than with sorting? Is the time complexity of this problem lower than that of sorting? If not, why not?

推荐答案

您似乎在问两个不同的问题，在一个放在这里。

You seem to be asking two different questions at one go here.

1）如果只允许相等检查，它使分区比，如果我们有一些顺序更容易？答案是，没有。您需要欧米茄（N ^ 2）比较，以确定在最坏的情况下，分区（所有不同的实例）。

1) If allowing only equality checks, does it make partition easier than if we had some ordering? The answer is, no. You require Omega(n^2) comparisons to determine the partitioning in the worst case (all different for instance).

2）如果允许排序，分区是比排序更容易？答案仍然是否定的。这是因为元素清晰与问题的。它说，为了即使确定是否所有的对象是不同的，你需要欧米茄（nlogn）的比较。由于排序可以在O（nlogn）的时间内完成（也有欧米茄（nlogn）下限），并解决了分区的问题，渐近他们同样辛苦。

2) If allowing ordering, is partitioning easier than sorting? The answer again is no. This is because of the Element Distinctness Problem. Which says that in order to even determine if all objects are distinct, you require Omega(nlogn) comparisons. Since sorting can be done in O(nlogn) time (and also have Omega(nlogn) lower bounds) and solves the partition problem, asymptotically they are equally hard.

如果你选择一个任意哈希函数，相等的对象不一定具有相同的哈希，在这种情况下，你还没有把他们在哈希表中所做的任何有用的工作。

If you pick an arbitrary hash function, equal objects need not have the same hash, in which case you haven't done any useful work by putting them in a hashtable.

即使你想出了这样一个散列（相等的对象保证具有相同的哈希），时间复杂度的预计的O（n）的好散列和最坏的情况是欧米茄（ N ^ 2）。

Even if you do come up with such a hash (equal objects guaranteed to have the same hash), the time complexity is expected O(n) for good hashes, and worst case is Omega(n^2).

是否使用散列或完全排序取决于这个问题不可用其他的限制。

Whether to use hashing or sorting completely depends on other constraints not available in the question.

其他的答案也似乎忘记了你的问题（主要是）关于比较分区和分类！

The other answers also seem to be forgetting that your question is (mainly) about comparing partitioning and sorting!

这篇关于是分区比排序更容易？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！