h*********e
发帖数: 56 | 1 How to sort N integers ranging from 0 to N^3, in O(N) time. |
g*****u
发帖数: 298 | 2 bitmap？也不是很好了，因为非常稀疏。可是别的方法都没有O(n)啊。呼唤好方法。。
。 |
h*********e
发帖数: 56 | 3 bitmap有两个问题：
1，元素可能重复，
2，空间O（N^3)，所以时间也是O(N^3)。这么说来counting sort也不能达到O(N)。 |
g*******y
发帖数: 1930 | 4 radix sort
每个数x可以表示为 {i,j,k} x=i*n^2 + j*n + k; |
h*********e
发帖数: 56 | |
d****i
发帖数: 4354 | 6 把数分解成i*n^2 + j*n + k要花不少时间吧？不如n^3有多少位就用多少位的radix呢？
【在 g*******y 的大作中提到】
: radix sort
: 每个数x可以表示为 {i,j,k} x=i*n^2 + j*n + k;
|
h*********e
发帖数: 56 | 7 In that way, the number of digits will be O(lgN), instead of a constant 3;
and the time complexity of the radix sort depends on that.
呢？
【在 d****i 的大作中提到】
: 把数分解成i*n^2 + j*n + k要花不少时间吧？不如n^3有多少位就用多少位的radix呢？
|
g*******y
发帖数: 1930 | 8 花时间？
i = x/n^2
j = (x%n^2)/n
k = ....
呢？
【在 d****i 的大作中提到】
: 把数分解成i*n^2 + j*n + k要花不少时间吧？不如n^3有多少位就用多少位的radix呢？
|
