55

次のコードの時間計算量を計算する必要があります。

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

O(n^2)ですか？

4

9 に答える 9

81

はい、ネストされたループは、大きな O 表記をすばやく取得する 1 つの方法です。

通常 (常にではありませんが)、1 つのループが別のループにネストされると、O(n²) が発生します。

考えてみてください。内側のループは iの値ごとにi 回実行されます。外側のループは n 回実行されます。

したがって、次のような実行パターンが表示されます: 1 + 2 + 3 + 4 + ... + n 回

したがって、コードの実行回数は、明らかに n 回を超えて実行される (下限) ということで制限できますが、n に関しては、コードを実行する回数は何回になるでしょうか?

数学的には、n² 回を超えて実行されないと言うことができ、最悪のシナリオと、O(n²) の Big-Oh 境界が与えられます。(これを数学的にどのように説明できるかについての詳細は、Power Seriesを参照してください)

Big-Oh は、実行されている作業量を常に正確に測定するとは限りませんが、通常、最悪のシナリオの信頼できる概算値を提供します。

4 年後 編集:この投稿はかなりの量のトラフィックを獲得しているようです。べき級数を使用して実行を O(n²) にバインドする方法をより完全に説明したいと思います

ウェブサイトから: 1+2+3+4...+n = (n² + n)/2 = n²/2 + n/2. では、これをどのように O(n²) に変換するのでしょうか? 私たちが (基本的に) 言っているのは、n² >= n²/2 + n/2 ということです。これは本当ですか？簡単な代数をやってみましょう。

  • 両辺に 2 を掛けると、次のようになります: 2n² >= n² + n?
  • 2n² を展開して取得:n² + n² >= n² + n?
  • n² >= n? を取得するには、両側から n² を引きます。

n が常に整数であると仮定すると、n² >= n (厳密には n=0 または 1 の場合よりも大きくない) であることは明らかです。

実際の Big O の複雑さは、今言ったこととは少し異なりますが、これが要点です。実際には、Big O complex は、十分に大きな入力に対して、一方の関数が他方よりも大きくなるように 1 つの関数に適用できる定数があるかどうかを尋ねます (ウィキペディアのページを参照してください) 。

于 2009-02-09T00:20:41.287 に答える
67

これを説明する簡単な方法は、視覚化することです。

i と j の両方が 0 から N の場合、O(N^2) は簡単にわかります

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

この場合、それは次のとおりです。

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

これは、まだ O(N^2) である N^2 の 1/2 になります。

于 2014-11-08T00:09:17.753 に答える
13

確かにO(n^2)です。ここで、同じランタイムを使用した非常によく似た例も参照してください。

于 2009-02-09T00:08:46.963 に答える
3

外側ループの 1 回目の反復 (i = 1) で、内側ループは 1 回反復します 外側ループの 2 回目の反復 (i = 2) で、内側ループは 2 回反復します 外側ループの 3 回目の反復で(i = 3)、内側のループは 3 回反復し
ます。
.
外側のループ (i = n) の FINAL 反復では、内側のループが n 回反復されます。

したがって、内側のループ内のステートメントが実行される合計回数は、1 から n までの整数の合計に等しくなります。つまり、次のようになります。

((n)*n) / 2 = (n^2)/2 = O(n^2) times 
于 2015-04-16T21:03:06.403 に答える
-2

最初に、内側のループの反復回数が外側のループのインデックスの値に依存しないループを考えます。例えば：

 for (i = 0; i < N; i++) {
     for (j = 0; j < M; j++) {
         sequence of statements
      }
  }

外側のループは N 回実行されます。外側のループが実行されるたびに、内側のループが M 回実行されます。その結果、内側のループ内のステートメントは合計 N * M 回実行されます。したがって、2 つのループの合計の複雑さは O(N2) です。

于 2014-04-29T10:20:19.493 に答える