algorithm - Big O关于背包的定义

Question

所以我读到背包问题的时间复杂度是指数级的，因为它是 O(nW) 并且时间相对于 W 的位串长度呈指数级增长。

但如果是这种情况，这是否意味着以整数 N 作为输入并打印 0 和 N 之间的每个数字的算法也以指数时间运行(与线性相反)，相对于长度N的位串？

Answer 1

没错。将整数 N 作为输入并打印从 0 到 N 的所有整数的算法将按时间以 N 的位数呈指数运行。因此，当我们说算法是“多项式”或“指数”时，我们的意思取决于我们使用的是什么单位。

通常，单位对应于输入的大小(这解释了为什么我们根据背包情况下的位数进行测量)。你的第二个例子看起来很奇怪的原因是通常当我们需要迭代 N 事物时，输入的大小也是 N 阶的。例如，要对 N 个数字求和，我们需要读入 N 个数字，这决定了数量读取数字 N 本身所需的计算量。

顺便说一下，我们通常也认为读取数字需要常数时间，但这并不完全准确，因为它需要对数位来表示一个数字。然而，出于实际目的，这并不重要，因为计算机通常具有处理 1 的硬件，其处理方式与 1000000000 相同。这里有一些相关的讨论:http://en.wikipedia.org/wiki/Random-access_machine .