[理工] 资结 radix sort时间复杂度 q5332159 PTT批踢踢实业坊

[理工] 资结 radix sort时间复杂度

楼主: q5332159 (chiu) 2018-11-01 16:08:29

http://i.imgur.com/eCueiPi.jpg
想问为什么合并的部分是O(r)而不是O(n)
我的想法是在合并的时候也是把n个数移到同一个串行
谢谢各位解答~

作者: alen0303 (艾伦零参智商负三) 2018-11-01 20:16:00

我想可能是类似circular link list的合并方式这样合并两条就能达到O(1) 合并r条就只要O(r)

楼主: q5332159 (chiu) 2018-11-01 20:21:00

我本来也是这样想但是上网查了一下实作发现都是用阵列所以才很疑惑XD

作者: alen0303 (艾伦零参智商负三) 2018-11-01 23:30:00

https://i.imgur.com/5amaUmy.jpg洪逸课本上给的算法应该就是用link list再用阵列存每条link list头尾的指标不过算法太长惹我懒得看XD

楼主: q5332159 (chiu) 2018-11-02 07:25:00

喔喔了解~那就照课本上的好了哈哈

继续阅读

[理工] 资结 shellsort inversion疑问rodndy666 [理工] data hazard Mem access 问题qazws3483 [理工] 计组 ch5 hazard问题sssxyz11 [理工] 计组浮点数十进制二进制转换QoGIVoQ Re: [理工] 101台联大电机计组 signal问题j5464654 [理工] 资结 Fibonacci heap delete xq5332159 [理工] 计组 branch 与 pcbefdawn [理工] 资结3-53 例35（D)!Aa841018 [理工] 资结graphqazws3483 [理工] 线代第五章 T or Forzotz01

Contact Us: admin [ a t ] ucptt.com