这是一个在我脑海里徘徊了一段时间的问题……
假设我有一个项目列表和它们的等价关系，并且比较两个项目需要恒定的时间。
我想退回一部分物品，例如链表的列表，每个链表包含所有等效项。
实现此目的的一种方法是将等价性扩展到项目的排序并对其进行排序（使用排序算法）；那么所有等价的项目将是相邻的。
但它能比排序更有效吗？这个问题的时间复杂度是不是比排序低？如果没有，为什么不呢？
您似乎在这里同时问两个不同的问题。
1）如果只允许相等性检查，是否比我们进行一些排序更容易分区？答案是不。您需要 Omega(n^2) 比较来确定最坏情况下的分区（例如，所有情况都不同）。
2）如果允许排序，分区是否比排序更容易？答案再次是否定的。这是因为元素独特性问题 http://en.wikipedia.org/wiki/Element_uniqueness_problem。也就是说，为了确定所有对象是否不同，您需要 Omega(nlogn) 比较。由于排序可以在 O(nlogn) 时间内完成（并且也有 Omega(nlogn) 下界）并解决分区问题，因此渐近地它们同样困难。
如果您选择任意哈希函数，则相等的对象不需要具有相同的哈希值，在这种情况下，您没有通过将它们放入哈希表来完成任何有用的工作。
即使你确实想出了这样的哈希（相同的对象保证具有相同的哈希），时间复杂度也是expectedO(n) 表示好的哈希值，最坏情况是 Omega(n^2)。
是否使用散列或排序完全取决于问题中不可用的其他约束。
其他答案似乎也忘记了您的问题（主要）是关于比较分区和排序！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
