各位好,想请问
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 我以前回答过类似问题