loops - 如何从外循环 : 中找到依赖于 "i"的内循环的时间复杂度

Question

如何找到依赖于 i 的内循环的时间复杂度从外部循环，例如:

int sum = 0;
for(int i = 0; i < n * n; i++) {
    for(int j = n - 1; j >= n - 1 - i; j--) {
        sum = i + j;
        System.out.println(sum);
    }
}

我很难弄清楚它的时间复杂度。我知道如果有i我们使用求和规则，但在这种情况下会怎样？

Answer 1

内循环在开始时执行 1 次迭代，增加到 n*n迭代结束。

i       iterations of inner loop
-       ------------------------
0       1
1       2
2       3
...
n*n-2   n*n-1
n*n-1   n*n

内循环的总迭代次数是这些的总和:



或者



因此时间复杂度为 Θ(n4)。