Vad*_*klk 8 algorithm complexity-theory big-o
从理论上讲,在O(n)的摊销复杂度中对n个整数的数组进行排序是否可行？
那么试图创建O(n)复杂性的最坏情况呢？
今天的大多数算法都建立在O(nlogn)平均值+ O(n ^ 2)最坏的情况下.一些,虽然使用更多的内存是O(nlogn)最差.
您是否可以对内存使用没有限制来创建这样的算法？如果你的记忆力有限怎么办？这将如何伤害你的算法？
evg*_*eny 11
对基于比较的排序交易的intertubes任何页面会告诉你,你不能比速度排序O(n lg n)与比较排序.也就是说,如果您的排序算法通过将2个元素相互比较来确定顺序,那么您不能做得更好.示例包括quicksort,bubblesort,mergesort.
某些算法(如计数排序或存储桶排序或基数排序)不使用比较.相反,它们依赖于数据本身的属性,例如数据中的值范围或数据值的大小.
这些算法可能具有更快的复杂性.以下是一个示例场景:
您正在排序
10^6整数,每个整数在0和之间10.然后你可以只计算零,一,二等的数量,并按排序顺序吐出它们.这就是countort的工作原理,在O(n + m)哪里m是你的数据可以采用的值的数量(在这种情况下m=11).
另一个:
您正在排序长度
10^6最多为5字符的二进制字符串.您可以使用基数排序:首先根据它们的第一个字符将它们分成2个桶,然后对第二个字符,第三个,第四个和第五个字符进行基数排序.只要每个步骤都是一个稳定的排序,你应该得到一个完美排序的列表O(nm),其中m是你的数据中的数字或位数(在这种情况下m=5).
但在一般情况下,您不能比O(n lg n)可靠地排序更快(使用比较排序).