如何计算该类双层嵌套for循环的时间复杂度

结论 #

该段循环的时间复杂度为O(n²)，其中n为数组array的长度。
对应代码如下：

for (int i = 0; i < array.length; i++){
   for(int j = i + 1; j < arrray.length; j++){
   // 若干O(1)常量级操作
   }
}

计算步骤 #

计算前先明确基础前提：

• 设数组长度为n，即n = array.length
• 内层循环中的操作是常量级操作，单次执行耗时固定，不会随数组长度变化
  逐轮统计循环执行次数：
• 外层循环的游标i从0递增到n-1，总共会跑n轮
• 每一轮外层循环里，内层循环的起点是i+1，终点是数组末尾，因此每轮内层循环的执行次数会随着i增大逐轮减1：
  • i=0时，j从1遍历到n-1，共执行n-1次
  • i=1时，j从2遍历到n-1，共执行n-2次
  • i=2时，j从3遍历到n-1，共执行n-3次
  • ……
  • i = n-2时，j从n-1遍历到n-1，共执行1次
  • i = n-1时，j初始值为n，不满足小于数组长度的判断条件，执行0次
    把所有轮次的执行次数加总，就是标准的等差数列求和：
    总执行次数 = (n-1) + (n-2) + …… + 1 + 0 = n*(n-1)/2 = (n² - n)/2
    按照大O复杂度的计算规则，我们只保留表达式里的最高阶项，去掉常数系数和低阶项，最终最高阶项为n²，因此时间复杂度为O(n²)。

这类循环本质是遍历数组中所有满足i<j的无序元素对，无序对的组合总数为组合数C(n,2)，和上述求和结果完全一致，也可以直接通过组合数逻辑快速得到复杂度结果。

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