このトリプルループの複雑さ？

for(i=1;i<=2237;i++) 
{ 
    for(j=i+1;j<=2237;j++) 
    { 
     for(k=1;k*(i*i+j*j)<=5000000;k++) 
     { 
      a[k*(i*i+j*j)]=1; 
     } 
    } 
}

ここで5 * 10^6はnと仮定でき、2237はsqrt（n）で近似されます。私は外側の2つのループの複雑さを理解することができます、それは私が混乱している最も内側のループです。このトリプルループの複雑さ？

可変入力のサイズがないため、O（1）です。はい、定数は高いですが、それにもかかわらず一定です。 –

これは、 '2237'を' n'で置き換えると、あなたの内部ループはO（n^2）回繰り返され、そして ' kループはn *（n^2 + n^2）を反復する。すなわちO（n^3）である。全体の複雑さはO（n^5）でなければなりません。（しかし直感的には、それを証明する方法はありません） –

上記のコードスニペットで述べたように、5 * 10^6はnで置き換えられ、次に2237はsqrt（n）で置き換えられます。 –

入力は最内ループにおける反復回数（あなたがそれを説明しているように）指示した場合：

を外側のループはsqrt(N)回実行し、その後、中間ループの各反復で平均sqrt(N)/2上で実行され外側のループ。次に、内側のループは、中間ループの各反復でN回実行されます。

ので.... sqrt(N) * sqrt(N)/2 * N == (N-Squared/2)

したがって

O(N-Squared)

入力は、最も外側のループで反復回数を指示した場合、最も内側のループの繰り返し回数は、外側の対話数の二乗値が常にあるように：

`N * N/2 * N-Squared = N**4 (N to the power of 4)`. Hence, `O(N**4)`

2016-12-06 07:21:00 selbie

答えて