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. linear time の定義は? O(nW) は線形時間ですか?
2. これは、「高速」の定義によって異なります。これは標準的な用語ではないため、教師/教授がここで何を意味するかについて詳細を記入できます。
3. 以上のことを踏まえて、あなたはどう思いますか？
4. W = n を O(nW) に代入してみてください。あなたは何を返しますか？

お役に立てれば！