为什么背包问题是伪多项式？
我知道Knapsack是NP-complete，DP可以解决。 他们说DP解决scheme是pseudo-polynomial ，因为它是“input长度”（即input编码所需的位数）的指数。 不幸的是我没有得到它。 有人可以慢慢地向我解释这个pseudo-polynomial东西吗？
运行时间为O（NW）对于一个无限背包问题的N项和W的大小背包。W在input的长度不是多项式，这是什么使它伪多项式。
考虑W = 1,000,000,000,000。 它只需要40位来表示这个数字，所以input大小= 40，但是计算运行时间使用的因数是10000000000，即O（2 40 ）。
所以运行时间更准确地说是O（ W的 N.2 位 ），这是指数的。
另请参阅：
- 如何理解背包问题是NP完全的？
- 背包的NP完全性
- dynamic规划algorithm对0-1背包问题的复杂性
- 伪多项式时间
在我们的大部分问题中，我们正在处理大量的数字列表，这些列表很适合标准的int / float数据types。 由于大多数处理器的构build方式是一次处理4-8个字节的数字，而不需要额外的成本（相对于数字而言，比如1个字节），我们很less遇到从缩放数字到改变运行时间或在我们遇到的实际问题的范围内 – 所以主导因素仍然是数据点的绝对数量，我们习惯的n或m个因素。
（你可以想象，Big-O符号隐藏了一个不变的因素，即每个数据分成32位或者64位，只留下数据点的数量，只要我们每个数字适合那么多位或者更less）
但是可以尝试使用其他algorithm进行重新处理，以处理涉及大型数据集的数据集 – 需要超过8个字节的数字来表示 – 并查看对运行时的影响。 所涉及的数字的大小总是有所不同，即使在其他algorithm（如二进制sorting）中，一旦您扩展到安全常规处理器的缓冲区以外，通过处理4-8字节的批处理就可以“免费”。
我们讨论的背包algorithm的诀窍是它对特定参数W的大小非常敏感（相对于其他algorithm）。向W添加一位，并且使algorithm的运行时间加倍。 在这之前我们还没有看到对其他algorithm中价值变化的那种戏剧性的反应，这就是为什么看起来我们正在以不同的方式处理Knapsack – 但这是对它是如何以非多项式方式响应的真实分析改变input大小。
背包algorithm的运行时间不仅受input大小的限制（n – 项数），而且也受input量（W – 背包容量）O（nW）的影响，在计算机中以二进制（2 ^ n）表示。计算复杂度（即如何通过比特在计算机内完成处理）只与input的大小有关，而不是其大小/值 。
忽略价值/权重列表片刻。 假设我们有一个背包容量为2的实例。W将在input数据中占用两位。 现在我们把背包容量增加到4，保留其余的投入。 我们的投入只增长了一点，但计算复杂度增加了两倍。 如果我们将容量增加到1024，那么W的input只有10位而不是2，但是复杂度增加了512倍。时间复杂度以二进制（或十进制）表示W的大小呈指数增长。
帮助我理解伪多项式概念的另一个简单例子是朴素的素数testingalgorithm。 对于一个给定的数n，我们检查它是否被范围2..√n中的每个整数均匀分割，所以该algorithm需要√（n-1）个步骤。 但是在这里，n是input的大小，而不是大小。
Now The regular O(n) case
相比之下，search一个给定元素的数组运行多项式时间：O（n）。 它最多需要n个步骤，这里的n是input的大小（数组的长度）。
[ 看这里 ]
计算存储十进制数所需的位
