1003

GoogleとStackOverflowの検索を行ったが、時間計算量の計算方法について明確でわかりやすい説明を見つけることができなかった。

私はすでに何を知っていますか？

以下のような単純なコードを考えてみましょう。

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

次のようなループについて考えてみましょう。

for (int i = 0; i < N; i++) {
    Console.Write('Hello World !');
}
  • int i=0;これは1回だけ実行されます。時間は実際にi=0は宣言ではなく計算されます。
  • i < N;これはN+1回実行されます
  • i++これはN回実行されます

したがって、このループに必要な操作の数は{1+（N + 1）+ N} = 2N+2です。（しかし、私は自分の理解に自信がないので、これはまだ間違っているかもしれません。）

OK、これらの小さな基本的な計算は私が知っていると思いますが、ほとんどの場合、時間計算量はO（N）、O（n ^ 2）、O（log n）、O（n！）などです。 。

4

9 に答える 9

449

アルゴリズムの時間計算量を見つける方法

入力のサイズの関数として実行するマシン命令の数を合計し、式を最大の（Nが非常に大きい場合）項に単純化し、任意の単純化定数係数を含めることができます。

たとえば、2N + 2これを単に。として説明するために、マシン命令を単純化する方法を見てみましょうO(N)。

なぜ2つを削除する2のですか？

Nが大きくなるにつれて、アルゴリズムのパフォーマンスに関心があります。

2Nと2という2つの用語を考えてみましょう。

Nが大きくなるにつれて、これら2つの項の相対的な影響は何ですか？Nが100万だとします。

その場合、第1項は200万で、第2項はわずか2です。

このため、大きなNの最大の項を除くすべてを削除します。

これで、から2N + 2になりました2N。

従来、私たちは一定の要因までのパフォーマンスにのみ関心があります。

これは、Nが大きい場合に、パフォーマンスに一定の倍数の差があるかどうかは実際には気にしないことを意味します。とにかく、2Nの単位はそもそも明確に定義されていません。したがって、定数係数で乗算または除算して、最も単純な式を得ることができます。

だから2NちょうどになりNます。

于 2012-06-14T11:25:12.177 に答える
434

これは優れた記事です： http ：//www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

以下の回答は上からコピーされています（優れたリンクが壊れた場合）

時間計算量を計算するための最も一般的なメトリックは、BigO表記です。これにより、すべての定数係数が削除されるため、Nが無限大に近づくにつれて、実行時間はNに関連して推定できます。一般的に、あなたはそれをこのように考えることができます：

statement;

一定です。ステートメントの実行時間は、Nに対して変更されません。

for ( i = 0; i < N; i++ )
     statement;

線形です。ループの実行時間はNに正比例します。Nが2倍になると、実行時間も2倍になります。

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

二次です。2つのループの実行時間は、Nの2乗に比例します。Nが2倍になると、実行時間はN*Nだけ増加します。

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

対数です。アルゴリズムの実行時間は、Nを2で割ることができる回数に比例します。これは、アルゴリズムが反復ごとに作業領域を半分に分割するためです。

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

N * log（N）です。実行時間は、対数であるN個のループ（反復または再帰）で構成されているため、アルゴリズムは線形と対数の組み合わせです。

一般に、1次元のすべてのアイテムで何かを行うことは線形であり、2次元のすべてのアイテムで何かを行うことは二次であり、作業領域を半分に分割することは対数です。三次、指数、平方根などの他のBig Oメジャーがありますが、それらはほとんど一般的ではありません。Big O表記は、メジャーO ( <type> )がどこにあるかとして説明されます。<type>クイックソートアルゴリズムは、として記述されO ( N * log ( N ) )ます。

これはいずれも、最良、平均、および最悪の場合の測定値を考慮していないことに注意してください。それぞれに独自のBigO表記があります。また、これは非常に単純な説明であることに注意してください。Big Oが最も一般的ですが、私が示したよりも複雑です。ビッグオメガ、リトルオ、ビッグシータなどの他の表記法もあります。おそらく、アルゴリズム分析コースの外ではそれらに遭遇することはないでしょう。;）

于 2013-01-18T10:04:35.560 に答える
198

ここからの抜粋-アルゴリズムの時間計算量の概要

1.はじめに

コンピュータサイエンスでは、アルゴリズムの時間計算量は、入力を表す文字列の長さの関数として、アルゴリズムが実行されるのにかかる時間を定量化します。

2.ビッグO表記

アルゴリズムの時間計算量は、通常、係数と低次の項を除外する大きなO表記を使用して表されます。このように表現すると、時間計算量は漸近的に、つまり入力サイズが無限大になるにつれて記述されると言われます。

たとえば、サイズnのすべての入力でアルゴリズムに必要な時間が最大で5n 3 + 3nの場合、漸近時間計算量はO（n 3）です。これについては後で詳しく説明します。

その他の例：

  • 1 = O（n）
  • n = O（n 2）
  • log（n）= O（n）
  • 2 n + 1 = O（n）

3. O（1）定数時間：

入力サイズに関係なく同じ時間が必要な場合、アルゴリズムは一定時間で実行されると言われます。

例：

  • 配列：任意の要素にアクセスする
  • 固定サイズのスタック：プッシュメソッドとポップメソッド
  • 固定サイズのキュー：エンキューおよびデキューメソッド

4. O（n）線形時間

アルゴリズムの実行時間が入力サイズに正比例する場合、つまり、入力サイズが大きくなるにつれて時間は線形に増加する場合、アルゴリズムは線形時間で実行されると言われます。

次の例を考えてみましょう。以下では、要素を線形に検索しています。これには、O（n）の時間計算量があります。

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

その他の例：

  • 配列：線形探索、トラバース、最小値の検索など
  • ArrayList：メソッドが含まれています
  • キュー：メソッドを含む

5. O（log n）対数時間：

アルゴリズムの実行時間が入力サイズの対数に比例する場合、アルゴリズムは対数時間で実行されると言われます。

例：二分探索

「二十の質問」ゲームを思い出してください。タスクは、間隔内の隠された数の値を推測することです。推測するたびに、推測が高すぎるか低すぎるかが通知されます。二十の質問ゲームは、推測数を使用して間隔サイズを半分にする戦略を意味します。これは、二分探索として知られている一般的な問題解決方法の例です。

6. O（n 2）2次時間

アルゴリズムの実行時間が入力サイズの2乗に比例する場合、アルゴリズムは2次時間で実行されると言われます。

例：

7.いくつかの便利なリンク

于 2014-03-27T13:14:17.463 に答える
115

この質問にはいくつかの良い答えがありますが。ここで、いくつかの例を挙げて別の答えを示したいと思いloopます。

  • O（n） ：ループ変数が一定量だけインクリメント/デクリメントされる場合、ループの時間計算量はO（n）と見なされます。たとえば、次の関数はO（n）時間計算量を持っています。

    // Here c is a positive integer constant   
for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

for (int i = n; i > 0; i -= c) {
    // some O(1) expressions
}

  • O（n ^ c）：ネストされたループの時間計算量は、最も内側のステートメントが実行された回数と同じです。たとえば、次のサンプルループの時間計算量はO（n ^ 2）です。

    for (int i = 1; i <=n; i += c) {
   for (int j = 1; j <=n; j += c) {
      // some O(1) expressions
   }
}

for (int i = n; i > 0; i += c) {
   for (int j = i+1; j <=n; j += c) {
      // some O(1) expressions
}

    たとえば、選択ソートと挿入ソートには、O（n ^ 2）時間計算量があります。

  • O（Logn）時間ループ変数が一定量で除算/乗算された場合、ループの時間計算量はO（Logn）と見なされます。

    for (int i = 1; i <=n; i *= c) {
   // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
   // some O(1) expressions
}

    たとえば、二分探索にはO（Logn）時間計算量があります。

  • O（LogLogn）ループ変数が一定量だけ指数関数的に減少/増加する場合、ループの時間計算量はO（LogLogn）と見なされます。

    // Here c is a constant greater than 1   
for (int i = 2; i <=n; i = pow(i, c)) { 
   // some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = fun(i)) { 
   // some O(1) expressions
}

時間計算量分析の一例

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

分析：

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

したがって、上記のアルゴリズムの合計時間計算量は(n + n/2 + n/3 + … + n/n)、になります。n * (1/1 + 1/2 + 1/3 + … + 1/n)

シリーズについて重要なことは、 O（Logn）(1/1 + 1/2 + 1/3 + … + 1/n)と同じです。したがって、上記のコードの時間計算量はO（nLogn）です。

参照： 1 2 3

于 2015-11-02T09:31:56.700 に答える
77

例による時間計算量

1-基本操作（算術、比較、配列の要素へのアクセス、割り当て）：実行時間は常に一定ですO（1）

例 ：

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2-if then elseステートメント：2つ以上の可能なステートメントからのみ最大実行時間を取得します。

例：

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

したがって、上記の擬似コードの複雑さはT（n）= 2 + 1 + max（1、1 + 2）= 6です。したがって、その大きなohは定数T（n）= O（1）のままです。

3-ループ（for、while、repeat）：このステートメントの実行時間は、ループの数にそのループ内の操作の数を掛けたものです。

例：

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

したがって、その複雑さはT（n）= 1 + 4n + 1 = 4n + 2です。したがって、T（n）= O（n）です。

4-ネストされたループ（ループ内のループ）：メインループ内に少なくとも1つのループがあるため、このステートメントの実行時間はO（n ^ 2）またはO（n ^ 3）を使用しました。

例：

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

一般的な実行時間

アルゴリズムを分析する場合、いくつかの一般的な実行時間があります。

  1. O（1）–時定数時定数とは、実行時間が一定であり、入力サイズの影響を受けないことを意味します。

  2. O（n）–線形時間アルゴリズムがn個の入力サイズを受け入れる場合、n個の操作も実行します。

  3. O（log n）–実行時間O（log n）を持つ対数時間アルゴリズムはO（n）よりわずかに高速です。一般に、アルゴリズムは問題を同じサイズのサブ問題に分割します。例：二分探索アルゴリズム、二分変換アルゴリズム。

  4. O（n log n）–線形時間この実行時間は、問題を再帰的にサブ問題に分割し、それらをn時間でマージする「分割統治アルゴリズム」でよく見られます。例：マージソートアルゴリズム。

  5. O（n 2）–二次時間ルックバブルソートアルゴリズム！

  6. O（n 3 ）–キュービック時間O（n 2 ）と同じ原理です。

  7. O（2 n）–指数時間入力が大きくなるにつれて非常に遅くなります。n= 1000.000の場合、T（n）は21000.000になります。ブルートフォースアルゴリズムには、この実行時間があります。

  8. O（n！）–階乗時間最も遅い!!! 例：巡回セールスマン問題（TSP）

この記事から引用。非常によく説明されているので、読んでください。

于 2014-04-19T09:36:07.843 に答える
41

コードを分析するときは、すべての操作をカウントし、時間の複雑さを認識して、コードを1行ずつ分析する必要があります。最終的には、コードを合計して全体像を把握する必要があります。

たとえば、線形の複雑さを持つ1つの単純なループを持つことができますが、同じプログラムの後半で、3次の複雑さを持つトリプルループを持つことができるため、プログラムは3次の複雑さを持つことになります。ここで、成長の機能順序が機能します。

アルゴリズムの時間計算量の可能性を見てみましょう。前述の成長の順序を確認できます。

  • 一定の時間には成長の順序があり1例：a = b + c。

  • 対数時間には成長の順序がありLogNます。これは通常、何かを半分に分割するとき（二分探索、木、さらにはループ）、または同じ方法で何かを乗算するときに発生します。

  • 線形、成長の順序はN、例えばです

    int p = 0;
for (int i = 1; i < N; i++)
  p = p + 2;

  • 線形性、成長の順序はn*logN、通常、分割統治アルゴリズムで発生します。

  • キュービック、成長の順序N^3、典型的な例は、すべてのトリプレットをチェックするトリプルループです。

    int x = 0;
for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
          x = x + 2

  • 指数関数的な成長の順序は2^N、通常、徹底的な検索を行うときに発生します。たとえば、あるセットのサブセットをチェックします。

于 2016-06-05T09:43:59.000 に答える
40

大まかに言えば、時間計算量は、入力サイズが大きくなるにつれてアルゴリズムの操作数または実行時間がどのように増加するかを要約する方法です。

人生のほとんどのもののように、カクテルパーティーは私たちが理解するのを助けることができます。

オン）

パーティーに到着したら、みんなの手を振る必要があります（すべてのアイテムを操作します）。参加者の数がN増えると、全員の手を振るのにかかる時間/作業が増えますO(N)。

なぜO(N)、そうではないのcNですか？

人と握手するのにかかる時間にはばらつきがあります。これを平均して、定数でキャプチャすることができcます。しかし、ここでの基本的な操作---全員と握手する---はO(N)、何cがあったとしても、常にに比例します。カクテルパーティーに行くべきかどうかを議論するとき、私たちはしばしば、それらの会議がどのように見えるかについての詳細よりも、すべての人に会わなければならないという事実に関心があります。

O（N ^ 2）

カクテルパーティーの主催者は、誰もが他の人と出会う愚かなゲームをプレイすることを望んでいます。したがって、あなたはN-1他の人に会う必要があり、次の人はすでにあなたに会っているので、彼らはN-2人に会う必要があります。このシリーズの合計はですx^2/2+x/2。参加者の数が増えるにつれて、x^2用語は急速に大きくなるので、他のすべてを削除します。

O（N ^ 3）

あなたは他のみんなに会わなければなりません、そして、それぞれの会合の間に、あなたは部屋の他のみんなについて話さなければなりません。

O（1）

ホストは何かを発表したいと思っています。彼らはワイングラスを鳴らし、大声で話します。誰もがそれらを聞きます。参加者の数に関係なく、この操作には常に同じ時間がかかります。

O（log N）

ホストは全員をアルファベット順にテーブルに配置しました。ダンはどこ？あなたは彼がアダムとマンディの間のどこかにいなければならないと推論します（確かにマンディとザックの間ではありません！）。それを考えると、彼はジョージとマンディの間にいますか？いいえ。彼はアダムとフレッドの間、およびシンディとフレッドの間にいる必要があります。など...セットの半分を見てから、そのセットの半分を見ると、ダンを効率的に見つけることができます。最終的に、O（log_2 N）個の個体を調べます。

O（N log N）

上記のアルゴリズムを使用して、テーブルのどこに座るかを見つけることができます。一度に1人ずつ多数の人がテーブルに来て、全員がこれを行った場合、O（N log N）の時間がかかります。これは、アイテムのコレクションを比較する必要がある場合に、それらをソートするのにかかる時間であることがわかります。

ベスト/ワーストケース

あなたはパーティーに到着し、イニゴを見つける必要があります-それはどのくらいかかりますか？いつ到着するかによります。誰もが周りを練り歩き回っているなら、あなたは最悪のケースにぶつかります：それは時間がかかりO(N)ます。ただし、全員がテーブルに座っている場合は、時間しかかかりませんO(log N)。あるいは、ホストのワイングラスを叫ぶ力を活用することができ、それは時間しかかかりませんO(1)。

ホストが利用できないと仮定すると、Inigo-findingアルゴリズムには、到着時のパーティの状態に応じて、のO(log N)下限と上限があると言えます。O(N)

宇宙とコミュニケーション

同じアイデアを、アルゴリズムが空間または通信をどのように使用するかを理解するために適用できます。

クヌースは前者について「歌の複雑さ」というタイトルの素晴らしい論文を書いています。

定理2：複雑さO（1）の任意の長い曲が存在します。

証拠:(ケーシーとサンシャインバンドによる）。（15）で定義されたSkの曲を考えてみましょう。

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

すべてのkについて。

于 2015-10-14T04:12:28.223 に答える
5

私はこの質問がさかのぼることを知っています、そしてここにいくつかの優れた答えがあります、それにもかかわらず私はこの投稿でつまずくであろう数学に関心のある人々のためにもう少し共有したいと思いました。マスター定理は、複雑さを研究するときに知っておくと便利なもう1つのことです。私はそれが他の答えで言及されているのを見ませんでした。

于 2015-11-04T09:20:14.063 に答える
2

O（n）は、アルゴリズムの時間計算量を記述するために使用される大きなO表記です。アルゴリズムの実行回数を合計すると、2N + 2のような結果が得られます。この式では、Nが支配的な項です（値が増減した場合に式に最も大きな影響を与える項）。ここで、O（N）は時間の複雑さであり、Nは項を支配しています。例

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

ここで、内部ループの合計実行数はn + 1であり、外部ループの合計実行数はn（n + 1）/ 2であるため、アルゴリズム全体の合計実行数はn + 1 + n（n + 1/2）です。 ）=（n ^ 2 + 3n）/2。ここで、n ^ 2が支配的な項であるため、このアルゴリズムの時間計算量はO（n ^ 2）です。

于 2013-03-11T20:18:39.540 に答える