logo标签列表

分区比排序更容易吗？

algorithmsortingpartitioningtime-complexity
21

这是我思考已久的一个问题...

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

一种方法是将等价性扩展为项目的排序，并对其进行排序（使用排序算法）；然后所有等价项将是相邻的。

但这个问题是否可以比排序更高效地解决呢？ 这个问题的时间复杂度是否低于排序的时间复杂度？ 如果不是，为什么？

8个回答
12

您似乎一次提出了两个不同的问题。

1）如果只允许相等性检查，那么是否比我们有一些排序更容易进行分区？答案是不。在最坏情况下（例如全都不同），您需要Omega（n ^ 2）次比较才能确定分区。

2）如果允许排序，那么分区是否比排序更容易？答案还是不。这是因为元素唯一性问题。它说为了确定所有对象是否都不同，您需要Omega（nlogn）次比较。由于排序可以在O（nlogn）时间内完成（并且也具有Omega（nlogn）下限）并解决分区问题，因此从渐近意义上讲，它们同样困难。

如果选择任意哈希函数，则相等的对象不需要具有相同的哈希值，在这种情况下，将它们放入散列表中没有做任何有用的工作。

即使您确实想出了这样的哈希（保证相等的对象具有相同的哈希），好的哈希的时间复杂度也是期望的 O（n），最坏情况是Omega（n ^ 2）。

是否使用哈希或排序完全取决于问题中不可用的其他约束条件。

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

1
任何哈希值如果对于相等的对象不产生相等的哈希值，那么它就是有问题的。哈希函数的定义的一部分（实际上，几乎是唯一的要求）是相等的值必须产生相等的哈希值。 - supercat
@supercat：如果我们有这样的哈希表，我们是否会发布这个问题？我猜不会。对于对象上的任意相等/比较函数，想出这样的哈希表可能很困难，解决这个问题可能涉及解决分区问题。因此，仅声称哈希是一种解决方案并没有真正提供帮助。 - Aryabhatta
@reinierpost：有帮助吗？没有点赞吗？;-) 但是，如果您认为答案（不仅仅是针对此问题）是正确和有用的，那么您应该考虑点赞它，特别是当有许多被误导的答案时（一般而言，不对此问题做任何声明）。整个网站的前提是正确和有用的答案得到点赞，并且信号/噪音比高。 - Aryabhatta
2
@supercat：“任何哈希值如果对于相等的对象不能产生相等的哈希，则是有问题的。”-- 这是正确的，但在这种情况下，哈希还需要为等效的对象产生相等的哈希。等价和相等之间存在差异。“John Smith”不等于“Fred Smith”，但如果您已将等价性定义为仅考虑姓氏，则它们可能是等价的。 - Dan
2
@Dimi：甚至不知道是否存在合适的哈希函数，你就建议使用哈希去回答一个问题，该问题的标题是“分区比排序容易”！？没有人声称排序在实践中比哈希更好（我在这里重复）。如果你有一个好的哈希函数，那当然可以使用它。如果你注意到，这个问题是一个理论性的问题，而更好或更差只是指最坏情况下的复杂度。我的答案确实提到了，如果有一个好的哈希函数，哈希期望是 O(n)。如果你看到我之前链接的答案，我希望你会同意排序可能更好。 - Aryabhatta
显示剩余13条评论
6
如果你能为项目定义一个哈希函数和等价关系，那么假设计算哈希是常数时间，你应该能够在线性时间内完成分区。哈希函数必须将等效的项目映射到相同的哈希值。
如果没有哈希函数，你需要将每个要插入分区列表的新项目与每个现有列表的头进行比较。这种策略的效率取决于最终会有多少个分区。
假设你有100个项目，并且它们最终将被划分为3个列表。然后，每个项目在插入其中一个列表之前最多只需与3个其他项目进行比较。
然而，如果这100个项目最终将被划分为90个列表（即，非常少的等效项目），那就是另一回事了。现在你的运行时间更接近于二次方而不是线性。
1
将元素添加到哈希表中本质上就是这样，其中等价关系为（哈希映射到相同的桶）。你并没有简化问题。 - Anthony Williams
2
除非哈希值可以干净地映射到等价类（即相等的哈希意味着值属于同一分区），否则哈希无济于事。 - Anthony Williams
1
@supercat：没有人质疑一个好的、适用的哈希函数的好处。如果你再读一遍问题，就会清楚地看到OP想要在使用比较函数的约束条件下比较分区和排序。谈论哈希只是噪音，特别是当我们无法保证更容易找到一个好的哈希函数（我们甚至不知道OP有什么对象/比较函数）比解决分区更容易时。 - Aryabhatta
1
@Dan：是的，但是对于任意等价关系来说，定义这样一个哈希函数是问题中最难的部分。（我认为在O（n log n）的时间内不可能...并且根据等价关系的给定方式，可能会更加困难。）因此，你并没有简化问题，只是重新陈述了它（或者假设等价关系是足够琐碎的，以至于定义哈希函数是琐碎的）。 - ShreevatsaR
1
我并没有说哈希不能帮助或者不起作用，只是说设计一个哈希函数（通常来说）和解决原始的分区问题一样困难。因此，使用哈希的想法“减少”了问题，但并没有使问题变得更容易。 （顺便说一句：你的新问题主要涉及可能性而不是算法复杂度，你可能需要进行编辑。） - ShreevatsaR
显示剩余14条评论
3
如果您不关心等价集的最终排序，那么将其划分为等价集可能更快。然而，这取决于算法和每个集合中元素的数量。
如果每个集合中只有很少的项目，则可以将元素排序，然后找到相邻的相等元素。一个好的排序算法对于n个元素是O(n log n)。
如果有一些集合中有很多元素，那么您可以将每个元素与现有集合进行比较。如果它属于其中之一，则添加它，否则创建一个新集合。这将是O(n*m)，其中n是元素数，m是等价集的数目，对于大的n和小的m小于O(n log n)，但随着m趋向于n而变差。
结合排序/划分算法可能会更快。
1
使用哈希算法，这个问题几乎可以以O(N)的时间解决，尽管一个好的哈希函数可能需要足够长的计算时间，以至于一个O(NlgN)的算法可能更快。将观察到的键存储在树中并丢弃重复项将得到一个O(NlgM)的时间，其中N是元素数，而M是不同元素的数量。 - supercat
1
只有哈希函数能够标识等价类（即，不相等但等效的值具有相同的哈希）时才有效。 - Anthony Williams
2
比较排序通常具有O(n log n)的下限。
假设您遍历项目集并将它们放入相同比较值的桶中，例如在列表集合中（使用哈希集合），此操作明显为O(n)，即使从集合中检索出列表集合后也是如此。
---编辑：---
这当然需要两个假设： 1.每个要分区的元素存在一个常量时间哈希算法。 2.桶的数量不取决于输入的数量。
因此，分区的下限是O(n)。
这假设这些项有一个“getHashCode”方法可用，或者有其他方式将所有相等的项与唯一键相关联。 - Peter Recore
1
这不是O(n)，而是O(n*桶数量)。 - Anthony Williams
4
你是在说O(N)并不等同于O(N乘以某个常数)？ - wheaties
桶计数器可以是预定义的常量，也可以是运行时参数，例如条目数量。 - Anthony Williams
@Nubsis：是的，所以我的问题是，分区是否可以比O(n log n)更快地完成。 - reinierpost
显示剩余3条评论
2
如果必须使用比较器，则排序或分区的下限为Ω(n log n)个比较。原因是所有元素都必须进行Ω(n)次检查，并且比较器必须对每个元素执行log n次比较，以唯一地识别或将该元素放置在与其他元素的关系中（每个比较将空间划分为2部分，因此对于大小为n的空间，需要log n次比较）。
如果每个元素可以与在常数时间内派生的唯一键相关联，则排序和分区的下限为Ω(n)，（参见RadixSort）。
2
这不是一个很好的下界解释。排序需要Ω(n log n)比较，因为要描述n！个排列中的一个需要log（n！）= Ω(n log n)位。信息理论上，分区与排序同样困难，因为如果对手选择比较结果，好像有n个不同的分区，它可以在输入被排序之前随时改变主意，将两个顺序未知的相邻元素放入一个分区中。 - user382751
我想从直觉的角度出发。例如，将n个项添加到自平衡树或跳表中进行比较。然后需要n log n次比较，结果是一个排序的集合。鉴于分区可以重新构建为排序问题，因此分区肯定不比排序更难，复杂性取决于如何比较项目，无论是通过哈希还是比较。鉴于基数排序的下限是线性的，那么在这种情况下，分区的效率不可能比基数排序更高。 - mdma
@mdma：在谈到下界时，请使用Omega而不是bigOh。 - Aryabhatta
当然，我不确定如何格式化它。我将从上面的评论中粘贴漂亮的欧米茄符号。 - mdma
@mdma：你总是可以使用Omega :-) 我希望这里有一些类似于LaTeX的支持。 - Aryabhatta
@user382751，你的回答实际上就是我在寻找的答案！但其他的回答和评论也是非常有帮助的补充。我喜欢这个网站... - reinierpost
1

通常情况下，分区比排序更快，因为您无需将每个元素与每个可能相等的已排序元素进行比较，而只需要将其与您的分区的已建立键进行比较。仔细研究一下基数排序。 基数排序的第一步是基于密钥的某个部分对输入进行分区。基数排序的时间复杂度为O(kN)。如果您的数据集的密钥受到给定长度k的限制，则可以将基数排序设置为O(n)。如果您的数据是可比较的并且没有有界的键，但您选择了一个用于分区集合的有界键，则排序集合的复杂度为O(n log n)，而分区的复杂度为O(n)。

除了 Big-O 外，应注意选择关键字对于特定数据集的分区或基数排序速度会产生很大影响。此外，具有少量等效元素的集合将倾向于排序，而具有许多等效元素的集合将倾向于分区。 - Eric Mickelsen
对哈希进行基数排序（本质上是通过递归地将数据散列到桶中得到的）比在典型键上进行基数排序要快得多，因为分布会更好。具有256个桶的典型基数排序场景可能会导致某些桶包含输入记录的10％或更多；而具有256个桶的哈希基数排序很不可能出现一个桶包含超过1-2％的输入记录，除非超过1％的输入记录具有相同的键。 - supercat
@supercat：如果只有256个箱子的哈希表，除了小数据集外，它会有非常高的哈希冲突率，从而抵消更均匀分布的好处。我不确定是否真的存在“哈希基数排序”。你能提供一个支持你说法的参考吗？ - Eric Mickelsen
数字256是任意的；我的观点是，基于哈希函数将项目划分到箱子中，将导致所有箱子的填充更加均匀，而不是使用典型的基数排序函数将它们划分到箱子中。我不知道是否存在所谓的“哈希基数排序”，但可以像其他任何东西一样在哈希函数的输出上使用基数排序。 - supercat
1
比排序更容易吗？ - reinierpost
0
使用哈希函数执行可能不完美的分区所需的时间将为O(n+bucketcount) [而不是O(n*bucketcount)]。使桶计数足够大以避免所有冲突将是昂贵的，但如果哈希函数工作得很好，每个桶中应该只有少量不同的值。如果可以轻松生成多个统计独立的哈希函数，则可以取出每个键不全匹配第一个键的桶，并使用另一个哈希函数来分割该桶的内容。
假设每个步骤上的桶数量恒定，时间将为O(NlgN)，但如果将桶数量设置为sqrt(N)之类的值，则平均通过次数应为O(1)，每次通过的工作量为O(n)。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接