0

基本的に、操作カウントとBig-O表記を理解するのに苦労しています。これはおそらくコンピューター サイエンスで理解するのが難しい部分の 1 つであることは理解しており、苦労していることを認めざるを得ません。これらの例について誰か助けてくれませんか? Big-O とのさらなるヘルプ/リンクはありますか?

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

ここでは、複雑さは O(N²) - 2 次です。

int m = -9
for (j = 0; j < n; j+=5)
     {
     if (j<m)
          {
          for (k = 1; k <n; k*=3)
               {some code}
               }
     }

ここでは、O(N²) とも言います。最初のループは N を使用し、2 番目のループは N を使用するため、答えは O(N²) に等しい O(N*N) と言えます。

さらに理解を深めるための助けとアドバイスは素晴らしいでしょう!!

4

5 に答える 5

2

O(n^2)あなたが疑ったように、「一連のステートメント」が であると仮定すると、最初のものは確かに ですO(1)。

ただし、コードの 2 番目の部分はO(n)、条件j < mが満たされないためです。したがって、外側のループは実際には何もせずに反復するだけです。内側のループにも到達できません。

補足として、一部のコンパイラはO(1)、変数の終了値を設定するだけで、コードの 2 番目の部分を実行するように実際に最適化する場合がありますが、これは問題のポイントではありません。

于 2013-08-15T17:25:13.213 に答える
1

2 番目の例は複雑さO(N)です。

int m = -9
for (j = 0; j < n; j+=5)
{
    if (j<m)
    {
        // this never executes; m is negative and j is positive
    }
}
于 2013-08-15T17:27:41.130 に答える
0

最初の例: 内側のループは、i = 0 の場合は N 回、i = 1 の場合は N-1 回、というように実行されます... for ループが実行するステップの数を計算するだけです。

(N) + (N - 1) + (N - 2) + ... + 2 + 1

ステップ = N(N+1)/2 = (N^2 + N) / 2

  1. N <=> 1 |左を右に追加| => N+1
  2. (N - 1) <=> 2 |左を右に追加| => N+1
  3. (N - 2) <=> 3 |左を右に追加| => N+1 . . . N

Big-O 国家とはどういう意味ですか?

F(N) = O(G(N)) は、|F(N)|<= c*|G(N)| を意味します。ここで c > 0

これは、G(N) 関数が関数の成長率の上限であることを意味します。F(N) は G(N) より速く成長できませんでした。

于 2013-08-15T17:45:21.737 に答える
0

わかりました、さらに注意してください。アルゴリズムの紹介シリーズの 1 つの講義を受講することをお勧めします。これ以上探す必要はないと信じてください。 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

于 2013-08-16T13:15:31.000 に答える