[理工] 106 清大 計科

看板Grad-ProbAsk作者時間6年前 (2018/01/10 00:22), 編輯推噓3(3推 0噓 4→)
留言7則, 4人參與, 5年前最新討論串1/1
因為手邊沒有答案，想跟大家討論看看 第六題 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
→
01/10 00:29, 6年前 , 1F
6. Merge sort適用於data量很大，需要硬碟輔助儲存的情況
01/10 00:29, 1F
→
01/10 00:29, 6年前 , 2F
； bucket sort適用於能事先確定輸入的數字值域的情況
01/10 00:29, 2F
推
01/10 09:00, 6年前 , 3F
7.2你寫的敘述應該是P?
01/10 09:00, 3F
→
01/10 09:02, 6年前 , 4F
喔喔沒事我看錯了
01/10 09:02, 4F
推
01/22 11:19, 6年前 , 5F
4 應該是p-approximation algo 必不存在
01/22 11:19, 5F
推
01/30 11:26, 5年前 , 6F
bucket sort還有一個digit數就是回合數d不大的時候較適合
01/30 11:26, 6F
→
01/30 11:26, 5年前 , 7F
像1,11,111,1111這種，因為他配10分我覺得多寫一點比較好
01/30 11:26, 7F
‣ 更多 a1596482 的文章
文章代碼(AID): #1QLEn6M7 (Grad-ProbAsk)