在查找嵌套循环的时间复杂度时，即使内部循环停止运行，是否也要考虑外部循环

Question

请考虑以下代码：

int sum = 0;
for(int i = 0; i < N*N; i++)
{
    for(int j = i; j < N; j++)
    {
        sum++;
        System.out.println(sum);
    }
}

我一直都知道，找到时间复杂度就是找到内部循环将被执行多少次。但是在上面的代码中，内部循环将继续运行，直到 i 到达 N。当 i 超过 N 时，内部循环不再更新 sum 的值。但是外部循环将继续运行直到完成。

因此，由于内部循环一直运行到我到达 N，那么这段代码的时间复杂度不应该是 O（N^2）吗？解说时间复杂度为 O（N^3）。

Answer 1

O（n^3） 是正确的！

对于外循环(i)的每次迭代，内循环(j)将迭代N次，然后退出循环。外部循环将i=0增加到i=1然后再次执行内部循环（再迭代 N 次），并将继续这样做直到 i = N*N 。因此，您可以说内循环每次外循环迭代 N 次。

外部循环从 i=0 开始并迭代 N*N 次。

如果内循环每次外循环循环 N 次，外循环迭代 N

*N 次，则内循环的总迭代次数为：

 (# of inner iterations per outer iteration) * (# of outer iterations)
 = (N) * (N*N)
 = N^3