推 yupog2003: 我也沒有正確答案，我的想法是(n/k)*k^2+k*log(n/k) 01/14 15:49
→ yupog2003: 阿不對，我再想更仔細一點 01/14 15:50
→ yupog2003: 也許應該是(n/k)*k^2+(n/k)*log(n/k)? 01/14 15:54
→ yupog2003: 前半段的想法跟你一樣，後半段我想說有n/k sublists 01/14 15:55
→ yupog2003: 用divide and conquer，T(x)=2T(x/2)+O(x)， 01/14 15:56
→ yupog2003: T(x)=O(xlogx)，這裡的x是n/k，代進去就得到我的想法 01/14 15:57
→ cshcsh6847: 所以merge那裡他是使用一次兩個兩個merge嗎 01/14 15:57
→ cshcsh6847: 我大概懂大大的意思了！因為我想成有寫過一題要慢慢me 01/14 15:58
→ cshcsh6847: rge QQ 01/14 15:58
→ yupog2003: 哈哈我也寫過那題，第一個念頭也是那個方法 01/14 16:01
→ yupog2003: ㄟㄟ我後來發現應該是T(x)=2T(x/2)+O(n/x)才對，因為 01/14 16:09
→ yupog2003: sublist的長度是k，而x=n/k => k=n/x才對，所以那個 01/14 16:10
→ yupog2003: big-Oh裡面要填O(n/x)，我最後化簡T(x)=O(n^2/k)... 01/14 16:11
→ yupog2003: 所以整個答案變成O(nk+n^2/k) 01/14 16:14
→ yupog2003: 但好像還是錯... 01/14 16:18
→ cshcsh6847: 喔喔！！！好的謝謝y大！！ 01/14 16:20
→ cshcsh6847: 我來研究看看QQQQ 01/14 16:21
→ yupog2003: 我好像想通了，big-Oh裡面要填O(kx/2)才對，這樣就會算 01/14 16:35
→ yupog2003: 出解答那樣子，抱歉沒想清楚一直亂回答 01/14 16:36