algorithm - 你能以 O(n) 的摊销复杂度对 n 个整数进行排序吗？

Question

理论上是否有可能以 O(n) 的摊销复杂度对 n 个整数数组进行排序？

如何尝试创建复杂度为 O(n) 的最坏情况？

当今的大多数算法都建立在 O(nlogn) 平均 + O(n^2) 最坏情况的基础上。有些，虽然使用更多内存，但 O(nlogn) 最差。

你能在不限制内存使用的情况下创建这样的算法吗？如果你的内存力有限怎么办？这将如何损害您的算法？

Answer 1

intertubes 上处理基于比较的排序的任何页面 will tell you使用比较排序，您不能排序比 O(n lg n) 更快。也就是说，如果您的排序算法通过将 2 个元素相互比较来决定顺序，那么您不能做得更好。示例包括快速排序、冒泡排序、归并排序。

一些算法，如计数排序、桶排序或基数排序不使用比较。相反，它们依赖于数据本身的属性，例如数据中值的范围或数据值的大小。

那些算法可能具有更快的复杂性。这是一个示例场景:

You are sorting 10^6 integers, and each integer is between 0 and 10. 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, in O(n + m) where m 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 most 5 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 in O(nm), where m is the number of digits or bits in your datum (in this case, m=5).

但在一般情况下，您无法可靠地(使用比较排序)比 O(n lg n) 更快地进行排序。