我知道背包问题是NP完全问题，但它可以通过DP解决。人们说DP解法是伪多项式，因为它在“输入长度”（即编码输入所需的位数）上是指数级别的。不幸的是我还没有理解这个概念。有人能够慢慢地向我解释一下什么是伪多项式吗？
为什么背包问题是伪多项式？
116
- Michael
1
可能是如何理解背包问题是NP完全的？的重复问题。 - nbro
5个回答
116
一个无界背包问题中，有N个物品和大小为W的背包，时间复杂度为O(NW)。然而，W并不是输入长度的多项式，这就是为什么它被称为“伪多项式”的原因。
考虑W=1,000,000,000,000，它只需要40位来表示，因此输入大小为40，但计算时间使用了因子1,000,000,000,000，即O(2^40)。
因此，运行时间更准确地说是O(N.2^(W的位数))，这是指数级的。
另请参见：
- 如何理解背包问题是NP完全问题？ - Knapsack的NP完全性 - 0-1背包问题的动态规划算法的复杂度 - 伪多项式时间
考虑W=1,000,000,000,000，它只需要40位来表示，因此输入大小为40，但计算时间使用了因子1,000,000,000,000，即O(2^40)。
因此，运行时间更准确地说是O(N.2^(W的位数))，这是指数级的。
另请参见：
- 如何理解背包问题是NP完全问题？ - Knapsack的NP完全性 - 0-1背包问题的动态规划算法的复杂度 - 伪多项式时间
- moinudin
5
1第三个链接指向“0-1背包问题的动态规划复杂度”已经失效。 - dev_nut
4抱歉，我没听懂。假设我们有一个时间复杂度为O(N)的算法，那么我们就有了O(2^(N的位数))，这是指数级的吗？谢谢~ - Lusha Li
6@LushaLi 这个视频对我很有帮助：https://www.youtube.com/watch?v=9oI7fg-MIpE。如果 N 是一个数组，其中每个元素的固定最大输入大小为32位（例如，数组中的每个元素都不超过32位），并且您在该数组上运行一次 for 循环，则它是一个多项式时间复杂度算法，其输入大小 N 是数组的大小。但是，如果 N 是一个整数，并且您在 N 上运行一个循环，则 N 是无界的，并且随着表示它所需的位数的增加呈指数增长。因此，对于 N 的简单 for 循环实际上是指数级别的。请注意，在数组的情况下，数组中每个元素的大小都有上限。 - max_max_mir
2我并不信服。有很多具有相同特性但不是“伪多项式”的算法。比如，埃拉托斯特尼筛法（或任何其他质数查找器）的复杂度是多少？ - Ofir A.
2描述算法的运行时间真是一种奇怪的方式。如果你有一个外循环，它有 N 次迭代，和一个内循环，它有 W 次迭代，那么你的算法的运行时间是 O(NW)……对吧？你的程序输入中包含了 N 个整数和一个整数 W 的事实似乎是一个单独的问题——你的算法仍然会进行 N*W 次迭代。 - Snackoverflow
38
在大多数情况下，我们处理的是包含在标准整型/浮点类型中的大量数字列表。由于大多数处理器设计为同时处理4-8字节大小的数字（相对于适合1字节大小的数字而言），而不需要额外付出代价，因此我们很少会遇到在我们遇到的实际问题范围内扩大或缩小数字所需的运行时间变化 - 因此，主要影响因素仍然只是数据点的数量，我们习惯的n或m因素。
（你可以想象大O符号隐藏了一个常数因子，该因子将每个数字拆分为32位或64位，只留下数据点的数量，每个数字适合那么多位或更少位）
但是尝试使用其他算法来处理涉及大于8字节的大整数的数据集，并查看它对运行时间的影响。所涉及数字的数量级始终会产生差异，即使在二进制排序等其他算法中，一旦您超出传统处理器免费提供的4-8字节缓冲区，“安全”范围。
Knapsack算法的诀窍在于，它对特定参数W的数量级异常敏感（相对于其他算法）。将W增加1位，算法的运行时间就会增加一倍。我们以前没有看到其他算法对值的变化产生如此剧烈的反应，这就是为什么它可能看起来像我们对待Knapsack不同的原因 - 但这是一种非多项式方式分析其对输入大小变化的响应。
（你可以想象大O符号隐藏了一个常数因子，该因子将每个数字拆分为32位或64位，只留下数据点的数量，每个数字适合那么多位或更少位）
但是尝试使用其他算法来处理涉及大于8字节的大整数的数据集，并查看它对运行时间的影响。所涉及数字的数量级始终会产生差异，即使在二进制排序等其他算法中，一旦您超出传统处理器免费提供的4-8字节缓冲区，“安全”范围。
Knapsack算法的诀窍在于，它对特定参数W的数量级异常敏感（相对于其他算法）。将W增加1位，算法的运行时间就会增加一倍。我们以前没有看到其他算法对值的变化产生如此剧烈的反应，这就是为什么它可能看起来像我们对待Knapsack不同的原因 - 但这是一种非多项式方式分析其对输入大小变化的响应。
- shaunak1111
1
1到目前为止，这是我读过的最好的回复。 - Jinhua Wang
20
我的理解是，如果容量输入是一个大小为W的数组[1,2，...，W]，则其容量将为O(W)，该数组的大小为W。但容量输入不是数字数组，而是单个整数。时间复杂度与输入大小的关系有关。整数的大小不是它的值，而是表示它的位数。在算法中，稍后将此整数W转换为数组[1,2，...，W]，导致人们错误地认为W是大小，但这个数组不是输入，整数本身才是。
将输入视为“一堆东西的数组”，大小为“数组中有多少东西”。实际上，项输入是数组中n个项目的数组，因此大小为n。容量输入不是其中包含W个数字的数组，而是单个整数，由log(W)位数组表示。将其大小增加1（添加1个有意义的位），W加倍，因此运行时间加倍，因此呈指数时间复杂度。
将输入视为“一堆东西的数组”，大小为“数组中有多少东西”。实际上，项输入是数组中n个项目的数组，因此大小为n。容量输入不是其中包含W个数字的数组，而是单个整数，由log(W)位数组表示。将其大小增加1（添加1个有意义的位），W加倍，因此运行时间加倍，因此呈指数时间复杂度。
- lineil
2
1这解决了很多问题，谢谢。 - gordon_freeman
这没有任何意义。按照这个逻辑，一个求前n个自然数和的for循环就是伪多项式？ - DollarAkshay
12
Knapsack算法的运行时间受到输入规模（n - 物品数量）和输入大小（W - 背包容量）的限制，其时间复杂度为O(nW)，这在计算机中以二进制表示时是指数级别的（2^n）。计算复杂度（即计算机内部通过位处理的方式）只关注输入的规模，而不关注它们的大小/值。
暂时忽略价值/重量列表。假设我们有一个背包容量为2的实例，W将占用输入数据中的两个位。现在，我们将背包容量增加到4，保持其余输入不变。我们的输入只增加了一位，但计算复杂度增加了两倍。如果我们将容量增加到1024，那么我们将只有10位W的输入，而不是2位，但复杂度增加了512倍。时间复杂度在二进制（或十进制）表示中随着W的大小呈指数级增长。
另一个帮助我理解伪多项式概念的简单例子是朴素素性测试算法。对于给定的数字n，我们正在检查它是否可以被2..√n范围内的每个整数整除，因此算法需要√(n−1)步。但在这里，n是输入的大小，而不是他的规模。
暂时忽略价值/重量列表。假设我们有一个背包容量为2的实例，W将占用输入数据中的两个位。现在，我们将背包容量增加到4，保持其余输入不变。我们的输入只增加了一位，但计算复杂度增加了两倍。如果我们将容量增加到1024，那么我们将只有10位W的输入，而不是2位，但复杂度增加了512倍。时间复杂度在二进制（或十进制）表示中随着W的大小呈指数级增长。
另一个帮助我理解伪多项式概念的简单例子是朴素素性测试算法。对于给定的数字n，我们正在检查它是否可以被2..√n范围内的每个整数整除，因此算法需要√(n−1)步。但在这里，n是输入的大小，而不是他的规模。
Now The regular O(n) case
相比之下，搜索数组中的某个元素以多项式时间运行：O(n)。它最多需要n步，这里的n是输入的大小（数组的长度）。
[ 在此查看 ]
- shaunak1111
1
6针对您最后的搜索示例，为什么不考虑将n也表示为二进制呢？例如n=1024时，也只需10位二进制表示，这样难道不是伪多项式时间吗？ - user1024
2
复杂性基于输入。在背包问题中，输入是大小、最大容量、利润和重量数组。我们构建dp表为size * W，因此我们感觉它的时间复杂度是多项式级别的。但是，输入W是一个整数，而不是一个数组。因此，它将是O(size*(存储给定W所需的位数)). 如果位数增加1，则运行时间加倍。因此它是指数级别的，因此是伪多项式。
- Venkateswarlu Gupta
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接