所以我读到背包问题的时间复杂度是指数的，因为它是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。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句