想请问11和12题要怎么写?
http://i.imgur.com/ylfClGU.jpg
http://i.imgur.com/o7vczhs.jpg

11(a)感觉可以用decision tree，4个数，有4!个leaf树高为log2(4!)，最少comparison次数为log_2(4!)>4

11题题目真的只有这样

http://imgur.com/a/0OA3Y阿对吼，所以真的整个想错了，抱歉

不能用counting sort，题目没给数字的上限，只说n个数字，这要用DP吧，用m*n的布林矩阵，[m,n]=[m,n-1]or[m-a_n,n-1]

11题我猜题目没有拍好？12题，sum要等于m，代表这些integer的range介于1~m用counting sort先排序，需要0(n)然后第一个数先跟最后一个数相加，如果超过m就舍弃最后一个数，然后换第一个数先跟倒数第二个相加，超过m的话再舍弃，一直找到<=m的，等于m的话就找到了，<m的话就第二个数跟刚刚还没舍弃的倒数第x个数，依此类推阿不对，我想错了，刚刚那段全部都错XD12(b)因为m要k=log_2(m)个bit去存他，占的空间是k所以真正的input size是k，而m=2^k，故O(mn)=O(n*2^k)这个叫做pseudo-polynomial time algorithm这个问题可以叫做weakly-NP-complete12(a)我好像想到了，一样counting sortfor i=1 to nfor j=2 to nif a[i]+a[j]>m:break;我又打错了QQ