rei*_*ost 20 sorting algorithm partitioning time-complexity
这个问题一直困扰着我的脑海......
假设我有一个项目列表和它们的等价关系,并且比较两个项目需要恒定的时间.我想返回项目的分区,例如链接列表列表,每个列表包含所有等效项目.
这样做的一种方法是将等价扩展到项目的排序并对它们进行排序(使用排序算法); 那么所有等价物品都会相邻.
但它可以比排序更有效地完成吗？这个问题的时间复杂度是否低于排序？如果没有,为什么不呢？
小智 12
你似乎一口气问两个不同的问题.
1)如果只允许相等检查,它是否比我们有一些排序更容易分区？答案是不.您需要Omega(n ^ 2)比较来确定最坏情况下的分区(例如,所有不同).
2)如果允许排序,分区是否比排序更容易？答案是否定的.这是因为元素差别问题.其中说,为了确定所有对象是否都是不同的,您需要进行Omega(nlogn)比较.由于排序可以在O(nlogn)时间内完成(并且还具有Omega(nlogn)下界)并且解决了分区问题,渐近它们同样很难.
如果选择任意哈希函数,则相等的对象不需要具有相同的哈希值,在这种情况下,通过将它们放入哈希表中,您没有做任何有用的工作.
即使你确实提出了这样的哈希(相同的对象保证具有相同的哈希值),时间复杂度预期为好的哈希值O(n),最坏的情况是Omega(n ^ 2).
是否完全使用散列或排序取决于问题中不可用的其他约束.
其他答案似乎也忘记了你的问题(主要)是关于比较分区和排序!
如果您可以为项目定义哈希函数以及等价关系,那么您应该能够在线性时间内进行分区 - 假设计算哈希是恒定时间.哈希函数必须将等效项映射到相同的哈希值.
如果没有哈希函数,则必须将要插入分区列表的每个新项目与每个现有列表的头部进行比较.该策略的效率取决于最终将有多少分区.
假设您有100个项目,最终将它们划分为3个列表.然后,在将其插入其中一个列表之前,必须将每个项目与最多3个其他项目进行比较.
但是,如果这100个项目最终将被划分为90个列表(即,很少有相同的项目),那么这是一个不同的故事.现在你的运行时更接近二次而不是线性.