[理工] 資結 merge sort

看板Grad-ProbAsk作者 (還很新)時間7年前 (2016/12/23 16:46), 7年前編輯推噓1(1推 0噓 12→)
留言13則, 3人參與, 最新討論串1/1
http://i.imgur.com/WdeKDSx.jpg
因為我寫不出遞迴式，所以用iterative分析： 1 因為merge的過程中只要其中一個run為空就會馬上return 所以不管是n/k跟n/k做merge 或是3n/k與n/k做merge應該都是花O(n/k)的時間 2 因為他是依序往後merge所以總共會執行k回合 這樣分析下來應該是k*n/k也就是O(n)吧？ 為什麼答案是給n*k？話說題目說的following algorithm是...?(104交大資演) 如果每次merge都要做最大run原是個數的時間才有機會被bound在n*k吧？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.213.159 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482482809.A.166.html
→
12/23 17:55, , 1F
應該是1的地方錯了吧 假設k=10 n=2 會有2 2 2 2 2個data
12/23 17:55, 1F
→
12/23 17:55, , 2F
然後你做完第一輪後 是4 2 2 2, 4在跟2 merge
12/23 17:55, 2F
→
12/23 17:56, , 3F
所以你每一輪的merge跟k沒關系 是跟n有關 他又說merge
12/23 17:56, 3F
→
12/23 17:57, , 4F
在linear time, 所以merge的time是n n作k回=O(nk)
12/23 17:57, 4F
→
12/23 17:58, , 5F
最後一次做merge的時候會花O((k-1)*n/k)，感覺這時候
12/23 17:58, 5F
→
12/23 17:58, , 6F
不能說bound在O(n/k)
12/23 17:58, 6F
→
12/23 18:00, , 7F
但每次merge都被bound在O(n)是肯定的
12/23 18:00, 7F
推
12/23 18:02, , 8F
這樣子想好了，第一次是O(n/k)，第二次是O(2*n/k)...
12/23 18:02, 8F
→
12/23 18:03, , 9F
把每一次加起來就是O(n/k)+O(2*n/k)+...+O((k-1)*n/k)
12/23 18:03, 9F
→
12/23 18:03, , 10F
=n/k*(1+2+3+...+k-1)
12/23 18:03, 10F
→
12/23 18:04, , 11F
=O((n/k)*k*(k-1)/2)=O(n*k)
12/23 18:04, 11F
→
12/23 18:05, , 12F
第二行忘記用big-O包起來了
12/23 18:05, 12F
→
12/23 20:09, , 13F
12/23 20:09, 13F
恩...是我merge的地方想錯了最慘狀況不會只有n/k次比較QQ ※ 編輯: newpuma (223.140.213.159), 12/23/2016 20:22:29
‣ 更多 newpuma 的文章
文章代碼(AID): #1ONEHv5c (Grad-ProbAsk)