Node.js嵌套双层for循环代码的时间复杂度是否为O(N²)？

时间复杂度判断结论 #

你认为这段代码时间复杂度为O(N²)的理解是正确的，该结论对应算法的最坏时间复杂度场景，具体推导逻辑如下：

对应参考代码 #

const arr = [{ key1: 2 }, { key1: 7 }, { key1: 11 }, { key1: 15 }];
const k = 9;
let valueSet = new Set(arr.flatMap((x) => Object.values(x)));
let valueArray = [...valueSet];

let indices;
let isFound = false;
// valueArray.forEach((v1, i1) => {
for (let i1 = 0; i1 < valueArray.length && !isFound; i1++) {
  for (let i2 = i1 + 1; i2 < valueArray.length && !isFound; i2++) {
    if ((valueArray[i1] + valueArray[i2]) === k) {
      //Return the Indices
      indices = [i1, i2];
      isFound = true;;
    }
  }
}
console.log(indices);

推导说明 #

我们先定义变量：设valueArray的长度为N（也就是原数组所有对象值去重后的元素总数）

• 最坏场景为：数组中不存在和为k的元素对，或者符合要求的元素对在遍历的最后位置才出现，此时两层循环都需要接近跑满：
  外层循环要执行N次左右，内层循环每次从i1+1开始遍历，总遍历次数为N + (N-1) + (N-2) + ... +1 = N*(N-1)/2，忽略常数项和低阶项后，时间复杂度为O(N²)
• 额外细节补充：
  • 代码里的isFound提前终止逻辑只能优化最好和平均情况的实际运行耗时，不会改变最坏场景下的复杂度量级
  • 代码前半段flatMap提取值、Set去重、转数组的操作时间复杂度为O(M)，M为原arr数组长度，线性复杂度远低于平方级，不会影响整体复杂度量级

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