2

私は Big-O について独学をしています。次の表記法の例をアルゴリズムに与える方法を理解しています。

オン）：

for(int i = 0; i < n; i++)
    sum++;

O(N^2):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O(N^3):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

私はよく理解していないこれらの表記法に出くわしました。アルゴリズムの観点からこれらの例をどのように挙げればよいでしょうか?

たぶん、次のように表現する必要があります: に比例して実行時間がかかるアルゴリズムを書きます:

  1. O((n^3)/4)
  2. ログ n^3
  3. O((log^2)n)+O(n)
  4. 4^n
  5. n^3/2
4

2 に答える 2

9

「Big-O」表記を誤解しているのではないかと心配しています。

記法はアルゴリズムとして「表現」されていません。むしろ、Big-O 表記はアルゴリズムのプロパティを表します。

つまり、「O(N) は XXX と表現できる」ではなく、「アルゴリズム XXX は O(N) の複雑さを持っている」ということです。

とはいえ、特定の複雑さを持つアルゴリズムの例を求めることは非常に合理的です。あなたはすでにいくつかをリストしています。質問に対処するには:

O(4^n) は O(e^n) と同じで、しばしば O(exp(n)) と書かれます (なぜ同じなのかを理解してください)。O(4^n) は、「指数関数的複雑さ」( EXPTIME )を持つアルゴリズムのクラスに属します。数学/CS の多くの重要な問題には、指数関数的な複雑さ (またはほぼ指数関数的な複雑さ) があります。

指数関数的な複雑さを持つアルゴリズムは、たとえば、離散対数問題に対する単純な解になります。

他の複雑さについては、例を挙げることはできませんが、少しグーグルで検索することでおそらく見つけることができます。

于 2010-10-25T08:35:28.660 に答える
-1

あなたが与えたアルゴリズムは、厳密に言えば Big-O ではなく Theta です。Big-O は漸近的な上限であり、最悪の場合の入力では実行時間が指定された時間になりますが、すべての入力に対してそうではないことを意味します。Theta はタイトな境界であるため、実行時間は常にそれになることを意味します。たとえば、すでに並べ替えられたリストが入力として与えられる並べ替えアルゴリズム、または検索対象がリストの最初の要素である検索アルゴリズムを考えてみましょう (この場合、バイナリ検索は線形検索とどのように比較されますか)。

于 2010-10-25T08:45:09.440 に答える