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(nilog ₄ n) ，它等于 O (n.(log ₄ 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²)。