大多数排序算法都具有O(N N)或O(N logN)的复杂度来实现结果.但是,对于特定的输入集合,存在具有O(N)复杂度的算法.我想知道是否有一种可用的排序算法,在所有情况下都具有O(N)的复杂度.
如果你只能比较(检查两个项是<,>,==)正在排序的值,那么你不能做得比O(n log(n))更好.它是少数几种经过验证的算法下界之一.证明不是太复杂(详情请查看维基百科上的比较排序),但它足够长,不能在此重复.
如果你可以做比较以外的事情你有更多的灵活性.如果你有数字,你可以检查存储桶排序(一种基数排序),它可以进行O(n)排序.
| 归档时间： |
|
| 查看次数： |
80 次 |
| 最近记录： |