D*******a
发帖数: 3688 | 1 radix sort号称是O(N)的排序，小弟有点不明白
假如排1~9999，那么需要排4遍，每遍是N次运算
排1～99999，那么需要5遍
如果排1～N，那么应该是需要Nlog10(N)遍才对啊
为什么得出O(N)的结论？ | l******t
发帖数: 108 | 2 这个复杂度分析是基于random-access machine (RAM) model的,
可以有无限个随机存储单元, 每个单元可以存放无限大的值
【在 D*******a 的大作中提到】
: radix sort号称是O(N)的排序，小弟有点不明白
: 假如排1~9999，那么需要排4遍，每遍是N次运算
: 排1～99999，那么需要5遍
: 如果排1～N，那么应该是需要Nlog10(N)遍才对啊
: 为什么得出O(N)的结论？
| y***u
发帖数: 101 | 3 radix sort 在ram model下还是O(n log n)啊，只不过一般人说机器
的word size是fixed，所以O(n)，其实不严格。RAM model下认为一个
word有O(log n)个bit。
不过在RAM model下的确是可以在小于O(n log n)时间内完成排序的。
【在 l******t 的大作中提到】
: 这个复杂度分析是基于random-access machine (RAM) model的,
: 可以有无限个随机存储单元, 每个单元可以存放无限大的值
|
|
