java - 试图计算下面这段代码的时间复杂度

Question

下面这段代码的时间复杂度是O(n^5)多少？我的推理是外部for循环是O(n)，中间for循环是O(n^2)因为i的值是基于n的值，而内部for循环是O(n^2)因为j的值是基于if i^2的值，即基于 n^2 的值。

int x = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i * i; j++) {
        for (int k = 0; k < j; k++) {
            x++;
        }
    }
}

标签： javaalgorithmtime-complexitycomplexity-theory

Answer 1

那不是那么简单。x要确定复杂性，需要计算将增加多少倍。

The most inner loop runs `j` times.
The middle loop runs `i*i` times.
The outer loop runs n times.

让我们减少：

中间循环的复杂度是：

1+2+3+...+(i-1)+i+(i+1)+...+(i-1)*(i-1) = (i^2-2i+1)*i*i/2=(i^4-2i^3+i^2)/2

并且外部循环运行n时间为每个 n 从 0 到n-1。它总结为：

n^5/10 - n^4/2 + 5n^3/6 - n^2/2 + n/15

它实际上是O(n^5)。

数学符号是：