algorithm - 关于 0/1 背包效率的问题？

Question

由于背包的时间复杂度为 O(nW)

背包用

1. 线性时间复杂度
2. 不管W有多大都快
3. W很大时可能需要大内存
4. 如果 W 与 n 成正比，则时间复杂度变为 O(n^2)
5. 以上都不是

以上哪一项是正确的？我认为2、3、4是正确的

Answer 1

背包问题的 O(nW) 时间算法如果只产生答案的数值，则使用 Θ(n) 内存，如果它产生实际答案，则使用 Θ(nW) 内存。

鉴于此，这里有一些提示：

1. 线性时间的定义是什么？O(nW) 是线性时间吗？
2. 这取决于“快速”的定义。您的老师/教授可以填写有关此处含义的详细信息，因为这不是标准术语。
3. 根据我上面的描述，你怎么看？
4. 尝试将 W = n 代入 O(nW)。你拿什么回来？

希望这可以帮助！