为何两段相似Java代码时间复杂度分别为O(n²)和O(n³)？

第一段代码：时间复杂度O(n²) #

你误以为外层循环会执行n次，但核心问题在于内外层循环共用了同一个变量i：

• 外层循环初始化i=1，第一次进入循环体后，直接进入内层循环。
• 内层循环的条件是i < n*n，每次循环i都会自增，直到i达到n*n时，内层循环结束。
• 这时候回到外层循环的判断条件i <n，此时i已经是n*n（远大于n），外层循环直接终止，不会再执行第二次。
• 所以整个函数的核心操作sum+=1总共执行了n²次，时间复杂度为O(n²)。

代码示例：

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³) #

这段代码的内外层循环用了不同的变量（外层i，内层j），相互独立：

• 外层循环从i=1到i<n，总共执行n次（时间复杂度分析中忽略常数项，n-1次等价于n次）。
• 每一次外层循环里，内层循环都会从j=0到j<n*n，执行n²次。
• 核心操作sum+=1的总执行次数是n * n² =n³，时间复杂度为O(n³)。

代码示例：

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

内容的提问来源于stack exchange，提问作者Coder1234