20

这个问题一直萦绕在我的脑海中……

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

这样做的一种方法是将等价扩展到对项目的排序并对其进行排序（使用排序算法）；那么所有等效的项目将是相邻的。

但它可以比排序更有效吗？这个问题的时间复杂度比排序低吗？如果不是，为什么不呢？

4

8 回答 8

12

您似乎在这里一口气问了两个不同的问题。

1）如果只允许相等检查，它是否比我们有一些排序更容易分区？答案是不。您需要 Omega(n^2) 比较来确定最坏情况下的分区（例如，所有不同）。

2）如果允许排序，分区比排序更容易吗？答案再次是否定的。这是因为Element Distinctness Problem。也就是说，为了确定所有对象是否不同，您需要 Omega(nlogn) 比较。由于排序可以在 O(nlogn) 时间内完成（并且还具有 Omega(nlogn) 下限）并解决了分区问题，因此它们同样困难。

如果你选择一个任意的散列函数，相等的对象不需要有相同的散列，在这种情况下，你没有做任何有用的工作，把它们放在一个散列表中。

即使您确实提出了这样的散列（保证相同的对象具有相同的散列），对于好的散列，时间复杂度预计为 O(n)，最坏的情况是 Omega(n^2)。

是否使用散列或排序完全取决于问题中不可用的其他约束。

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

于 2010-07-15T15:17:14.340 回答
6

如果您可以为项目定义哈希函数以及等价关系，那么您应该能够在线性时间内进行分区 - 假设计算哈希是恒定时间。散列函数必须将等效项映射到相同的散列值。

如果没有散列函数，您将不得不将要插入分区列表的每个新项目与每个现有列表的头部进行比较。该策略的效率取决于最终会有多少分区。

假设您有 100 个项目，它们最终将被划分为 3 个列表。然后，在将每个项目插入其中一个列表之前，必须将其与最多 3 个其他项目进行比较。

但是，如果这 100 个项目最终会被划分为 90 个列表（即非常少的等价项目），那就另当别论了。现在您的运行时间更接近于二次而不是线性。

于 2010-07-15T14:34:13.127 回答
3

如果您不关心等价集的最终排序，那么划分为等价集可能会更快。但是，这取决于算法和每个集合中的元素数量。

如果每个集合中的项目很少，那么您不妨对元素进行排序，然后找到相邻的相等元素。对于 n 个元素，一个好的排序算法是 O(n log n)。

如果有几个集合，每个集合中有很多元素，那么您可以获取每个元素，并与现有集合进行比较。如果它属于其中一个，则添加它，否则创建一个新集合。这将是 O(n*m)，其中 n 是元素的数量，m 是等价集的数量，对于大 n 和小 m，它小于 O(n log n)，但当 m 趋向于 n 时更糟.

组合排序/分区算法可能更快。

于 2010-07-15T14:34:51.193 回答
2

基于比较的排序通常具有 O(n log n) 的下限。

假设您遍历您的项目集并将它们放入具有相同比较值的项目的存储桶中，例如在一组列表中（例如使用哈希集）。这个操作显然是 O(n)，即使在从集合中检索列表列表之后也是如此。

---编辑： ---

这当然需要两个假设：

  • 每个要分区的元素都存在一个恒定时间哈希算法。
  • 桶的数量不取决于输入的数量。

因此，分区的下限是 O(n)。

于 2010-07-15T14:29:04.150 回答
2

如果必须使用比较器，则下限是用于排序或分区的 Ω(n log n) 比较。原因是必须检查所有元素 Ω(n)，并且比较器必须对每个元素执行 log n 比较，以唯一地识别或放置该元素与其他元素的关系（每次比较将空间分成 2，因此对于空间大小为 n，需要进行 log n 比较。）

如果每个元素都可以与在恒定时间内派生的唯一键相关联，则下限为 Ω(n)，用于排序蚂蚁分区（参见RadixSort）

于 2010-07-15T14:29:31.480 回答
1

这是数据结构中的经典问题，是的，它比排序更容易。如果您还想快速查找每个元素属于哪个集合，您需要的是不相交集合数据结构，以及联合查找操作。见这里：http ://en.wikipedia.org/wiki/Disjoint-set_data_structure

于 2010-07-15T17:11:21.463 回答
1

通常，分区比排序快，因为您不必将每个元素与每个可能等效的已排序元素进行比较，您只需将其与分区的已建立键进行比较。仔细看看基数排序。基数排序的第一步是根据键的某些部分对输入进行分区。基数排序是 O(kN)。如果您的数据集具有以给定长度 k 为界的键，则可以对其进行基数排序 O(n)。如果您的数据具有可比性并且没有有界键，但您选择了一个有界键来对集合进行分区，那么对集合进行排序的复杂度将是 O(n log n)，而分区将是 O(n) .

于 2010-07-15T14:42:10.043 回答
0

使用散列函数执行可能不完美的分区所需的时间将是 O(n+bucketcount) [不是 O(n*bucketcount)]。使桶数足够大以避免所有冲突将是昂贵的，但如果散列函数运行良好，每个桶中应该有少量不同的值。如果可以轻松生成多个统计上独立的散列函数，则可以获取每个键与第一个不完全匹配的桶，并使用另一个散列函数来划分该桶的内容。

假设每一步的桶数恒定，时间将为 O(NlgN)，但如果将桶数设置为类似 sqrt(N)，则平均通过次数应为 O(1)，并且在每遍 O(n) 中工作。

于 2010-07-15T15:56:07.247 回答