分区比排序容易吗?

你好像一次问了两个不同的问题。到这儿来。

1)如果只允许相等性检查,它是否比我们有一些排序更容易进行分区?答案是,不是。你需要欧米伽(n^2)比较来确定最坏情况下的分区(例如,所有的分区都不同)。

2)如果允许排序,分区是否比排序更容易?答案又是否定的,这是因为 Element Distinctness Problem . 也就是说,为了确定所有对象是否都是不同的,您需要进行omega(nlogn)比较。由于排序可以在O(nlogn)时间内完成(也有ω(nlogn)下界),并且解决了分区问题,因此渐进地,它们同样困难。

如果您选择一个任意的散列函数,那么相等的对象不需要具有相同的散列,在这种情况下,您没有通过将它们放入散列表来完成任何有用的工作。

即使您确实提出了这样的哈希(保证具有相同哈希的相等对象),时间复杂性也是 预期 O(n)代表好哈希,最坏的情况是欧米茄(n^2)。

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

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

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

如果没有哈希函数,则必须将要插入分区列表的每个新项与每个现有列表的头进行比较。该策略的效率取决于最终会有多少分区。

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

然而,如果这100个项目最终被划分成90个列表(即几乎没有等价的项目),情况就不同了。现在你的运行时间更接近二次方而不是线性。

如果您不关心等价集的最终顺序,那么划分为等价集可能会更快。然而,它取决于算法和每个集合中元素的数量。

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

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

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

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

如果每个元素都可以与一个在恒定时间内派生的唯一键相关联,那么低位键是(n),用于对蚂蚁分区(c.f)进行排序。 RadixSort )

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

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

--- 编辑: ---

当然,这需要两个假设:

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

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

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

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

使用哈希函数执行可能不完美的分区所需的时间为o(n+bucketcount)[不是o(n*bucketcount)]。使bucket的数量足够大以避免所有的冲突是很昂贵的,但是如果hash函数运行良好,那么每个bucket中应该有少量不同的值。如果可以轻松生成多个统计独立的散列函数,则可以获取键不完全匹配第一个散列函数的每个存储桶,并使用另一个散列函数对该存储桶的内容进行分区。

假设每个步骤上的存储桶数为常量,则时间将为o(nlgn),但如果将存储桶数设置为sqrt(n)之类的值,则平均通过次数应为o(1),每个通过次数中的功应为o(n)。