Mic*_*ael 68 language-agnostic complexity-theory knapsack-problem dynamic-programming
我知道这Knapsack是NP完全的,而DP可以解决.他们说DP解决方案是pseudo-polynomial,因为它在"输入长度"(即编码输入所需的位数)中是指数的.不幸的是我没有得到它.有人能pseudo-polynomial慢慢向我解释那件事吗？
mar*_*cog 66
对于具有N个项目和大小为W的背包的无界背包问题,运行时间为O(NW).虽然W在输入的长度上不是多项式的,这使得它伪伪多项式.
考虑W = 1,000,000,000,000.它只需要40位来表示这个数字,因此输入大小= 40,但计算运行时使用因子1,000,000,000,000即O(2 40).
因此,运行时更准确地说是O(W中的 N.2 位),这是指数的.
另见:
sha*_*111 25
在我们的大多数问题中,我们正在处理大量的数字列表,这些数字很适合标准的int/float数据类型.由于大多数处理器的构建方式一次只能处理4-8个字节的数字而无需额外成本(相对于数字而不是1英寸),我们很少会遇到从缩放数字或在我们在实际问题中遇到的范围内 - 所以主导因素仍然只是数据点的绝对数量,我们习惯的n或m因子.
(你可以想象Big-O表示法隐藏了一个常数因子,它将每个数据分成32或64位,只要每个数字都适合那么多位或更少,就只留下数据点数)
但是尝试重新使用其他算法来处理涉及大整数的数据集 - 需要超过8个字节来表示的数字 - 并查看它对运行时的作用.所涉及的数字的大小总是有所不同,即使在其他算法如二进制排序中,一旦你扩展到安全缓冲区之外,传统的处理器通过处理4-8字节批次给我们"免费".
我们讨论的Knapsack算法的技巧是,它对于特定参数W的大小非常敏感(相对于其他算法).向W添加一位,并使算法的运行时间加倍.在此之前我们还没有看到对其他算法价值变化的那种戏剧性反应,这就是为什么看起来我们对待背包的方式不同 - 但这是对它如何以非多项式方式作出反应的真实分析改变输入大小.
nei*_*ims 13
我的理解是，如果容量输入是 [1,2,...,W] 数组，其大小为 W ，则容量将是 O(W) 。但容量输入不是一个数字数组，它是一个整数。时间复杂度大约是关系到尺寸输入。整数的大小不是整数的值，而是表示它的位数。后来我们在算法中把这个整数W转换成数组[1,2,...,W]，导致人们误以为W是大小，但这个数组不是输入，整数本身才是。
将输入视为“一组内容”，将大小视为“数组中有多少内容”。项目输入实际上是数组中的 n 个项目的数组，因此 size=n。容量输入不是其中包含 W 个数字的数组，而是一个整数，由 log(W) 位数组表示。将其大小增加 1（添加 1 个有意义的位），W 加倍，因此运行时间加倍，因此时间复杂度为指数级。
Knapsack算法的运行时间不仅取决于输入的大小(n - 项目数),还取决于输入的大小(W - 背包容量)O(nW),它是如何指数的在计算机中以二进制(2 ^ 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是输入的大小(数组的长度).
[ 看这里 ]
| 归档时间： |
|
| 查看次数： |
24901 次 |
| 最近记录： |