指数時間アルゴリズム

1. 注意すべき兆候はありますが、これに対する簡単な回答はありません。 。たとえば、セットのすべての可能なサブセットを調べることは指数関数的です-したがって、整数のセット$ \ {x_1、…、x_n \} $があり、これらのすべてのサブセットをチェックして、それらが合計されるかどうかを確認したい場合$ 0 $までは、正確に$ 2 ^ n $のサブセットを考慮する必要があるため、このメソッドは指数関数的な時間になります。いくつかの異なるトラップがアルゴリズムを指数関数的にする可能性がありますが、幅広いカテゴリを探すのではなく、ケースバイケースでアルゴリズムを分析します。

2. アルゴリズムが完了するのに$ n ^ 2 $ステップかかる場合、それは多項式です。$ 2 ^ n $ステップかかる場合、それは指数関数的です。違いは$ n $の位置です。 $ n > 1 $、$ m > 0 $に対して$ O（n ^ m）$の場合、それは固定$ m $の場合は$ n $の多項式ですが、固定$ n $の場合は$ m $の指数関数です。

コメント

• 注意。$ m $が定数でない限り、関数$ n ^ m $ isn ' t多項式は$ n $です。また、$ m $ が定数、'関数がその定数で指数関数的であると言っても意味がありません。
• はい、'正解です。'明確にします。

問題を検討するときに指数関数的な時間ブルートフォースアルゴリズムを取得し、その検索空間全体を列挙することがよくあります。通常、サブセットの問題について考えます（SATでは、次のサブセットを選択します。変数をtrueに設定）、並べ替えの問題（TSPでは、すべてのツアーは都市の並べ替えです）、およびパーティションの問題（グラフの色付けでは、pを実行しようとしています）頂点をカラークラスにアーティフィケーションします）。または、並べ替えも検討してください。$ n $整数の$ n！$順列があります。すべての順列を調べて、ソートされているかどうかを確認します。ばかげている（そして遅い）が、それは機能する。

コメント

• $ O（n！）$は$ O（ k ^ n）$。 'まだ時間計算量について学習しようとしている場合、これは自分自身に証明するのに役立つ可能性があります。