82

O(n!)関数の (コード内の) 例は何ですか? を参照して実行するには、適切な数の操作が必要nです。つまり、時間の複雑さについて質問しています。

4

17 に答える 17

121

ほらね。O(n!)これはおそらく、時間内に実行される関数の最も単純な例です(nは関数の引数です)。

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}
于 2010-10-17T12:42:17.620 に答える
51

古典的な例の 1 つは、ブルート フォース検索による巡回セールスマンの問題です。

都市が存在する場合N、ブルート フォース法はこれらの都市のすべての順列を試して、Nどれが最も安いかを見つけます。N現在、都市との順列の数はN!複雑性を階乗にしています ( O(N!))。

于 2010-10-17T12:41:43.960 に答える
10

Big O ウィキペディアの記事の共通関数の順序セクションを参照してください。

記事によると、巡回セールスマン問題をブルート フォース サーチで解決することと、未成年者による展開で決定要因を見つけることは、どちらも O(n!) です。

于 2010-10-17T13:03:44.563 に答える
8

与えられた配列のすべての順列を計算するアルゴリズムはO(N!).

于 2010-11-02T13:44:29.610 に答える
6

NP-complete(非決定論的多項式時間で検証可能)という問題があります。つまり、入力がスケーリングされると、問題を解決するために必要な計算が大幅に増加します。

ハミルトニアン経路問題NP-hard( open img ),巡回セールスマン問題( open img )ブール充足可能性問題 (土) ( open img ) , N-パズル( open img ), ナップザック問題( open img ),部分グラフ同型問題( open img )、部分和問題( open img )、クリーク問題( open img )、頂点カバー問題
NP-complete( open img ),独立集合問題( open img ),支配集合問題( open img ),グラフ彩色問題( open img ),

ソース:リンク 1、リンク 2

代替テキスト
出典：リンク

于 2010-10-17T12:43:59.457 に答える
6

私は少し遅れていると思いますが、snailsortは O(n!) 決定論的アルゴリズムの最良の例だと思います。基本的に、配列を並べ替えるまで、配列の次の順列を見つけます。

次のようになります。

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}
于 2010-10-17T18:38:54.273 に答える
5

未成年者による拡張で決定要因を見つける。

ここで非常に良い説明。

# include <cppad/cppad.hpp>
# include <cppad/speed/det_by_minor.hpp>

bool det_by_minor()
{   bool ok = true;

    // dimension of the matrix
    size_t n = 3;

    // construct the determinat object
    CppAD::det_by_minor<double> Det(n);

    double  a[] = {
        1., 2., 3.,  // a[0] a[1] a[2]
        3., 2., 1.,  // a[3] a[4] a[5]
        2., 1., 2.   // a[6] a[7] a[8]
    };
    CPPAD_TEST_VECTOR<double> A(9);
    size_t i;
    for(i = 0; i < 9; i++)
        A[i] = a[i];


    // evaluate the determinant
    double det = Det(A);

    double check;
    check = a[0]*(a[4]*a[8] - a[5]*a[7])
          - a[1]*(a[3]*a[8] - a[5]*a[6])
          + a[2]*(a[3]*a[7] - a[4]*a[6]);

    ok = det == check;

    return ok;
}

ここからコード。必要な.hppファイルもそこにあります。

于 2010-10-17T12:43:23.707 に答える
4

最も簡単な例:)

疑似コード:

input N
calculate N! and store the value in a vaiable NFac - this operation is o(N)
loop from 1 to NFac and output the letter 'z' - this is O(N!)

そこに行きます:)

実際の例として、一連のアイテムのすべての順列を生成する場合はどうでしょうか?

于 2010-10-17T12:42:29.307 に答える
2

ウィキペディアでは

ブルートフォース検索による巡回セールスマン問題の解決; 未成年者による拡張で決定要因を見つける。

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

于 2010-10-17T13:04:37.137 に答える
1

C# の場合

これは、空間の複雑さで O(N!) ではないでしょうか? なぜなら、C# の文字列は不変だからです。

string reverseString(string orgString) {
    string reversedString = String.Empty;

    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }

    return reversedString;
}
于 2011-02-18T16:17:36.157 に答える
1

printf("Hello World");

はい、これはO(n!)です。そうでないと思われる場合は、BigOh の定義をお読みになることをお勧めします。

この回答を追加したのは、実際の意味に関係なく、人々が常に BigOh を使用しなければならないという迷惑な習慣があるためです。

たとえば、質問がシータ(n!)、少なくとも cn! ステップとCn以下！一部の定数 c、C > 0 のステップですが、代わりに O(n!) を使用することを選択しました。

別の例: Quicksort is O(n^2) in the worst case、技術的には正しい (最悪の場合、ヒープソートでさえ O(n^2) です!) が、実際の意味はQuicksort is Omega(n^2) in the worst caseです。

于 2011-02-18T17:19:12.800 に答える
0

行列式をとるためにおそらく学んだ再帰的方法（線形代数をとった場合）には、O（n！）時間がかかります。私は特にそれをすべてコーディングする気はしませんが。

于 2010-10-18T10:37:46.753 に答える
0

Bogosortは、私が遭遇した唯一の「公式」であり、O(n!) エリアに足を踏み入れています。ただし、本質的にランダムであるため、保証された O(n!) ではありません。

于 2010-10-17T14:32:50.620 に答える
0

@clocksmith あなたは絶対に正しいです。これは n! を計算していません。また、O(n!) のものでもありません。以下の表のデータを収集して実行しました。列 2 と列 3 を比較してください。(#nF は nFacRuntimeFunc への呼び出しの数です)

n #nF n!

0    0      1
1    1      1
2    4      2
3    15     6
4    65     24
5    325    120
6    1956   720
7    13699  5040

明らかに、if は O(n!) よりもはるかに悪いパフォーマンスを示します。以下は、n! を計算するためのサンプル コードです。再帰的に。O(n) オーダーであることに注意してください。

int Factorial(int n)
{
   if (n == 1)
      return 1;
   else
      return n * Factorial(n-1);
}
于 2016-12-17T21:29:20.280 に答える