実行時間の複雑さ

Question

私は次のコードがn^3の大きなシータであると信じています、これは正しいですか？

for (int i = 0; i < n; i ++) 
{ // A is an array of integers 
    if (A[i] == 0) { 
     for (int j = 0; j <= i; j++) { 
      if (A[i] == 0) { 
      for (int k = 0; k <= j; k++) { 
       A[i] = 1; 
      } 
      } 
     } 
    } 
} 

そして、forループ（N）回を記録実行します、そしてfuncが最大n再帰呼び出しで動作しますので、次の（n）がnlogの大きなシータ

for (int i = 1; i < n; i *= 2) 
{ 
    func(i); 
} 

void func(int x) { 
    if (x <= 1) return; 
    func(x-1); 
} 

です。

ありがとうございました！

Answer 1

あなたの直感は正しいようです。最初のビットでは、入力に非ゼロ要素が含まれている場合、時間の複雑さはbig-theta（n）に低下します。チェックを外すと、間違いなく大きなシータ（n^3）になります。

Answer 2

2番目のスニペットについては正しいですが、最初はBig-Theta(n^3)ではありません。それもO(n^3)ではありません！重要なのは、各iについて、最も内側のループは多くてもを実行します。

明らかに、最悪の場合は、配列に0しか含まれていない場合です。しかし、A[i]は最も内側のループの最初のパスで1に設定され、同じiのすべての次のチェックはと評価され、iが増分されるまで最も内側のループは実行されません。したがって、合計で1 + 2 + 3 + .. + n = n * (n + 1)/2回の反復があるため、最初のスニペットの時間複雑度はO(n^2)です。

希望すると便利です。