[理工] 100 清大計科 第二題
請問這題怎麼算？有爬過文但還是不太懂。
第一小題我的想法是分成兩步驟：
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
→
12/11 12:17,
6年前
, 1F
12/11 12:17, 1F
→
12/11 12:20,
6年前
, 2F
12/11 12:20, 2F
→
12/11 12:20,
6年前
, 3F
12/11 12:20, 3F
→
12/11 12:20,
6年前
, 4F
12/11 12:20, 4F
推
12/11 13:16,
6年前
, 5F
12/11 13:16, 5F
→
12/11 13:31,
6年前
, 6F
12/11 13:31, 6F
→
12/11 14:37,
6年前
, 7F
12/11 14:37, 7F
推
12/11 14:44,
6年前
, 8F
12/11 14:44, 8F
→
12/11 16:03,
6年前
, 9F
12/11 16:03, 9F
→
12/11 16:03,
6年前
, 10F
12/11 16:03, 10F
→
12/11 16:03,
6年前
, 11F
12/11 16:03, 11F
→
12/11 16:21,
6年前
, 12F
12/11 16:21, 12F
推
12/11 16:34,
6年前
, 13F
12/11 16:34, 13F
→
12/11 18:18,
6年前
, 14F
12/11 18:18, 14F
推
12/11 20:19,
6年前
, 15F
12/11 20:19, 15F
→
12/11 20:19,
6年前
, 16F
12/11 20:19, 16F
推
12/11 20:21,
6年前
, 17F
12/11 20:21, 17F
→
12/11 20:21,
6年前
, 18F
12/11 20:21, 18F