cfi*_*her 9 sorting algorithm big-o computer-science
是否存在比O(n log n)运行得更快的通用元素(与计数排序或桶排序不同)的实用算法？
tem*_*def 25
许多人已经提到了在比较排序算法上绑定的信息理论Ω(n lg n),这种算法不能在比较排序中被打破.(这个早先的问题探讨了为什么会这样.)
但是,有一些类型的比较排序,虽然在平均情况下不破坏O(n lg n),但可以显示在已经在某种程度上预先排序的输入上运行得更快.例如,Dijkstra的smoothsort在已经排序的输入上以O(n)运行,具有O(n lg n)最坏情况行为.我最喜欢的一种,笛卡尔树排序,可以在一些指标中最佳地利用预先排序.例如,它可以在时间O(n)中对具有恒定数量的递增或递减子序列的任何序列进行排序,在最坏的情况下优雅地降级为O(n lg n).
关于非比较排序的主题,有一些着名但棘手的整数排序算法超过O(n lg n)bynp做巧妙的位操作技巧.最着名的整数排序算法是一种可以在O(n√lglgn)中排序的随机算法,而用于整数排序的最快确定性算法在O(n lg lg n)时间内运行.您可能听说过基数排序在O(n)中工作,虽然从技术上来说它是O(n lg U),其中U是要排序的数组中的最大值.
简而言之,不,你不能比O(n lg n)做得更好,但如果你对输入有所了解,你可以做得更好.