作者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/cn.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