Yuu*_*shi 11
这取决于.如果你能以某种方式既具有下限和上限(和最大精度/值长度)的约束你的输入,那么你可以使用一个基数排序是O(n).类似地,Bucket SortO(n)在最佳情况下可能具有复杂性,但O(n^2)对于不良输入会降级.
但是,一般情况下,如果您无法限制输入并需要使用基于比较的排序,则可以证明这O(n log n)是最佳的.
在对固定精度整数或浮点数(通常最多64位)进行排序时,这些值实际上是有界的,并且可以进行基数排序.
即使值的最大位长有界,位长越长,常数越大.实际上,如果存在要排序的n值,并且每个值可以具有高达m位的长度或精度,则算法复杂度为O(nm).
| 归档时间： |
|
| 查看次数： |
11814 次 |
| 最近记录： |