[理工] 100 清大計科 第二題

[pyramidinc (PyramidInc)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1576034865.A.DFC.html
→ cossetannie: merge最多是比較n個
→ pyramidinc: 我發現我有地方好像想錯 每條k個元素 這樣兩條拿來mer
→ pyramidinc: ge最多比2k-1次 然後每回合都是兩兩merge 總共要log(n
→ pyramidinc: /k) 回合 但感覺這樣答案還是不對
推 jeremyyuan:  https://i.imgur.com/x2ezS0j.jpg
→ pyramidinc: 請問為什麼是n*log(n/k) ?
→ jeremyyuan: n個data 最多比n-1次喔
推 a9778875: https://goo.gl/khO82I
→ pyramidinc: 所以是兩兩比對時因為每條k個最多2k次 總共n/k條 兩兩
→ pyramidinc: 比對的話要n/2k 組 每組又是2k次 相乘就是n  不知道我
→ pyramidinc: 這樣理解有沒有錯？
→ jeremyyuan: 每條k個 最多只會比k次喔
推 cossetannie: 用整條是n個去想比較直接一點
→ pyramidinc: 好的 感謝
推 gash55025502: 我覺得這裡的merge用selection tree的k-way merge去
→ gash55025502: 想比較好想
推 gash55025502: selection tree共要做O(n)回合（因為要output n個da
→ gash55025502: ta) 每回合需花log(n/k)次比較（樹高）