[理工] 資結 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