algorithm - コードの計算の複雑さ

Question

私はプログラムを持っていて、その複雑さを計算しようとしています。間違えないようにしたい

for(int i=4; i<=n; i=i*4)
{
    cout<<"counter for first loop: "<<++count1<<endl;
    for(int j=i;j>=0;j=j-4)
    {
        cout<<"counter for second loop: "<<++count2<<endl;
        for(int k=0;k<=n;k++)
        {
            cout<<"counter for third loop: "<<++count3<<endl;
        }
    }
}

ここで、3番目のループの複雑さはO（n）であり、2番目のループと合わせて複雑さはO（n.log ₄ i）になり、プログラム全体の複雑さはO（n。（log ₄ i）²）になります。 。私は私の答えに正しいですか？ありがとう

Answer 1

最も内側のループの複雑さは O(n) です。真ん中の複雑さは O(i/4) で、これは O(i) です。最も外側のループの複雑さは O(log ₄ n) です。コードの全体的な複雑さは、 O (n.(log ₄ n) ² )に等しいO(nilog ₄ n)です。

Answer 2

次のように正式に進めることができます。

このフラグメントの実行:

sum = 0;
for( i = 4 ;  i <= n;  i = i * 4 ) {
    for( j = i ; j >= 0 ; j = j - 4 ) {
        for( k = 0 ; k <= n ; k ++ ) {
            sum ++;
        }
    }
}

私達は手に入れました：

上記の式と完全に一致する結果。

その上、両方の内側のループのランタイムは O(n) ... つまり、一緒に実行すると O(n²) になります。