想請問11和12題要怎麼寫?

11(a)感覺可以用decision tree，4個數，有4!個leaf樹高為log2(4!)，最少comparison次數為log_2(4!)>4

11題題目真的只有這樣

" target="_blank" rel="nofollow">

阿對吼，所以真的整個想錯了，抱歉

不能用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