KnapsackDPで解決できる一方で、NP完全であることはわかっています。pseudo-polynomial彼らは、「入力の長さ」（つまり、入力をエンコードするために必要なビット数）が指数関数的であるため、DPソリューションは であると言います。残念ながら、私はそれを取得しませんでした。誰pseudo-polynomialか私にそのことをゆっくり説明してもらえますか?
40212 次
5 に答える
107
実行時間は、N 個のアイテムとサイズ W のナップザックを持つ無制限のナップザック問題の場合、O(NW) です。ただし、W は入力の長さにおいて多項式ではないため、疑似多項式になります。
W = 1,000,000,000,000 とします。この数値を表すのに 40 ビットしかかからないため、入力サイズ = 40 ですが、計算ランタイムは O(2 40 ) である係数 1,000,000,000,000 を使用します。
したがって、実行時間はより正確には O( W の N.2 ビット) であると言えます。これは指数関数的です。
以下も参照してください。
于 2010-12-27T12:35:54.690 に答える
34
ほとんどの問題では、標準の int/float データ型に問題なく収まる大きな数のリストを扱っています。ほとんどのプロセッサは、追加コストなしで一度に 4 ～ 8 バイトの数値を処理するように構築されているため (たとえば、1 バイトなどの適合する数値と比較して)、数値のスケールアップやスケーリングによる実行時間の変化に遭遇することはほとんどありません。実際の問題で遭遇する範囲内に収まります。したがって、支配的な要因は、データポイントの膨大な量、つまり私たちが慣れ親しんでいる n または m 要因のままです。
(Big-O 表記法は、32 ビットまたは 64 ビット/データを除算する定数係数を隠しており、各数値がそのビット数以下に収まるときは常にデータ ポイントの数のみを残していると想像できます。 )
ただし、ビッグ整数 (表現するのに 8 バイト以上を必要とする数値) を含むデータ セットに作用するように他のアルゴリズムを作り直してみて、それがランタイムに与える影響を確認してください。バイナリソートのような他のアルゴリズムであっても、関係する数値の大きさは常に違いを生みます。安全な従来のプロセッサのバッファを超えて拡張すると、4〜8バイトのバッチを処理することで「無料」になります。
説明したナップザック アルゴリズムの秘訣は、(他のアルゴリズムと比べて) 特定のパラメーター W の大きさに異常に敏感であることです。W に 1 ビットを追加すると、アルゴリズムの実行時間が 2 倍になります。これまで、他のアルゴリズムの値の変化に対するそのような劇的な反応は見られませんでした。そのため、Knapsack を別の方法で扱っているように見えるかもしれません。入力サイズの変更。
于 2013-10-16T06:11:10.093 に答える
10
ナップザック アルゴリズムの実行時間は、入力のサイズ (n - アイテムの数) だけでなく、入力の大きさ (W - ナップザックの容量) O(nW) にも拘束されます。これは指数関数的です。コンピューターではバイナリ (2^n) で表されます。計算の複雑さ (つまり、ビットを介してコンピューター内で処理が行われる方法) は、入力のサイズのみに関係し、その大きさ/値には関係しません。
値/重量リストはしばらく無視してください。ナップザックの容量が 2 のインスタンスがあるとします。W は入力データで 2 ビットを取ります。次に、ナップザックの容量を 4 に増やし、残りの入力を維持します。入力は 1 ビットだけ増えましたが、計算の複雑さは 2 倍になりました。容量を 1024 に増やすと、W の入力は 2 ビットではなく 10 ビットになりますが、複雑さは 512 倍に増加します。時間の複雑さは、バイナリ (または 10 進) 表現の W のサイズで指数関数的に増加します.
擬似多項式の概念を理解するのに役立ったもう 1 つの簡単な例は、素朴な素数性テスト アルゴリズムです。与えられた数 n について、それが範囲 2..√n の各整数で均等に分割されているかどうかをチェックしているため、アルゴリズムは √(n−1) ステップを使用します。ただし、ここでは、n は入力の大きさではなく、大きさです。
Now The regular O(n) case
対照的に、特定の要素の配列の検索は、多項式時間 (O(n)) で実行されます。最大で n ステップかかります。ここで、n は入力のサイズ (配列の長さ) です。
【こちらをご覧ください】
于 2013-10-16T05:50:29.080 に答える