与えられた数nの製品の数を見つけるためのコードがあります。複雑さはsqrt（n ^ 3）だと思いますが、n ^ 2だと思う人もいます。コードは次のとおりです。
int f(int n)
{
int i,j,k,p,r=0;
k=sqrt(n);
p=n/2;
for (i=2; i<=p; i++)
for(j=2; j<=k; j++)
if(i*j==n)
r++;
return r;
}
私の論理の背後にある理由は次のとおりです。
T = C1 +（n / 2-1）C2 +（n / 2-1）（sqrt（n）-1）C3
でも完全にはわかりません
（内側のループが言うことを意味していると仮定するj<=kのではなくi<=k。）
あなたの論理と答えは両方とも正しいです（大きな意味で）。
これを見る別の方法は、外側のループがO(n/2)（と同じO(n)）であり、内側のループがであるということO(sqrt(n))です。2つを乗算すると、が得O(n*sqrt(n))られO(sqrt(n^3))ます。これは代数的に。と同等です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加