[理工] 104 清大 計算機科學

[kev72806 (想太多oo)]

這一題小弟我是說明採用 radix sort 給它
過程由個位數開始至最高位數 d
由於範圍已知故 d 為常數
每回合執行時間是 O(n)
這樣解釋符合題意嘛 @@
如果需要做更多的說明麻煩幫我補充 ><
http://i.imgur.com/a1N9YVN.jpg

下面這一題的 b 小題，
如何說明 subset sum problem 是一個 NP-hard 的問題呢？A的演算法我會寫可是不知道
b要怎麼說明 ..
http://i.imgur.com/ZighEn5.jpg
http://i.imgur.com/OBKeSO5.jpg

最後一個問題是在解什麼問題呢 @@
我自己列出來的時間函數是 T(n)=T(3n/4)+T(n/2)+n
不過感覺就不對 = = 有請高手指教
http://i.imgur.com/6wxVTXX.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.64.128
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453099323.A.C70.html
推 OppOops: 第一題要說明d是如何得知的, d和radix的選擇有何關係
→ OppOops: 第二題說明m的input string長度為k, 則m至少為2^k
→ OppOops: 第三題T(n) = O(1)+O(1)+O(n)+O(n)+O(n)+T(3n/4) = O(n)
→ lemonsheep: 可是第一題是要O(|S|),如果|S|=n^1/2應該就不是O(n)?
→ OppOops: 對 不會是O(n)
→ lemonsheep: 這樣用radix sort不一定可以確保O(|S|)吧?
推 OppOops: 確實O(d|S|)不會是O(|S|), 所以d要選擇正確
→ OppOops: d想辦法讓它是常數... 如果radix有選好
→ OppOops: 提示: O( d * (|S| + radix) ),  radix跟n有關
感謝 O 大的解釋！用多個回合限制範圍再說明範圍的取法這樣我了解了
第三題我再想想看 感恩

→ lemonsheep: 恩恩了解 對原PO取法有疑問而已 感謝
→ jerry031181: 我是用counting sort 讓range在n^1/2內做4回合
→ jerry031181: b的話說明一下儲存m只需logm的大小 所以input size
→ jerry031181: O(nm)=O(n*2^(logm)) 不為polynomial time
感謝 j 大的說明！
※ 編輯: kev72806 (49.214.64.128), 01/18/2016 22:33:46
推 dslin: 想請問k大第2題的演算法怎麼寫呀??