[理工] 資結 merge sort

[newpuma (還很新)]

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
→ gigayaya: 應該是1的地方錯了吧 假設k=10 n=2 會有2 2 2 2 2個data
→ gigayaya: 然後你做完第一輪後 是4 2 2 2, 4在跟2 merge
→ gigayaya: 所以你每一輪的merge跟k沒關系 是跟n有關 他又說merge
→ gigayaya: 在linear time, 所以merge的time是n n作k回=O(nk)
→ yupog2003: 最後一次做merge的時候會花O((k-1)*n/k)，感覺這時候
→ yupog2003: 不能說bound在O(n/k)
→ yupog2003: 但每次merge都被bound在O(n)是肯定的
推 yupog2003: 這樣子想好了，第一次是O(n/k)，第二次是O(2*n/k)...
→ yupog2003: 把每一次加起來就是O(n/k)+O(2*n/k)+...+O((k-1)*n/k)
→ yupog2003: =n/k*(1+2+3+...+k-1)
→ yupog2003: =O((n/k)*k*(k-1)/2)=O(n*k)
→ yupog2003: 第二行忘記用big-O包起來了
→ ken52011219:  http://i.imgur.com/oBKDwQk.jpg
恩...是我merge的地方想錯了最慘狀況不會只有n/k次比較QQ
※ 編輯: newpuma (223.140.213.159), 12/23/2016 20:22:29