c - ネストされた for ループの複雑さ

Question

以下のコードの複雑さを知りたいです。このコードを使用して、並べ替えを使用して配列内で 2 番目に高い要素を見つけました。

for(i=0;i<2;i++)
{
   for(j=0;j<n;j++)
   {
     //some code
   }
}

複雑さは O(2n) または O(n ² ) ですか?

Answer 1

それは非常に広大なトピックです。私はあなたにそれをもたらすために全力を尽くしています。それについては、いくつかの良い本を参照してください。での私のおすすめCoreman。

複雑さ :

forループの基本構造は

for(initialization;condition;updation)

更新では値を更新しているため、基本的には条件までループを繰り返しています。

だからそれは好きです

n*(n+1)/2

これは基本的に O(n^2) for ループの場合です。

複雑さの見積もり:

アルゴリズムの複雑さの式を求めるのは簡単ではない場合があります。このような場合は、実験によって推定できる場合があります。カウント変数をプログラムに追加し、重要な操作が実行されたときにインクリメントされ、最終的な合計が出力されます。実行時間は、ストップウォッチまたはルーチンを呼び出してコンピューター システムの時計を出力することで測定することもできます。複雑さは、そのような測定値が問題のサイズによってどのように変化するかを調べることで推測できます。

プログラムまたは操作のタイミングの精度は、多くの実行のタイミングを (おそらくループで) 計り、合計所要時間をその数で割ることによって改善できます。時分割のコンピュータは、多くの人が同時に使用します。プログラムの所要時間は、システムの負荷によって異なります。したがって、共有マシンで実行されるタイミングは、経過時間ではなく、調査中の特定のプログラムに費やされた中央処理装置の時間に基づいている必要があります。

シリーズ内の隣接する用語間の違いを調べると、シリーズを定義する基礎となる関数の形式を示すことができます。線形関数は、と の間にT(n)=a*n+b一定の差を生じさせます。T(n)T(n-1)

D1(n) = T(n)-T(n-1) = a*n+b-a*(n-1)-b = a

二次関数T(n)=a*n2+b*n+cは、線形の一次差分を生じさせます。

D1(n) = T(n)-T(n-1) = a*n2+b*n+c-a*(n-1)2-b*(n-1)-c = 2a*n-a+b

これにより、一定の二次差が生じD2(n) = D1(n)-D1(n-1)ます。一般に、次数 d の多項式は、一定dth-orderの差によって明らかにされます。

Answer 2

解決策を知る最善の方法は、表を描くことです。

Iteration |   i    |   j
----------+--------+-------
    0     |   0    |   0
    0     |   0    |   1
    0     |   0    |   2
    0     |  ...   |  ... 
    0     |  ...   |  ...
    0     |  ...   | n - 1
    1     |   1    |   0
    1     |   1    |   1
    1     |  ...   |  ... 
    1     |  ...   |  ...
    1     |  ...   | n - 1

何回実行されますか？それが答えです..
直感を持ちたい場合は、いくつかをn選択し、例を実行する必要があります..次に、別のものを選択しnて、何が得られるかを確認します。最終的に、答えが何であるかを結論付けます。

Answer 3

「あるコード」が o(1) を実行する場合、このコードの複雑さは O(2n) です。

これは、内部コードが o(n) の複雑さであり、このループを 2 回実行するためです。それならO(2n)

Answer 4

Big Oh 表記法は大きさの推定値の順序を示します。定数の違いは実際にはアルゴリズムの大きさに影響しないため、O(2n) = 2O(n) = (n) になります。

1000 >> 10 = 5 と同様です。つまり、1000 は 10 よりもはるかに大きく、10 は 5 の値の 2 倍ですが、10 の場合と同じように 5 よりも「大きく」なります。