嵌套数组场景下代码时间复杂度疑问：O(n²)还是O(n)？

嘿，我来帮你把这个时间复杂度的问题掰扯清楚！

首先得明确核心：你的代码结构是外层循环调用内层循环函数，而array2嵌套在array1中——这个嵌套关系直接决定了时间复杂度的结果，主要分两种常见场景：

1. 最典型的嵌套场景：O(n²) #

如果array1是一个n×n的二维数组（也就是外层有n个元素，每个外层元素对应的内层array2也有n个元素），那时间复杂度就是O(n²)。

举个具体的代码例子：

function function1() {
  const array1 = new Array(100).fill().map(() => new Array(100).fill(0)); // 100x100的二维数组
  for (let i = 0; i < array1.length; i++) { // 外层循环100次
    function2(array1[i]);
  }
}

function function2(array2) {
  for (let j = 0; j < array2.length; j++) { // 每次内层循环100次
    // 执行某个操作，比如访问array2[j]
  }
}

这里外层循环跑n次，每次调用function2都会触发n次内层循环，总操作次数是n * n = n²。当n不断增大时，总操作次数的增长趋势是平方级的，所以时间复杂度为O(n²)。

2. 特殊的“扁平化嵌套”场景：O(n) #

如果array2嵌套在array1中，但所有内层array2的总元素个数是O(n)（比如外层array1有k个元素，但所有内层数组的元素加起来总共是n，且n和k是同阶的），那时间复杂度就是O(n)。

比如这个例子：

function function1() {
  const array1 = [[1,2], [3], [4,5,6], [7]]; // 总元素数是7
  for (let i = 0; i < array1.length; i++) { // 外层循环4次
    function2(array1[i]);
  }
}

function function2(array2) {
  for (let j = 0; j < array2.length; j++) { // 内层循环次数分别是2、1、3、1
    // 执行操作
  }
}

这里总操作次数是2+1+3+1=7，也就是等于所有内层元素的总数。如果这个总数是O(n)（比如当array1的规模扩大时，总元素数跟着线性增长），那时间复杂度就是O(n)。

一句话总结 #

• 若外层循环n次，每次内层循环也n次：O(n²)
• 若所有内层循环的总次数是线性的n：O(n)

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