[問題] 一題經典的RADIX SORT時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/04/30 21:03)推噓2(2推 0噓 1→)留言3則, 2人參與討論串1/1
題目我想應該很多人都看過了
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
→
04/30 21:06, , 1F
04/30 21:06, 1F
推
05/01 00:35, , 2F
05/01 00:35, 2F
感謝 我目前算法..
2^b = n^2
log2^b = logn^2
所以 b = 2logn
可是 r 是什麼意思..?
※ 編輯: mqazz1 來自: 61.228.28.222 (05/01 00:45)
推
05/01 13:41, , 3F
05/01 13:41, 3F
謝謝!
※ 編輯: mqazz1 來自: 61.228.26.91 (05/01 13:53)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
