作者q5332159 (chiu)
看板Grad-ProbAsk
標題[理工] 資結 radix sort時間複雜度
時間Thu Nov 1 16:08:29 2018
http://i.imgur.com/eCueiPi.jpg
想問為什麼合併的部分是O(r)而不是O(n)
我的想法是在合併的時候也是把n個數移到同一個串列
謝謝各位解答~
-----
Sent from JPTT on my HTC_D830x.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.69.108
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1541059712.A.176.html
1F：推 alen0303: 我想可能是類似circular link list的合併方式 這樣合併 11/01 20:16
2F：→ alen0303: 兩條就能達到O(1) 合併r條就只要O(r) 11/01 20:16
3F：→ q5332159: 我本來也是這樣想 但是上網查了一下實作發現都是用陣列 11/01 20:21
4F：→ q5332159: 所以才很疑惑XD 11/01 20:21
6F：→ alen0303: 洪逸課本上給的演算法應該就是用link list 11/01 23:30
7F：→ alen0303: 再用陣列存每條link list頭尾的指標 11/01 23:31
8F：→ alen0303: 不過演算法太長惹我懶得看XD 11/01 23:32
9F：→ q5332159: 喔喔了解~那就照課本上的好了哈哈 11/02 07:25