所以我读到背包问题的时间复杂度是指数的，因为它是O（nW），并且时间相对于W的位串的长度呈指数增长。
但是，如果是这种情况，这并不意味着以整数N作为输入并输出0到N之间的每个数字的算法，相对于N的位串？
是的。一个以整数N作为输入（输出从0到N的所有整数）的算法将以N的位数按时间指数运行。因此，当我们说一个算法是“多项式”或“指数”时，我们的意思取决于我们正在使用什么单位。
通常，单位对应于输入的大小（这解释了为什么我们用背包情况下的位数进行测量）。您的第二个示例看起来很奇怪的原因是，通常当我们需要遍历N个事物时，输入的大小也是N阶。例如，要对N个数字求和，我们需要读入N个数字，这主要是数量数N本身所需的计算量。
顺便说一句，我们通常也认为读数字需要花费固定的时间，但这并不是完全准确的，因为用对数数表示一个数字需要很多位。但是，出于实际目的，这无关紧要，因为计算机通常具有处理1的硬件与1000000000相同的方式。这里有一些相关的讨论：http://en.wikipedia.org/wiki/Random-access_machine。