Rya*_*mos 26 sorting algorithm performance big-o lower-bound
我写了一个简单的程序,在O(n)中排序.它的内存效率很低,但这不是重点.
它使用了背后的原理HashMap进行排序:
public class NLogNBreak {
public static class LinkedListBack {
public LinkedListBack(int val){
first = new Node();
first.val = val;
}
public Node first = null;
public void insert(int i){
Node n = new Node();
n.val = i;
n.next = first;
first = n;
}
}
private static class Node {
public Node next = null;
public int val;
}
//max > in[i] > 0
public static LinkedListBack[] sorted(int[] in, int max){
LinkedListBack[] ar = new LinkedListBack[max + 1];
for (int i = 0; i < in.length; i++) {
int val = in[i];
if(ar[val] == null){
ar[val] = new LinkedListBack(val);
} else {
ar[val].insert(val);
}
}
return ar;
}
}
那么这算是一种O(n),即使它以一种时髦的格式返回结果呢？
tem*_*def 146
直接回答你的问题:
那么这个Ω(n log n)障碍是什么？它从何而来？你怎么打破它？
Ω(n log n)势垒是任何基于比较的排序算法的平均情况速度的信息理论下界.如果允许您应用于数组元素以区分它们的唯一操作是执行某种比较,那么在平均情况下,排序算法不能比Ω(n log n)做得更好.
为了理解这是为什么,让我们考虑算法在执行过程中的任何时刻的状态.在算法运行时,它可以获得有关输入元素的排序方式的一些信息.假设如果算法具有关于输入元素的原始排序的一组信息X,则算法处于状态X.
Ω(n log n)参数的关键(以及几个相关的参数,我稍后会讨论)是算法必须能够根据输入进入大量不同的状态.我们现在假设排序算法的输入是n个不同值的数组.因为算法无法告诉除了它们的排序方式之外的任何元素,所以排序的值并不重要.重要的是这些n个元素相对于彼此的相对排序.
现在关键步骤 - 让我们假设有f(n)个唯一的方法来排序n个输入元素,并假设我们的排序算法不能进入至少f(n)个不同的状态.如果是这种情况,那么数组中的元素必须有两种不同的排序,算法总是将它们组合在一起形成相同的状态.如果发生这种情况,那么排序算法可能无法正确地对两个输入数组进行正确排序.这背后的原因是因为算法以相同的方式处理两个数组,所以用于重新排序第一个数组的元素的步骤将与它用于重新排序第二个数组的元素的步骤相同.由于两个数组不相同,因此必须至少有一个元素在两种情况之一中不合适.因此,我们知道排序算法必须能够进入f(n)个不同的状态.
但算法如何进入这些不同的状态？好吧,让我们考虑一下.最初,该算法根本没有关于元素排序的信息.当它进行第一次比较时(例如,在元素A [i]和A [j]之间),算法可以进入两种状态之一 - 一种是A [i] <A [j],另一种是A [i] > A [j].更一般地,在最佳情况下,算法进行的每次比较都可以基于比较结果将算法置于两个新状态之一中.因此,我们可以想到一个大的二叉树结构,描述算法可以处于的状态 - 每个状态最多有两个子节点,根据所做的比较结果描述算法进入的状态.如果我们从树的根到叶子采取任何路径,我们得到一系列的比较,最终由算法在特定输入上进行.为了尽可能快地排序,我们希望尽可能少地进行比较,因此我们希望这种树结构具有尽可能小的高度.
现在,我们知道两件事.首先,我们可以考虑算法可以作为二叉树进入的所有状态.其次,该二叉树必须至少具有f(n)个不同的节点.鉴于此,我们可以构建的最小二叉树必须具有至少Ω的高度(log f(n)).这意味着如果存在f(n)不同的排序数组元素的可能方式,我们必须至少进行Ω(log f(n))比较,否则我们无法进入足够不同的状态.
为了得出你不能击败Ω(n log n)的证明,请注意,如果数组中有n个不同的元素,那么就有n!订购元素的不同可能方式.使用斯特林的近似值,我们得到了log n!=Ω(n log n),因此我们必须在平均情况下至少进行Ω(n log n)次比较以对输入序列进行排序.
在我们刚刚看到的内容中,我们看到如果你有n个数组元素都是不同的,你不能用比Ω(n log n)更快的比较排序对它们进行排序.但是,这个开始的假设不一定有效.我们想要排序的许多数组可能包含重复的元素.例如,假设我想要排序仅由零和1组成的数组,例如此数组:
0 1 0 1 1 1 0 0 1 1 1
在这种情况下,有n 是不正确的!不同的零数组和长度为n的数组.事实上,它们只有2 个.从上面的结果来看,这意味着我们应该能够使用纯粹的基于比较的排序算法对Ω(log 2 n)=Ω(n)时间进行排序.事实上,我们绝对可以做到这一点; 这是我们如何做到的草图:
要看到这是有效的,如果0是我们的第一个元素,那么'less'数组将为空,'equal'数组将包含所有零,而'greater'数组将具有所有的数组.然后连接它们然后将所有零置于所有零之前.否则,如果1是我们的第一个元素,那么less数组将保存零,equal数组将保存1,greater数组将为空.因此,根据需要,它们的串联全部为零,后面跟着所有的串联.
实际上,您不会使用此算法(您将使用计数排序,如下所述),但它表明如果可能的输入数量,您确实可以使用基于比较的算法击败Ω(n log n)算法很小.
已知一些基于比较的排序算法在具有多个重复值的输入上非常快速地工作.例如,众所周知,具有特殊分区步骤的Quicksort可以利用输入数组中的重复元素.
所有这些讨论都假设我们讨论的是基于比较的排序,其中对数组元素唯一允许的操作是比较.但是,如果我们更多地了解我们将要排序的元素,并且可以在简单比较之外对这些元素执行操作,那么上述任何一个边界都不再存在.我们正在打破导致我们构造算法所有状态的二叉树的起始假设,因此没有理由怀疑这些边界仍然存在.
例如,如果您知道输入值是从仅具有| U |的Universe中提取的 在其中的元素,然后您可以使用聪明的算法在O(n + | U |)时间内排序.首先创建| U | 我们可以将原始数组中的元素放入其中的不同桶.然后,遍历数组并将所有数组元素分发到相应的存储桶中.最后,访问每个桶,从存放最小元素副本的存储桶开始,最后用包含最大元素副本的存储桶结束,然后将所有找到的值连接在一起.例如,让我们看看如何对包含值1 - 5的数组进行排序.如果我们有这个起始数组:
1 3 4 5 2 3 2 1 4 3 5
然后我们可以将这些元素放入这样的桶中:
Bucket 1 2 3 4 5
-------------
1 2 3 4 5
1 2 3 4 5
3
迭代桶并将它们的值连接在一起产生这样:
1 1 2 2 3 3 3 4 4 5 5
这当然是我们原始数组的排序版本!这里的运行时间为O(n)时间并将原始数组元素分配到存储桶中,然后O(n + | U |)时间迭代所有存储桶,将元素重新组合在一起.请注意,如果| U | = O(n),这在O(n)时间内运行,打破了Ω(n log n)排序障碍.
如果要对整数进行排序,则可以使用基数排序(在O(n lg | U |)中运行)做得比这更好.如果你正在处理原始ints,lg | U | 通常是32或64,所以这是非常快的.如果你愿意实现一个特别棘手的数据结构,你可以使用van Emde Boas Tree在时间O(n lg lg U)中对从0到U - 1的整数进行排序,再次利用整数由组组成的事实可以在块中操作的位数.
类似地,如果你知道你的元素是字符串,你可以通过从字符串中构建一个trie来快速排序,然后在trie中迭代以重建所有字符串.或者,您可以将字符串视为以大型基础编写的数字(例如,ASCII文本的基数128),然后使用上面的整数排序算法之一.
在每一种情况下,你可以击败信息理论障碍的原因是你打破了障碍的开始假设,即你只能应用比较.如果您可以将输入元素视为数字,或作为字符串,或者显示更多结构的任何其他内容,则所有投注均已关闭,您可以非常有效地进行排序.
希望这可以帮助!
这被称为Radix Sort,是的它打破了nlog(n)障碍,这只是障碍Comparison Model.在比较模型链接的维基百科页面上,您可以看到使用它的排序列表,以及一些不使用它的排序.
Radix排序通过将每个元素放在一个桶中,根据它的值进行排序,然后在最后再将所有桶连接在一起.它仅适用于具有有限数量的可能值的整数类型.
通常,基数排序一次完成一个字节或半字节,以减少桶的数量.请参阅维基百科上的文章,或搜索更多信息.
您也可以对负数进行排序,并仅为其用于改进的桶分配内存.