作者a1596482 ()
看板Grad-ProbAsk
標題[理工] 106 清大 計科
時間Wed Jan 10 00:22:28 2018
因為手邊沒有答案，想跟大家討論看看
第六題
https://i.imgur.com/IRgLsML.jpg
這題是問怎樣的data分別適合merge sort和bucket sort嗎？
我想到使用bucket sort的data數字要小，例如1～9999之類的
第七題
https://i.imgur.com/h2YZCQY.jpg
1.T NPC被NP-hard包含
2.F NP為可被nondeterministic 在多項式時間內解決的
3.F 任一NPC reduce 到X
4.F 存在2-approximation algo
有錯還請大家幫忙指正
第八題
https://i.imgur.com/4lFtevq.jpg
不知該從何下手
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.205.6
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1515514950.A.587.html
→ sarsman: 6. Merge sort適用於data量很大，需要硬碟輔助儲存的情況 01/10 00:29
→ sarsman: ； bucket sort適用於能事先確定輸入的數字值域的情況 01/10 00:29
推 yupog2003: 7.2你寫的敘述應該是P? 01/10 09:00
→ yupog2003: 喔喔沒事我看錯了 01/10 09:02
推 kobechampion: 4 應該是p-approximation algo 必不存在 01/22 11:19
推 ko330: bucket sort還有一個digit數就是回合數d不大的時候較適合 01/30 11:26
→ ko330: 像1,11,111,1111這種，因為他配10分我覺得多寫一點比較好 01/30 11:26