關於0/1揹包效率的問題？

Question

作爲揹包爲O的時間複雜度（NW）

爲揹包

1. 線性時間複雜度
2. 快速無質W多大
3. 可能需要一個大的存儲器，當W是大
4. 當w成正比n，則時間複雜度變爲O（N^2）
5. 沒有以上

以上哪一項是真實的？ 我認爲2，3，4是正確

Answer 1

的O（NW）-time算法揹包問題使用Θ（n）的存儲器，如果它只是產生的答案的數值和Θ（NW）存儲器，如果它產生實際的答案。

鑑於此，這裏有一些提示：

1. 什麼是線性時間的定義是什麼？ O（nW）是線性時間嗎？
2. 這取決於「快」的定義。你的老師/教授可以填寫這裏的含義，因爲這不是一個標準術語。
3. 根據我上面所描述的，你的想法是什麼？
4. 嘗試用W = n代入O（nW）。你回來了什麼？

希望這會有所幫助！