作者pyramidinc (PyramidInc)
看板Grad-ProbAsk
標題[理工] 100 清大計科 第二題
時間Wed Dec 11 11:27:43 2019
https://i.imgur.com/XJwuUoF.jpg
請問這題怎麼算？有爬過文但還是不太懂。
第一小題我的想法是分成兩步驟：
1.quick sort:
因為每條有k個元素，所以worst case是k^2,然後做n/k次 =》總共k^2 * (n/k)
2. merge:
共有n/k條，每回合兩兩比較，最多比較k次，要merge log(n/k)回合=》總共 k*log(n/k)
請問這樣的想法哪裡有錯嗎？
還有借問一下有人有比較完整的資結解答嗎？手寫題的解答真的好難找qq
或是有人有寫題的群可以讓小弟我加的嗎，謝謝。
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.25.168 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1576034865.A.DFC.html
1F：→ cossetannie: merge最多是比較n個 12/11 12:17
2F：→ pyramidinc: 我發現我有地方好像想錯 每條k個元素 這樣兩條拿來mer 12/11 12:20
3F：→ pyramidinc: ge最多比2k-1次 然後每回合都是兩兩merge 總共要log(n 12/11 12:20
4F：→ pyramidinc: /k) 回合 但感覺這樣答案還是不對 12/11 12:20
6F：→ pyramidinc: 請問為什麼是n*log(n/k) ? 12/11 13:31
7F：→ jeremyyuan: n個data 最多比n-1次喔 12/11 14:37
9F：→ pyramidinc: 所以是兩兩比對時因為每條k個最多2k次 總共n/k條 兩兩 12/11 16:03
10F：→ pyramidinc: 比對的話要n/2k 組 每組又是2k次 相乘就是n 不知道我 12/11 16:03
11F：→ pyramidinc: 這樣理解有沒有錯？ 12/11 16:03
12F：→ jeremyyuan: 每條k個 最多只會比k次喔 12/11 16:21
13F：推 cossetannie: 用整條是n個去想比較直接一點 12/11 16:34
14F：→ pyramidinc: 好的 感謝 12/11 18:18
15F：推 gash55025502: 我覺得這裡的merge用selection tree的k-way merge去 12/11 20:19
16F：→ gash55025502: 想比較好想 12/11 20:19
17F：推 gash55025502: selection tree共要做O(n)回合（因為要output n個da 12/11 20:21
18F：→ gash55025502: ta) 每回合需花log(n/k)次比較（樹高） 12/11 20:21