-3

以下のコード フラグメントについて、Big O の複雑さを分析する必要があります。

a)

// loop 1
for(int i = 0; i < n; i++)
  // loop 2
  for(int j = i; j < n; j++)
    sum++;

b)

// loop 1
for(int i = 0; i < n; i++)
  // loop 2
  for(int j = i + 1; j > i; j--)
    // loop 3
    for(int k = n; k > j; k--)
      sum++;

その方法がわからないので、提供されたヘルプは大歓迎です。ありがとう。

4

2 に答える 2

1

1 つ目は簡単です (2 つ目のコード スナップのツールを使用しますが、これは少しトリッキーです)。2 つ目のコード スナップに焦点を当てます。

Big O表記は、アルゴリズムが実行する操作の数に漸近的な上限を与えています。

各内部反復が 1 つの op を実行すると仮定し、カウンターとループのオーバーヘッドを無視しましょう。
プログラムT(n)で実行された操作の総数を示します。

プログラムにこれ以上の操作がないことは明らかです。

 // loop 1
for(int i = 0; i < n; i++)
   // loop 2
   for(int j = i+1; j > i; j--) //note a single op in here, see (1) for details
      // loop 3
      for(int k = n; k > 0; k--) //we change k > j to j > 0 - for details see (2)
         sum++;

(1)jは として初期化されi+1、繰り返しごとに減少するため、ループ 2 の最初の繰り返しの後、 が得られj == i、条件は false になります。つまり、1 回の繰り返しが行われます
(2) 元のループは次のn回数以上繰り返されません。 （以来j >= 0） - したがって、「新しいプログラム」は古いプログラムよりも「良くない」（上限に関して）。

単純化されたプログラム の複雑さ ループ 1 とループ 3 はそれぞれ何度も繰り返され、ループ2 は正確に 1 回 繰り返されるため
、上記のプログラムの全体的な複雑さはです。内側のループごとに 1 つのコマンドが実行されると仮定すると、実行されるコマンドの総数は になります。O(n^2)n
n^2

結論：
新しいプログラムはn^2（仮定によると）「ops」を実行しており、元のプログラムは「新しいプログラムよりも悪くない」ため、ステップを実行していT(n) <= n^2ます。 ビッグ O 表記の定義(c=1 で N ごと) から、プログラムは次のように結論付けることができます
。O(n^2)

于 2012-10-21T09:51:57.353 に答える