计算给定Java测试代码test方法关于变量n的时间复杂度

首先给出待分析的代码：

class test_case
{
  public static void test(int n)
  {
    int sum=0;int i;
    for(i=1;i<n;i++)
    {
       for(;i<n*n;i++)
       {
          sum=sum+i;
       }
    }
    system.out.println(sum);
  }
}

复杂度分析过程 #

• 首先注意变量i是在两个for循环外部统一声明的，两个循环共享同一个计数变量，而非外层循环的局部变量
• 当n>1时，外层for循环初始化i=1，第一次判断i <n条件成立，进入循环体触发内层循环
• 内层for循环没有重新初始化i，直接从当前i=1开始执行，每次循环i自增1，直到i >= n*n时退出，此时i的值已经为n²，远大于外层循环的终止阈值n
• 内层循环退出后，外层for循环执行自增逻辑，i变为n²+1，再次判断i <n时条件不成立，外层循环直接终止，不会进入第二次循环
• 总循环执行次数为n²-1次，忽略常数项后，最终渐近时间复杂度为O(n²)

补充边界场景：当n<=1时，外层循环首次判断就不成立，方法直接执行打印语句，时间复杂度为O(1)，该场景不影响渐近上界的结果。

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