理论上是否可以以 O(n) 的摊余复杂度对 n 个整数的数组进行排序?
尝试创建 O(n) 复杂度的最坏情况怎么样?
现在的大多数算法都是建立在平均 O(nlogn) + 最坏情况 O(n^2) 之上。
有些虽然使用更多内存,但最糟糕的是 O(nlogn)。
你能在不限制内存使用的情况下创建这样的算法吗?
如果你的记忆力有限怎么办?这会对你的算法造成什么影响?
intertubes 上处理基于比较的排序的任何页面会告诉你那你cannot排序速度快于O(n lg n)
通过比较排序。也就是说,如果您的排序算法通过比较 2 个元素来决定顺序,那么您就不能做得更好了。示例包括快速排序、冒泡排序、合并排序。
某些算法(例如计数排序、桶排序或基数排序)不使用比较。相反,它们依赖于数据本身的属性,例如数据中值的范围或数据值的大小。
那些算法might具有更快的复杂性。这是一个示例场景:
你正在排序10^6
整数,并且每个整数都在0
and 10
。然后你可以数出零、一、二等的数量,然后按排序顺序将它们吐出来。这就是 countsort 的工作原理,在O(n + m)
where m
是您的数据可以采用的值的数量(在本例中,m=11
).
Another:
你正在排序10^6
最多全部为二进制字符串5
字符长度。您可以使用基数排序:首先根据第一个字符将它们分成 2 个桶,然后对第二个字符、第三个、第四个和第五个字符进行基数排序。只要每一步都是稳定排序,您最终应该得到一个完美排序的列表O(nm)
,其中 m 是数据中的位数或位数(在本例中,m=5
).
但在一般情况下,排序速度不能比O(n lg n)
可靠地(使用比较排序)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)