有没有排序的时间复杂度为O(n)的算法

主题：有没有排序的时间复杂度为O(n)的算法

shuiqingyangliu [专家分：0] 发布于 2007-01-08 18:17:00

排序的时间复杂度最低为O(nlogn),那有没有比它还快的

沙发

雪光风剑 [专家分：27190] 发布于 2007-01-08 18:46:00

不可能有的
问题本身有时间要求下限

板凳

boxertony [专家分：23030] 发布于 2007-01-09 09:48:00

分配排序法的时间复杂度类似于O(n)，在某些情况下会比O(nlogn)快。

3 楼

雪光风剑 [专家分：27190] 发布于 2007-01-09 10:00:00

[quote]分配排序法的时间复杂度类似于O(n)，在某些情况下会比O(nlogn)快。[/quote]
那需要特定次序
整体算法不可能低过时间限吧

4 楼

argentmoon [专家分：13260] 发布于 2007-01-09 12:00:00

O(N)排序法很多，只是都带有一个系数，而且应用都有各自的局限性，还有排序下界不是nlog(n)吧？

5 楼

雪光风剑 [专家分：27190] 发布于 2007-01-09 13:17:00

[quote]O(N)排序法很多，只是都带有一个系数，而且应用都有各自的局限性，还有排序下界不是nlog(n)吧？[/quote]
通用的排序算法下界不是nlog(n)么？

6 楼

DFDer [专家分：70] 发布于 2007-01-09 20:41:00

基于比较的排序的下限是nlog(n)

7 楼

argentmoon [专家分：13260] 发布于 2007-01-15 18:15:00

[quote][quote]O(N)排序法很多，只是都带有一个系数，而且应用都有各自的局限性，还有排序下界不是nlog(n)吧？[/quote]
通用的排序算法下界不是nlog(n)么？[/quote]

什么叫通用排序算法？什么叫通用排序算法的下界？

一般的数据结构书上都会介绍O（N）的排序

8 楼

argentmoon [专家分：13260] 发布于 2007-01-15 18:17:00

确切地说，是基于比较的排序算法下界是nlog(n)，但还有些是不基于比较的排序算法

您尚未登录，请登录后再回复。点此登录或注册