以下函数的时间复杂度是多少 - O(n^3) 还是其他函数？

Question

是 O(n^3) 还是 O(n^4)？我不确定时间复杂度是O(n^3)还是O(n^4)

for(int i = 1; i <= n;i++)
{
    for(int j = 1; j <= i*i;j++)
    {
        if( j % i == 0)
        {
            for(int k = 0; k < j;k++){sum++;}
        } 
    }

}

Answer 1

外循环运行

n

次。

中间循环对于

each

外循环运行 i * i 次，并且

i

与

n

呈线性关系。这使得复杂性达到

n

的立方。

内部循环对于

each

中间循环(a) 运行 ^j 次，并且

j

与

n * n

呈线性关系。这使得复杂性达到

n

的五次方。

---

^(a) 由于 if 语句，它不会对

all

中间循环迭代执行此操作。

但是，如果您考虑到，对于 1000 的

n

，中间的循环将迭代一百万次。然后，

if

语句将删除每组 i 的

one

中间循环迭代的内部循环执行，从而有效地进行计数

i * (i - 1)

而不是

i * i

。这是 still 与

i

平方成线性关系，因此对复杂性没有影响。