你能排序的n O（n）的整数摊销的复杂性？ [英] Can you sort n integers in O(n) amortized complexity?

问题描述

这是理论上的可能，以n个整数数组排序为O（n）？

Is it theoretically possible to sort an array of n integers in an amortized complexity of O(n)?

有关试图创建的O（n）的复杂性最坏的情况是什么？

What about trying to create a worst case of O(n) complexity?

目前，大多数的算法是建立在O（nlogn）平均+ O（N ^ 2）最坏的情况。 有些人，而使用更多的内存为O（nlogn）最坏的。

Most of the algorithms today are built on O(nlogn) average + O(n^2) worst case. Some, while using more memory are O(nlogn) worst.

您对内存的使用没有限制，可以创建这样的算法？ 如果你的记忆是有限的？这将如何伤害你的算法？

Can you with no limitation on memory usage create such an algorithm? What if your memory is limited? how will this hurt your algorithm?

推荐答案

在与基于比较的排序的会告诉你的，你的不能排序比为O（n LG N）更快比较排序。也就是说，如果你的排序算法决定的顺序通过比较两个元素互相反对，你不能这样做比这更好的。例子包括快速排序，冒泡排序，归并。

Any page on the intertubes that deals with comparison-based sorts will tell you that you cannot sort faster than O(n lg n) with comparison sorts. That is, if your sorting algorithm decides the order by comparing 2 elements against each other, you cannot do better than that. Examples include quicksort, bubblesort, mergesort.

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

Some algorithms, like count sort or bucket sort or radix sort do not use comparisons. Instead, they rely on the properties of the data itself, like the range of values in the data or the size of the data value.

这些算法可能有更快的复杂性。下面是一个示例场景：

Those algorithms might have faster complexities. Here is an example scenario:

正在整理 10 ^ 6 整数，每个整数之间 0 和 10 。然后，你可以指望零，那些，三三两两，数量等，并吐回了排序顺序。这是countsort如何工作的，在 O（N + M），其中 M 是值的数据可以采取数量（在这种情况下，米= 11 ）。

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).

另：

正在整理 10 ^ 6 二进制字符串，都处于最 5 字符的长度。您可以使用基数排序为：首先根据自己的第一个字符分割成2桶，然后基数排序他们的第二个字符，第三，第四和第五。只要每一步都是一个稳定的排序，你应该结束了一个完美的排序列表中的 O（NM），其中M是在你的数据位数或比特数（在这种情况下，米= 5 ）。

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）可靠（使用比较排序）。

But in the general case, you cannot sort faster than O(n lg n) reliably (using a comparison sort).

这篇关于你能排序的n O（n）的整数摊销的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！