理论上是否有可能以 O(n) 的摊销复杂度对 n 个整数数组进行排序?
如何尝试创建复杂度为 O(n) 的最坏情况?
当今的大多数算法都建立在 O(nlogn) 平均 + O(n^2) 最坏情况的基础上。 有些,虽然使用更多内存,但 O(nlogn) 最差。
你能在不限制内存使用的情况下创建这样的算法吗? 如果你的内存力有限怎么办?这将如何损害您的算法?
最佳答案
intertubes 上处理基于比较的排序的任何页面 will tell you使用比较排序,您不能排序比 O(n lg n)
更快。也就是说,如果您的排序算法通过将 2 个元素相互比较来决定顺序,那么您不能做得更好。示例包括快速排序、冒泡排序、归并排序。
一些算法,如计数排序、桶排序或基数排序不使用比较。相反,它们依赖于数据本身的属性,例如数据中值的范围或数据值的大小。
那些算法可能具有更快的复杂性。这是一个示例场景:
You are sorting
10^6
integers, and each integer is between0
and10
. Then you can just count the number of zeros, ones, twos, etc. and spit them back out in sorted order. That is how countsort works, inO(n + m)
wherem
is the number of values your datum can take (in this case,m=11
).
另一个:
You are sorting
10^6
binary strings that are all at most5
characters in length. You can use the radix sort for that: first split them into 2 buckets depending on their first character, then radix-sort them for the second character, third, fourth and fifth. As long as each step is a stable sort, you should end up with a perfectly sorted list inO(nm)
, where m is the number of digits or bits in your datum (in this case,m=5
).
但在一般情况下,您无法可靠地(使用比较排序)比 O(n lg n)
更快地进行排序。
关于algorithm - 你能以 O(n) 的摊销复杂度对 n 个整数进行排序吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6121868/