在循环内使用indexOf是个坏主意吗?

我在为一次技术采访研究大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)时间。

相关文章