作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] 一题经典的RADIX SORT时间复杂度
时间Fri Apr 30 21:03:27 2010
题目我想应该很多人都看过了
Show how to sort n integers in the range 0 to n^2 - 1 in O(n) time
把它用 n进位制，再使用radix-sort
有一个公式: n b-bit numbers and any postive integer r≦b
则时间复杂度是 θ( (b/r) * ( n + 2^r) )
我的算法是 b = n, r = n
所以 θ( (n/n) * ( n + 2^n ) )
θ( n + 2^n )
这样时间复杂度就不是 O(n) 了吧?
请问是我在公式的时候有错吗?
thinks!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.28.222
1F：→ mqazz1:这公式是Cormen第二版172页的8.4公式 04/30 21:06
2F：推 fadingaway:你算错了，encode 0 ~ n^2-1 的整数只需要 2*lg n bits 05/01 00:35
感谢 我目前算法..
2^b = n^2
log2^b = logn^2
所以 b = 2logn
可是 r 是什麽意思..?
※ 编辑: mqazz1 来自: 61.228.28.222 (05/01 00:45)
3F：推 fadingaway:r 是给你自己任意代入的正整数, 1 <= r <= b 05/01 13:41
谢谢!
※ 编辑: mqazz1 来自: 61.228.26.91 (05/01 13:53)