作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1515514950.A.587.html
1F：→ sarsman: 6. Merge sort适用於data量很大，需要硬碟辅助储存的情况 01/10 00:29
2F：→ sarsman: ； bucket sort适用於能事先确定输入的数字值域的情况 01/10 00:29
3F：推 yupog2003: 7.2你写的叙述应该是P? 01/10 09:00
4F：→ yupog2003: 喔喔没事我看错了 01/10 09:02
5F：推 kobechampion: 4 应该是p-approximation algo 必不存在 01/22 11:19
6F：推 ko330: bucket sort还有一个digit数就是回合数d不大的时候较适合 01/30 11:26
7F：→ ko330: 像1,11,111,1111这种，因为他配10分我觉得多写一点比较好 01/30 11:26