一段代码的计算复杂性

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;
        }
    }
}

这里,第三个循环的复杂度是O(n),然后与第二个循环一起,复杂度变为O(n.log ₄ i),整个程序的复杂度为O(n.(log ₄ i)²) .我的回答是对的？谢谢

Answer 1

最内层循环的复杂度是O(n)。中间的复杂度是O(i/4)，反过来就是O(i)。最外层循环的复杂度为 O(log ₄ n)。代码的总复杂度为 O(nilog ₄ n) ，等于 O (n.(log ₄ n) ² )。