就是作業四的某一題，他問說
一個複雜度為 O(nW) 的 0-1 knapsack 的演算法是否為 polynomial time
我一開始的理解是，因為 W 和 n 並沒有一定關係，所以不能確定它是否為polynomial
time
但在詢問了某位上學期修過演算法的強者之後，我大概瞭解題目想幹嘛了～
就是在判斷一個複雜度對 input 的大小為何種關係的時候，要有個比較的基準
比如說 merge sort ，複雜度 O(n lg n) ，比較的基準就是被排序的陣列大小 n
但是 n 和 W 之間沒有特定的關係，沒辦法就 nW 來判斷它是哪一種函數關係
因此要取它們共同的基準─ bit 的長度，來決定這個函數
首先 n 就是 item 數目的大小， n 個東西就 n 個 bit ( 1 或 0 代表拿或不拿)，所以
是線性的
至於 W ，是背包的大小，用 bit 來表示的話是一個二進位的數字
所以當 bit 長度變為 2 倍時， W 其實是變成 W^2 ，是指數關係
所以 nW 不是 polynomial time
如果有甚麼錯的話還請不吝指教，謝謝！