[問題] 0/1背包問題的時間複雜度

[i78524 (Shulei)]

0/1背包問題的時間複雜度

雖然是演算法的問題，不過是想要和大家請教時間複雜度
想一想之後就決定po到這裡
請大家多多指教，謝謝！

我想問0/1背包問題的時間複雜度的問題

問題如圖 http://i.imgur.com/Sltc4.jpg

以下根據wiki百科

"
儘管背包問題的時間複雜度為O(nW)，但它仍然是一個NP完全問題。這是因為W同問題的輸
入大小並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的比特數。事
實上，log W，即表達W所需的比特數，同問題的輸入長度成線性關係。
"

wiki也是做類似的解釋
不過我還是不懂為什麼只有W要看成BIT數...
請高手解釋一下，謝謝大家了。


:::::::::::::::::::::::::::::::::::::::::::::::::::::::
我是今年資工所的考生，不過沒有補習了
所以問的這個問題也是完全偏向研所考題的
(如果有什麼適合研所考試問問題或互相討論的版也請告知一下)
如果不能在這邊問了話，我會自己刪除的...

謝謝大家，謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.21.235.246
→ firejox:0與1 選與不選呀...
→ suhorng:我自己是覺得...因為W是輸入的"數值"範圍, 不是"數量"範圍
→ suhorng:但以上只是我自己的想法...我沒修過課沒唸過...
推 chchwy:Grad-ProbAsk版是你的好朋友
推 DJWS:因為對W取log之後(log底數為二)，就是W二進位表示法的比特數
→ DJWS:輸入數值到Turing Machine裡面  輸入的是二進位數字
→ i78524:謝謝大家！還有得到了Grad-ProbAsk的相關資訊真的很開心 :)