是否有任何比O(n log n)运行得更快的通用元素的实用算法(与计数排序或桶排序不同)?通用实用的排序算法比O(n log n)快吗?
回答
很多人都提到了比较排序算法的信息论Ω(n lg n),这些算法在比较排序时不能被破解。 (This earlier question探讨了为什么是这种情况。)
但是,有一些类型的比较排序,虽然在平均情况下不会破坏O(n lg n),但可以显示在已预分类的输入上运行得更快在某种程度上。例如,Dijkstra的smoothsort运行在O(n)上,已经排序的输入中有O(n lg n)的最坏情况行为。我最喜欢的排序之一,Cartesian tree sort,在一些指标中可以最大限度地利用预分类。例如,它可以在时间O(n)中对具有恒定数量的增加或减少的子序列的任何序列进行排序,在最坏的情况下优雅地降级为O(n lg n)。
关于非比较排序的主题,有一些着名但棘手的排序算法整数超过O(n lg n)通过做聪明的位操作技巧。最有名的整数排序算法是一种随机算法,可以在O(n lg lg n)中排序,而用于整数排序的最快确定性算法以O(n lg lg n)时间运行。您可能已经听说过基数排序在O(n)中工作,尽管技术上它是O(n lg U),其中U是要排序的数组中最大的值。简而言之,不,你不能比O(n lg n)做得更好,但是如果你知道一些关于你的输入的信息,你可以稍微做的更好一些。
对于只能比较而不访问内部元素的通用元素,不可能有比Theta(n log n)更快的排序算法。那是因为有n! (n阶乘)元素的可能顺序,并且您需要Theta(n log n)比较来区分所有元素。
有多少元素?尽管它类似于N 1.2,但Shell-Metzner排序通常比其他多数其他元素(几千个元素)要快。
这也取决于你的意思是“通用”和“实用”。基数排序可以击败O(n log n),并且它适用于相当广泛的各种数据(但绝对不是所有的)。
如果你的想法是实用的和通用的,将算法限制为直接比较元素的算法,那么无 - 无(或永远不会)比O(n log n)更好。这已经证明了相当长的一段时间。
不是。这是我们拥有的少数几个严格的最小界限之一。对于n个元素的集合,有n!不同的顺序,所以要指定一个给定的顺序,我们需要log(n!)位。通过斯特林近似,这大约是n log n。对于我们在元素之间进行的每一次比较,我们基本上得到了一点信息(忽略了相同元素的可能性)。
- 1. floor(√2n)的O(log log n)算法?
- 2. 比O(log N)int set set实现在Java中快吗?
- 3. 快速排序中位数在O(n log n)
- 4. 是log(n!)= O((log(n))^ 2)?
- 5. O(n)排序算法可能吗?
- 6. 如何计算O(Log(N))?
- 7. 你能比O(log n)获得10的幂更快吗?
- 8. 与log(n)相比,log(n^2)的大O是什么?
- 9. 大O符号 - O(n日志(N))对O(的log(n^2))
- 10. 显示n^2不是O(n * log(n))?
- 11. 为什么排序字符串O(n log n)?
- 12. 排序在最坏情况下O(n * log(n))
- 13. O(N)查找,但O(日志(N))的比较排序列表
- 14. 快速带O的最坏的情况下(N log n)的
- 15. 你如何看出O(log n)和O(n log n)之间的差异?
- 16. 时间复杂度O(N日志(log n)的)+ N O(L)
- 17. 为O(n^log n)的碰撞检测
- 18. 算法复杂度,log^k n vs n log n
- 19. 时间复杂度 - O(n^2)到O(n log n)搜索
- 20. 为什么此循环返回值为O(n log log n)而不是O(n log n)?
- 21. 图形搜索O(log(N)(N + M)
- 22. heapify O(n)算法
- 23. log(n!)=Ω(n * log(n))?
- 24. 增长率log(log * n)和log *(log n)哪个更快?
- 25. 我可以说Θ(n^3/2)时间算法渐近地比Θ(n log n)时间算法慢吗?
- 26. 在k <n的算法运行时log(n)vs log(k)
- 27. 使用Prim算法从O(n^3)到O(n^2)优化MST
- 28. O(n Log n)是多项式时间吗?
- 29. N ++的C++算法!排序
- 30. n!实现以n^100为log N
以O(n√lg lg n)运行的整数排序算法的名称是什么? – 2017-11-15 08:51:01