在循环内使用indexOf是个坏主意吗？ [英] Is it a bad idea to use indexOf inside loops?

问题描述

我在为一次技术采访研究大O表示法，然后我意识到javascript的indexOf方法可能有O(N)的时间复杂度，因为它遍历数组的每个元素并返回找到的索引。

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

那么在循环内使用indexOf是个坏主意吗？在javascript中，在循环中使用indexOf方法代码很常见，可能是为了度量相等性或准备某个对象。

而不是数组，我们是否应该在需要的地方选择对象，因为它们提供具有恒定时间性能O(1)的查找。

如有任何建议，我们将不胜感激。

推荐答案

在循环内使用indexOf可能不是一个好主意，尤其是在您正在搜索的dataStructure非常大的情况下。 解决此问题的一种方法是创建一个哈希表或字典，其中包含您可以在O(N)时间内生成的每个项目的索引，方法是遍历数据结构并在每次添加到数据结构时对其进行更新。

如果您push位于数据结构的末尾，则更新此表将需要O(1)时间，而最糟糕的情况是，如果您将某些内容推到数据结构的开头，则将花费O(N)。

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

这篇关于在循环内使用indexOf是个坏主意吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！