代码的计算复杂度

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)²)。我的回答正确吗？谢谢。

- user2110714

Answer 1

内部循环的复杂度为O(n)。中间循环的复杂度为O(i/4)，进而为O(i)。最外层循环的复杂度为O(log₄n)。因此，代码的总复杂度为O(n.i.log₄n)，即等于O(n.(log₄n)²)。

- Deepu

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²)。

- Mohamed Ennahdi El Idrissi