10

そのnを見るのは非常に簡単です！N乗（たとえば、100 ^ N）のほとんど何よりもゆっくりと成長するため、問題がNP完全であると見なされ、問題が発生した場合は！解を近似するアルゴリズムでは、スヌーピーダンスを行います。

この状況について2つの質問があります。

  1. nだろう！アルゴリズムは多項式時間の解と見なされますか？階乗は確かに権力に引き上げられた用語ではないようです。
  2. 見つけたら！解決策とは、かなり高速なアルゴリズムを使用していることを意味します。2 ^ Nよりも速く成長する場合、これは、一部のNP完全問題がヒューリスティック/近似アルゴリズムを必要としないことを意味しますか（あいまいな場合を除く）？

もちろん、これら2つの質問は、最初の段落が正しいことに依存しています。間違えた場合はお知らせください。

4

2 に答える 2

41

  1. いいえ、階乗時間は多項式時間ではありません。多項式時間は通常、O(N k ) の形式の方程式を意味します。ここで、N = 処理されるアイテムの数、k = 何らかの定数です。重要な部分は、指数が定数であるということです.N自体に依存するのではなく、固定された数をNに掛けています。階乗複雑度アルゴリズムは、乗算の数が固定されていないことを意味します。乗算の数自体は、N とともに増加します。

  2. あなたはここで同じ問題を抱えているようです。N 2は多項式の複雑さになります。2 Nではありません。あなたの基本的な教訓も間違っています.factorial-complexityアルゴリズムは、少なくとも一般的なルールとして、「かなり高速なアルゴリズムを持っている」という意味ではありません。どちらかといえば、結論はむしろ逆です。階乗アルゴリズムは、いくつかの特殊なケース (つまり、N が非常に小さい場合) では実用的かもしれませんが、N が大きくなるとすぐに実用的ではなくなります。

これを視野に入れてみましょう。二分探索は O(log N) です。線形検索は O(N) です。ソートでは、「遅い」アルゴリズムは O(N 2 ) であり、「高度な」アルゴリズムは O(N lg N) です。階乗複雑度は (明らかに十分) O(N!) です。

(今のところ) 10 項目だけを考慮して、それにいくつかの数字を当てはめてみましょう。これらはそれぞれ、1 アイテムではなく 10 アイテムの処理にかかるおおよその回数です。

O(ログ N): 2
O(N):10
O(N ログ N): 23
O(N 2 ): 100
O(N!): 3,628,800

今のところ、私は少しごまかしており、2 を底とする対数の代わりに自然対数を使用していますが、ここでは概算の推定のみを試みています (いずれにせよ、差はかなり小さな定数係数です)。

ご覧のとおり、factorial-complexity アルゴリズムの成長率は、他のどのアルゴリズムよりもはるかに高速です。20 項目に拡張すると、違いはさらに劇的になります。

O(log N): 3
O(n): 20
O(N log N): 60
O(N 2 ): 400
O(N!): 2,432,902,008,176,640,000

Nの成長率！非常に高速であるため、関連するアイテムの数が非常に少ないことがわかっている場合を除いて、実用的ではないことがほぼ保証されています. grins については、上記のプロセスの基本操作がそれぞれ 1 つのマシン クロック サイクルで実行できると仮定しましょう。議論のために (そして計算を簡単にするために)、10 GHz の CPU を想定してみましょう。したがって、基本は、1 つのアイテムの処理に 0.1 ns かかるということです。その場合、20個のアイテムで：

O(log N) = .3 ns
O(N) = 2 ns
O(N log N) = 6 ns
O(N 2 ) = 40 ns
O(N!) = 7.7 年。

于 2011-06-04T06:16:20.270 に答える
5

階乗の動作が (ほぼ) 指数関数的であることは非常に簡単にわかります。

これは (非常に大雑把に) n n (より具体的には sqrt(2πn)(n/e) n ) として近似できます。

したがって、M nが適切な近似値であると考える特定の M を見つけた場合は、(おそらく) 間違っています。269！は 100 nより大きく、n! 100 を超える数が掛けられると、より速く成長し続けます。

于 2011-06-04T10:36:59.750 に答える