[理工]100清大計科

看板Grad-ProbAsk作者 (cshcsh6847)時間7年前 (2017/01/14 15:41), 編輯推噓1(1推 0噓 19→)
留言20則, 3人參與, 最新討論串1/1
想要請問大家100年清大計科第二題 http://imgur.com/a/CjQBR 如果是 (a) quick sort的 worst case 不是 k^2嗎 然後再用merge 所以我的想法是 (n/k)*k^2 + n/k(1+2+...+k-1) 但是稍微爬板發現似乎不太正確 想請問大家這題該用什麼角度想，謝謝！ 至於(b)想必我想的也是錯的QQ 最近在寫考古題 但是大部分非選擇題都找不太到答案 連爬板都找不到 是不是這種題目真的找不太到QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 124.12.193.208 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484379699.A.907.html
推
01/14 15:49, , 1F
我也沒有正確答案，我的想法是(n/k)*k^2+k*log(n/k)
01/14 15:49, 1F
→
01/14 15:50, , 2F
阿不對，我再想更仔細一點
01/14 15:50, 2F
→
01/14 15:54, , 3F
也許應該是(n/k)*k^2+(n/k)*log(n/k)?
01/14 15:54, 3F
→
01/14 15:55, , 4F
前半段的想法跟你一樣，後半段我想說有n/k sublists
01/14 15:55, 4F
→
01/14 15:56, , 5F
用divide and conquer，T(x)=2T(x/2)+O(x)，
01/14 15:56, 5F
→
01/14 15:57, , 6F
T(x)=O(xlogx)，這裡的x是n/k，代進去就得到我的想法
01/14 15:57, 6F
→
01/14 15:57, , 7F
所以merge那裡他是使用一次兩個兩個merge嗎
01/14 15:57, 7F
→
01/14 15:58, , 8F
我大概懂大大的意思了！因為我想成有寫過一題要慢慢me
01/14 15:58, 8F
→
01/14 15:58, , 9F
rge QQ
01/14 15:58, 9F
→
01/14 16:01, , 10F
哈哈我也寫過那題，第一個念頭也是那個方法
01/14 16:01, 10F
→
01/14 16:09, , 11F
ㄟㄟ我後來發現應該是T(x)=2T(x/2)+O(n/x)才對，因為
01/14 16:09, 11F
→
01/14 16:10, , 12F
sublist的長度是k，而x=n/k => k=n/x才對，所以那個
01/14 16:10, 12F
→
01/14 16:11, , 13F
big-Oh裡面要填O(n/x)，我最後化簡T(x)=O(n^2/k)...
01/14 16:11, 13F
→
01/14 16:14, , 14F
所以整個答案變成O(nk+n^2/k)
01/14 16:14, 14F
→
01/14 16:18, , 15F
但好像還是錯...
01/14 16:18, 15F
→
01/14 16:20, , 16F
喔喔！！！好的謝謝y大！！
01/14 16:20, 16F
→
01/14 16:21, , 17F
我來研究看看QQQQ
01/14 16:21, 17F
→
01/14 16:35, , 18F
我好像想通了，big-Oh裡面要填O(kx/2)才對，這樣就會算
01/14 16:35, 18F
→
01/14 16:36, , 19F
出解答那樣子，抱歉沒想清楚一直亂回答
01/14 16:36, 19F
→
01/14 16:36, , 20F
https://goo.gl/khO82I 據說之前是CLRS 的題目
01/14 16:36, 20F
‣ 更多 cshcsh6847 的文章
文章代碼(AID): #1OUTOpa7 (Grad-ProbAsk)