在循环中使用indexOf是一个坏主意吗？

Question

我正在研究技术面试的大O符号,然后我意识到javascript的indexOf方法可能具有O(N)的时间复杂度,因为它遍历数组的每个元素并返回其找到的索引.

我们还知道,对于较大的数据,O(n ^ 2)(n平方)的时间复杂度不是一个好的性能度量.

那么使用indexOf内部循环是一个坏主意吗？在javascript中,看到indexOf在循环中使用方法的代码很常见,可能是测量相等性或准备一些对象.

我们应该在必要时更喜欢对象,而不是数组,因为它们提供具有恒定时间性能O(1)的查找.

任何建议将不胜感激.

Answer 1

使用indexOf内部循环可能是一个坏主意，特别是如果dataStructure您正在搜索的内容非常大。一种解决方法是拥有一个哈希表或字典，其中包含每个项目的索引，您可以O(N)通过循环遍历数据结构并在每次添加到数据结构时更新它来及时生成这些索引。

如果你push在数据结构的末尾有东西O(1)，更新这个表需要时间，最坏的情况是如果你把东西推到数据结构的开头，它会花费O(N)。

在大多数情况下，这是值得的，因为获取索引将是O(1)时间。

Answer 2

老实说，tl;博士。但是，我对检查字符串中出现的各种方法进行了一些速度测试（如果这是您使用 indexOf 的目标。如果您实际上是想获得匹配的位置，我个人不知道如何提供帮助你那里）。我测试的方法是：

• .includes()
• .match()
• .indexOf()

（也有该变体如.search()，.lastIndexOf()等。这些我没有测试）。

这是测试：

var test = 'test string';

console.time('match');
console.log(test.match(/string/));
console.timeEnd('match');

console.time('includes');
console.log(test.includes('string'));
console.timeEnd('includes');

console.time('indexOf');
console.log(test.indexOf('string') !== 0);
console.timeEnd('indexOf');

我知道它们不是循环，但向您展示它们的速度基本相同。老实说，每个人都做不同的事情，这取决于您的需要（您想通过 RegEx 搜索吗？您需要与 ECMAScript 2015 兼容吗？等等 - 我什至没有列出所有这些）是否真的有必要分析就这么多？

从我的测试来看，有时indexOf()会赢，有时其他人会赢。