私はこれらのコードフラグメントで迷っていて、他の類似した例が見つからない場合があります。私はそれを推測しているコードフラグメントのBig-Oh表記
//Code fragment 1
sum = 0;
for(i = 0;i < n; i++)
for(J=1;j<i*i;J++)
for(K=0;k<j;k++)
sum++;
は、フラグメント1
//Code fragment 2
sum = 0;
for(1; i < n; i++)
for (j =1;,j < i * i; j++)
if(j % i == 0)
for(k = 0; k < j; k++)
sum++;
私は非常にこの1に失われていますのためにはO（n^4）です。 if文がループにどのような影響を与えるかはわかりません。
時間のお手伝いをしていただきありがとうございます。
最初のものは実際にはO(n^5)です。 sum++行は1^4回実行され、次に2^4回実行され、次に3^4回実行されます。度数の和は、n^(k+1)（例えば、Faulhaber's formula参照）であるので、n^5である。
第2の場合、内部ループはjがiの倍数であるときにのみ実行されるということです。したがって、2番目のループは、for (j = 1; j < i * i; j+=i)と書くこともできます。しかしこれはfor (j = 1; j < i; j++)と同じです。今度は、4のべき乗ではなく、一連のキューブがあります。したがって、最高期限はn^4です。計算することがとても便利sumで
、あなたはn=10、n=50のためにこれらを実行して、というように、ちょうどOのどの（N^2）見て、O（N^3）ができ、O（N^4） 、O（N^6）はより良い一致です。 （最も内側のループのインデックスもがn * n ...に実行されることに注意してください）
あなたはこの質問にうまく答えていません。 – TaslemGuy
+1：それはまさに私がコードに関する私の仮定を確認するために行うことです。 –
最初に、私は最初のシナリオの仮定に同意します。ここに私の2番目の内訳です。
Ifステートメントは、i * iの奇数値がi * iを分解することができる素数の第3の内側ループにのみつながるため、最後のループは半分の時間しか実行しません。私たちは定数を無視するので、O（n^3）を見ていると思います。
最初のフラグメントが実際にO（n^5）であることはかなり確信しています。
ため：iは、Nの半分実際には倍
n、
i^2倍であり、これは（平均で、私の場合、各和を2N、対応するNXあるxについて以降）従ってn^2/4回。再び（回）
、回、
とあなたは：N * Aを、またはN * N * N/4 * N * N/4 = N^5月16日、これは、n回繰り返されます
：またはO（N^5）
私は、第二は、（4）、ので、Oであると考えています。
そして、それをn * n回繰り返されます、（文字通りN * N/4ではなく、O表記）
のみ1/nは（私は私が得たか覚えていない場合で通すされていますこれ）
n * nを繰り返します。
したがって、n * n * n * n * n/n = n^4です。
-1：推測は非常に有用な答えではありません。間違った推測はあまり有用ではありません！ –
私はそれが推測だとは決して言わなかった。私はそれがどのように得られたかを示した。正式にこれを教えたことはありませんので、私の理解が正しいかどうかはわかりません。あなたはちょうど私が私の答えを得た方法を正確に示したにもかかわらず、私が間違っていることをちょうど "推測"しました。 – TaslemGuy
Downvoteが取り消されました（元の質問を正しく読むことができなかったため）。 –
O（n^4）ですか？私はそれがO（n^5）だとはっきりと確信していますが、私が確信するまであなたをマークするつもりはありません。 – TaslemGuy
@Taslem：はい。内部ループは 'i * 'の各値に対して' i * i * i'回繰り返す。 –
@Taslem：これは恥ずかしいです！内部ループを「j」ではなく「i」まで反復して誤読しました。あなたは実際に正しいです、そして、私は実際には間違っています。それに応じて私の答えを更新する。多くの謝罪。 （あなたの答えにダミーの編集を行う場合、私はdownvoteを削除することができます）。 –