は

Question

は、私が理解スニペットそのような単純な文：

int x = 5; // is 1 or O(1) 

そして、whileループのような単一のためと

while(i<); // is n+1 or O(n) 

と同じforループ（依存）しばらくネストされたかのようなforループで ：

for(int i = 0; i<n; i++){ // this is n + 1 
for(int j = 0; j<n; j++){ // this is (n+1)*n, total = O(n^2) 
} 

はまた、いつでも我々はそれがそうでエフェクトlog_3（n）と3倍、log_2（n）のだ倍増効果を持っています。また、制御変数が半分または四分されている場合は、log_2（n）またはlog_4（n）のいずれかになります。

しかし、私ははるかに複雑な例を扱っています。これらの例をどのように理解するか私は答えを持っている私はちょうど試験紙にそれらを働かせる方法を知らない。

例1：

for (i = 1; i < (n*n+3*n+17)/4 ; i += 1) 
System.out.println("Sunshine"); 

例2：

for (i = 0; i < n; i++) 
if (i % 2 == 0) // very confused by what mod would do to runtime 
for (j = 0; j < n; j++) 
System.out.print("Bacon"); 
else 
for (j = 0; j < n * n; j++) 
System.out.println("Ocean"); 

例3：

for (i = 1; i <= 10000 * n: i *= 2) 
x += 1; 

は

Answer 1

例1は、用語(n*n+3*n+17)とtherefで囲まれているありがとう鉱石はO(n^2)でなければなりません。これがO(n^2)の理由は、式の中で最大の、したがって支配的な用語がn^2であるためです。

2番目の例は少し難解です。 iの外側ループはn回繰り返されますが、内部で実行される内容は、その値がiであるかどうかによって異なります。偶数の場合でも、nを超える別のループが発生しますが、n^2の奇数ループが発生します。奇妙なケースが最終的に実行時間を支配するので、例2はO(n^3)でなければなりません。

第3の例は、10000*nを打つまで反復するが、各ステップでループカウンタiを2倍にすることによって繰り返す。これはO(lgn)のパフォーマンスを持ちます（lgはログベース2を意味します）。n=32に到達し、それぞれi=1から2倍になりたかったとします。まあ、2,4,8,16,32、つまり6ステップとなり、それはlg(32)として成長します。