是 array.include 方法在 for 循环内运行 o(n) 次的大 o 运行时吗？

Question

这是我的代码。用于查找数组中唯一值的非常简单的代码。我很困惑这是 n 次还是 n^2 次，因为 uniqueValues 数组循环的次数与长度有多大有关。所以这使得它与 for 循环有些无关，不是吗？

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]);

Answer 1

不幸的是

O(n^2)

。请注意

const result = uniqueArray.includes(array[i])

与

相同

let result = false
for (let j = 0; j < uniqueArray.length; j++) {
    if (array[i] == uniqueArray[j]) {
        result = true
    }   
}

请注意，每次调用

uniqueArray

时，都会迭代所有

includes

。

另请注意，

O(...)

符号指的是最坏情况性能。想想你的算法最坏的情况是什么：

array

的所有元素都是唯一的！一个简单的例子是

[1, 2, 3, 4, 5]

。因此，您的

else

语句的

if

子句将始终被输入。

如果

array

的所有元素都是唯一的，那么

uniqueArray.length === array.length

。

因此，

includes

实际上是

O(n)

，从技术上讲，您的算法将迭代

array

两次！

Answer 2

是的，如果您想将它们视为不相关，您可以说

O(n*m)

，其中

n

是数组中的项目数，

m

是唯一项目的数量。然而，对于数组中项目的给定（或平均）相对唯一性，当然对于 100% 唯一性的最坏情况，

m = O(n)

，所以我们简化为

O(n²)

。