[理工] 資結 radix sort時間複雜度

[q5332159 (chiu)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1541059712.A.176.html
推 alen0303: 我想可能是類似circular link list的合併方式 這樣合併
→ alen0303: 兩條就能達到O(1) 合併r條就只要O(r)
→ q5332159: 我本來也是這樣想 但是上網查了一下實作發現都是用陣列
→ q5332159: 所以才很疑惑XD
推 alen0303: https://i.imgur.com/5amaUmy.jpg
→ alen0303: 洪逸課本上給的演算法應該就是用link list
→ alen0303: 再用陣列存每條link list頭尾的指標
→ alen0303: 不過演算法太長惹我懶得看XD
→ q5332159: 喔喔了解~那就照課本上的好了哈哈