JS中的indexOf()是搜索数组的所有元素来执行吗？

Question

const arr = ['a','b','c']; 
for (let char of arr) {
  console.log(char);
}

我相信上面代码的时间复杂度是 O(n)。

const arr = ['a','b','c']; 
for (let char of arr) {
  console.log(arr.indexOf(char);
}

但是，indexOf() 是否搜索所有元素？如果这样做，我相信上面代码的时间复杂度可能是 O(n^2)

我想知道 indexOf() 是否像 for 循环一样搜索所有组件。

Answer 1

是的，indexOf() 函数的复杂度为 O(n)。如果提供的索引为负数，则仍然从前到后搜索数组。如果计算出的索引小于0，则搜索整个数组。

因此您的程序将具有 O(n^2)

的大符号

您可以在 MDN

找到更多相关信息

Answer 2

对于时间复杂度，你总是考虑最坏的情况（对于OP的情况，每个字符在列表中没有特别指定的位置）。以 OP 示例数组为例，执行 arr.indexOf('c') 将涉及查看每个位置，直到找到字符 c（这是最后一个位置）。因此，假设最坏的情况，执行将花费 .indexOf() 的 O(n) 时间。根据@Nick Parsons 的评论，有一些方法可以使用二分搜索等策略（即 O(log n) 时间复杂度）来改进基础搜索算法的时间，但这意味着数据在某些 semi-structured 中任何概念的格式，如二进制搜索，以提高时间复杂度。

Answer 3

如果浏览器供应商遵循语言规范，那么答案是否定的。一旦找到匹配项，它应该 return。在某些情况下，即使不检查任何元素，它也会 return 。参见 ECMA262。

但是，复杂度是一样的，O(n^2)。

JS中的indexOf()是搜索数组的所有元素来执行吗？

does indexOf() in JS search all the elements of an array to execute?

javascript

arrays

indexof