3

次のアルゴリズムの時間計算量を知りたいです。一見したところ、時間の複雑さは O(n^5) のように見えます。これは、私がインターネットで見たサイトの大部分で言及されていることです。しかし、注意深く分析すると、別の答えが得られるようです。コードは次のとおりです。

public void fun(int n)
{
   int i,j,k,sum=0;
   for(i=0;i<n;i++)
   {
       for(j=0;j<i*i;j++)
       {
            if(j%i==0)
            {
                for(k=0;k<j;k++)
                sum++;
            }
       }
   }
}
4

1 に答える 1

2

（それぞれの個別の）時間j%i c== 0を生成することに注意してください-したがって、内側のループは「外側の」反復ごとにそれ自体を繰り返します。true O(i)iO(i)

したがって、複雑さはO(n*n^2 + n*n^3) = O(n^4)

説明:
O(n*n^2) if 条件の評価に関係なく繰り返される「中間ループ」用です。それは、次のO(n^3)ようになるからです。1 + 4 + 9 + 16 + ... + n^2これは、二乗和であり、 ですO(n^3)。
O(n*n^3)少しトリッキーです：

各 についてi、各内部ループはi回数を繰り返すため、それぞれについて次のようにiなります i + 2i + 3i + ... + (i-1)i。 内部ループの総繰り返し回数。i(1 + 2 + ... + i-1)実際にどちらがであるかは簡単にわかりO(i^3)ます。

これで、それぞれについて発生するためi、合計の複雑さは次のようになります (形式的ではなく、直感的なものです):O(1^3) + O(2^3) + ... + O(n^3)これは、立方級数の合計O(n^4)からのものです

結論:
コールド分析で示されている可能性がありますがO(n^5)、内側のループは中央のループの反復ごとに繰り返されないため、全体の複雑さは次のとおりです。O(n^4)

于 2012-11-26T09:48:52.377 に答える