作者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/cn.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