機能とループ時間の複雑さのためにネストされたが、この場合

for(i = 1; i < a; i++){ 
    for(j = 1; j < b; j = j + 3){ 
     if((i+j) % 2 == 0) 
      Func() 
} 
}

を呼び出して、私はそれがO(a*b)とTheta(a*b)あると思いました。機能とループ時間の複雑さのためにネストされたが、この場合

複雑さを正しく分析しましたか？ iが正、j % 2非負あるときにi + j % 2が正あるので、

2017-01-17 NoSleep

え、* 'i'は、* *正である' jは％2 'は非負*であるを持っています'i + j％2'は* positive *であり、* never *は' 0'と等しくなります。したがって、 'Func（）'は決して実行されません。 '（i + j）％2 == 0'を意味しますか？ –

これは（i + j）％2 == 0です。混乱して申し訳ありません – NoSleep

まず第一に、あなたは、おそらく、代わりに

if (i + j % 2 == 0)

の

if ((i + j) % 2 == 0)

を意味し、したがってi + j % 2neverはゼロと等しくなります。Func()はまったく実行されません。

あなたの答えが正しいものである：複雑さは

a *  // from the first loop 
b/3 * // from the second loop 
1  // from the condition (it always true)

ですから、

Θ(a * b/3 * 1) = Θ(ab)

2017-01-17 15:53:16

答えて