array.length()为线性复杂度时，对应双层循环代码的时间复杂度是多少

核心结论 #

在array.length()每次调用的时间复杂度为O(N)（N为数组实际长度）的前提下，这段代码的整体时间复杂度为O(N³)。

推导过程 #

我们先明确两个默认前提：

• 代码运行全程没有修改数组长度，每次array.length()返回的值恒为N
• print()操作的时间复杂度为O(1)
  接下来分层统计耗时：

1. 外层循环的length调用耗时
   外层循环的条件判断i < array.length()会在每次迭代前执行，直到i=N时判断失败退出，共执行N+1次，单次调用耗时O(N)，这部分总耗时为(N+1)*O(N) = O(N²)。
2. 内层循环的length调用耗时
   每次外层循环迭代（共N次）都会触发一轮完整的内层循环，每轮内层循环的条件判断j < array.length()同样要执行N+1次，总调用次数为N*(N+1)，单次调用耗时O(N)，这部分总耗时为N*(N+1)*O(N) = O(N³)。
3. print操作耗时
   两层循环共执行N*N次print()，总耗时为O(N²)，远小于O(N³)可以忽略。
   将所有部分的耗时合并取最高阶，最终整体时间复杂度为O(N³)。

补充说明 #

如果我们在循环前先把数组长度缓存为局部变量：

void printPairs(int[] array) {
   int len = array.length(); // 仅调用1次length()，耗时O(N)
   for (int i = 0; i < len; i++) {
       for (int j = 0; j < len; j++){
          print(array[i], array[j])
       }
   }
}

此时length()仅调用1次，耗时O(N)，加上两层循环的*O(N²)*操作，整体复杂度会降到O(N²)，和Java中length为预存常量的场景结果一致。

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