c - 三重嵌套循环的时间复杂度？

Question

for(i=0; i<n; i++)
{
    a[i]=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            a=3;
        }
    }
}

这是一个三重嵌套循环。我的书说运行时间是：O(N) + O(N^2) = O(N^2)

不应该是 O(N^3) 吗？所有 3 个循环都相互依赖。它将运行 N*N*N 次。

Answer 1

这是因为循环#1和循环在比较期间#2使用相同的计数变量。i

在使用 的第二个循环结束时i， 的值为ni ，这也使其脱离了外循环。一个循环在那里完全是多余的。

---

#include <stdio.h>
int main(){
    int x = 0;
    int n = 20;
    int i, j;
    for(i=0; i<n; i++) //this loop runs once
    {
        for(i=0; i<n; i++) //this loop runs n times
        {
            for(j=0; j<n; j++) //this loop also runs n times
            {
                x++;
            }
        }
    }
    printf("%d", x);
}

O(N^2)整个运行的时间到了。

例子

Answer 2

我不认为他们是你书中的错误。您必须更深入地查看您的代码：前两个循环使用相同的变量进行循环，所以会发生以下情况：

在第一个括号之后， i 等于 0，然后进入第二个循环。当第二个循环结束时，第一个循环将结束，因为两个循环都使用条件 i

实际上我看不出 O(N) 来自哪里，但全局复杂度应该是 O(N^2)

Answer 3

这不是 n^3，因为变量 i 在内部循环中被重用，使其成为 n^2。不过，不确定这本书在哪里得到 O(n)。