数组for循环内调用include方法的时间复杂度是O(n)吗？附去重代码疑问

1. 数组includes方法的时间复杂度 #

数组的includes方法会从数组起始位置开始逐个比对元素，直到找到目标值或遍历完整个数组，因此它的时间复杂度是O(k)，其中k是调用该方法的数组的长度。

2. 统计唯一值代码的时间复杂度 #

先看你提供的代码：

function countUniqueValues(array) {
  let uniqueArray = []; //constant
  for (let i = 0; i < array.length; i++) { //n time
    if (uniqueArray.includes(array[i])) { //n time 
    } else {
      uniqueArray.push(array[i]); //constant time
    }
    console.log(i) //constant
    console.log(uniqueArray) //constant
  }
  console.log(uniqueArray.length);
  return uniqueArray.length;
}
countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]);

这段代码的时间复杂度是O(n²)，原因如下：

• 外层for循环执行n次（n为输入数组array的长度）。
• 每次循环中的uniqueArray.includes(array[i])，在最坏场景（输入数组所有元素均唯一）下，uniqueArray的长度会从1逐步增长到n，每次includes的遍历次数分别为1、2、3...n次。
• 总遍历次数为1+2+...+n = n(n+1)/2，属于二次方级别的时间复杂度，即O(n²)。

如果想将时间复杂度优化到O(n)，可以用JavaScript的Set（哈希表结构）来存储唯一值，因为Set的查找操作是O(1)级别的：

function countUniqueValues(array) {
  const uniqueSet = new Set(array);
  return uniqueSet.size;
}

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