各位好,想請問
0/1 knapsack problem的時間複雜度為O(nW)其中W因為是用binary表示,所以實際上upper bound為指數,不知道這樣理解對不對?
但是這樣，那n用binary表示，不就還要再取lg ?

please google pseudo-polynomial time

平常我們的n，input size指的是"程式執行次數"，這裡的input W則是variable。 假如變數為4, 在memory裡則佔lg4=2, 但是程式執行次數實際上為4次(2^2)，所以為指數成長

我覺的課本應該是假設W比n大很多，大到我們根本沒辦法用固定的bit數去表示，所以他才將W化成2^m，而n因為比較小，可以用固定bit去表示，e.g. n=32k or n=64k，所以O(32k*2^m)=O(k*2^m)，n有沒有化成bit數並不影響整個時間複雜度。https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time我是看這篇的，因為如果n指的是程式執行次數而不用化成bit數的話，文章下面那個isPrime(n)時間複雜度應該為O(n)（這個function只執行n-2次）

#1N-azPo9 我以前回答過類似問題