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

看板Grad-ProbAsk作者 (想太多oo)時間10年前 (2016/01/18 14:42), 10年前編輯推噓3(3推 0噓 11→)
留言14則, 4人參與, 最新討論串1/2 (看更多)
這一題小弟我是說明採用 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
推
01/18 18:37, , 1F
第一題要說明d是如何得知的, d和radix的選擇有何關係
01/18 18:37, 1F
→
01/18 18:39, , 2F
第二題說明m的input string長度為k, 則m至少為2^k
01/18 18:39, 2F
→
01/18 18:58, , 3F
第三題T(n) = O(1)+O(1)+O(n)+O(n)+O(n)+T(3n/4) = O(n)
01/18 18:58, 3F
→
01/18 21:09, , 4F
可是第一題是要O(|S|),如果|S|=n^1/2應該就不是O(n)?
01/18 21:09, 4F
→
01/18 21:32, , 5F
對 不會是O(n)
01/18 21:32, 5F
→
01/18 21:39, , 6F
這樣用radix sort不一定可以確保O(|S|)吧?
01/18 21:39, 6F
推
01/18 21:42, , 7F
確實O(d|S|)不會是O(|S|), 所以d要選擇正確
01/18 21:42, 7F
→
01/18 21:43, , 8F
d想辦法讓它是常數... 如果radix有選好
01/18 21:43, 8F
→
01/18 21:45, , 9F
提示: O( d * (|S| + radix) ), radix跟n有關
01/18 21:45, 9F
感謝 O 大的解釋！用多個回合限制範圍再說明範圍的取法這樣我了解了 第三題我再想想看 感恩
→
01/18 21:52, , 10F
恩恩了解 對原PO取法有疑問而已 感謝
01/18 21:52, 10F
→
01/18 22:03, , 11F
我是用counting sort 讓range在n^1/2內做4回合
01/18 22:03, 11F
→
01/18 22:05, , 12F
b的話說明一下儲存m只需logm的大小 所以input size
01/18 22:05, 12F
→
01/18 22:06, , 13F
O(nm)=O(n*2^(logm)) 不為polynomial time
01/18 22:06, 13F
感謝 j 大的說明！ ※ 編輯: kev72806 (49.214.64.128), 01/18/2016 22:33:46
推
01/19 11:38, , 14F
想請問k大第2題的演算法怎麼寫呀??
01/19 11:38, 14F
‣ 更多 kev72806 的文章
文章代碼(AID): #1Md8axnm (Grad-ProbAsk)
‣ 更多 kev72806 的文章
文章代碼(AID): #1Md8axnm (Grad-ProbAsk)