1
私は学校で時間の複雑さをする方法を学び、教授はいくつかの例をアップロードしました。下の最初の例では、答えはO（n^3）であると考えられていますが、わかりません。Big O - これらのアルゴリズムの時間の複雑さを理解していませんか？
public static int fragment1 (int n)
{
int sum = 0;
for (int i = 1; i <= n*n; i++)
for (int j = 0; j*j < i; j++) sum++;
return sum;
} // end fragment1
私はループのために最初のを見て、それがn^2回実行していることがわかり、問題は、その後、forループの内側でもあるN^2試みます。私がO（n^4）を得たときに追加されます。
public static int fragment5 (int n)
{
int sum = 0;
for(int i=0; i < n*n*n; i++)
{
if(i%(n*n) == 0) {
for(int j=i*i; j > 0; j--)
sum++;
} // if
else
{
for(int k=0; k < i: k++)
sum++;
} // else
} // outer loop
}
上記の問題については、答えはO（n^7）である必要があります。私はそれを試みたとき、私は得た：最初のループ実行n^3回、内部ループn^3 * n^3 = n^6と、^10）。誰かが私に上記の問題に関するヒントを与えることができますか？私はそれがこの1つになると無知に感じ、私はこれまでのところ他の問題を抱えてきました。
は、nは、jは何とか関連しますか？問題の追加情報はありますか？外側ループはn^2回実行されますが、内側ループはj^2回実行されます。 n == j以外の場合、n^4に結合するとは言えません。 – Ali
これらは深刻なアルゴリズムではありません。これらは複雑さについて教えてくれるちょっとしたことですが、あなた自身で学ぶ必要があります。あなたを助けることができる助手がいると確信しています。例1の場合は、 "inner forループもn^2"と言ってください - 間違っています。ループが実際に言うことをよく見てください。 'j
Q1についてのより大きいヒント：x = 1からn^2への統合x ^（1/2）を試す Q2の場合：最悪の場合は 'if'ブロックにあり、 'if'条件が真となる回数を考えることで' j'ループが起こる – shole