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

这里，第三个循环的复杂度是O(n)，那么加上第二个循环，复杂度就变成了O(n.log₄i)，整个程序的复杂度是O (n.(log₄i)²)。我的回答对吗？谢谢

Answer 1

最内层循环的复杂度为 O(n)。中间一个的复杂度是 O(i/4)，它又是 O(i)。最外层循环的复杂度为 O(log₄n)。代码的总复杂度为 O(n.i.log₄n) 等于 O (n.(log₄n)²).