我仍然很困惑时间复杂度是如何计算的

Question

对于下面的代码，我们说时间复杂度为O(n^2)

如果内循环运行n*n次外循环运行n次，不应该是O(n^3)

public static void func(int n){
int sum=0;

for(int i=1;i<n;i++) {
for(;i<n*n;i++)
sum+=1;

System.out.println(sum):

}
}

但同样对于下面的代码，时间复杂度为O(n^3)

public static void func(int n) {
int sum=0;

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

那么有人能解释一下原因吗?

我觉得这种情况下的时间复杂度应该是O(n^3)，但事实并非如此。

Answer 1

在第二个例子中你是对的，时间复杂度是O(n^3)，因为外部循环迭代n-1次，内部循环迭代n^2，结果是(n-1) * n^2或n^3 - n^2，所以考虑到常数时间操作，复杂度可以表示为O(n^3)。

然而，在第一个例子中，复杂度仅为O(n^2)，这反映了内部循环的迭代次数，因为外部循环总是只执行一次。这是因为在外部循环的第一次迭代之后，内部循环将以i=n*n-1退出，外部循环超出了第一个循环的边界(i <n)>

Answer 2

第一个代码的时间复杂度为O(n^2)，因为我们在两个循环中使用相同的迭代器i，所以它只会在i<n从外循环时运行，无论我们是否将i<n^3 or i<n^10放入内循环，它都会在变成i=n时退出两个循环。

,第二个循环的时间复杂度肯定是O(n^3)