尝试计算以下代码的时间复杂度

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++;
        }
    }
}

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

并且对于从 0 到 n-1 的每个 n，外循环运行 n 次。总结为：

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

实际上是 O(n^5)。

数学符号为：

尝试计算以下代码的时间复杂度

Trying to calculate the time complexity of the following piece of code

java

algorithm

complexity-theory

time-complexity