※ 引述《oklp1415 (天生我材)》之銘言：
: 1.
: what is condition for a radix sort a linear complexity(linear to the number
: of input)?
洪兔上課筆記寫的
(1)沒有採用"Comparsion-Base"技巧
(2)Key range <= K (就是Key的range有限制)
則有機會造出 Linear-time sorting method
Radix sort 之複雜度為 O(d*(n+r))
d : 代表key range有限制，所以回合數固定住，可視為常數C2
r：基底 視為常數C1
所以
O( C2*(n+C1) ) = O( C2*n+C2C1 ) <= O(n)
是為Linear-time
: 2.
: what method uses the least space during the sorting?
: 這題解不是因該quick sort的嗎?
: 想尋求這兩題解答!!
: 謝謝~
我不確定我的答案是不是題目要的@@
不過還是希望有幫到你
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.62.212