我正在为一次技术面试研究大 O 表示法,然后我意识到 javascript 的 indexOf
方法可能具有 O(N) 的时间复杂度,因为它遍历数组的每个元素并返回找到它的索引。
我们还知道,O(n^2)(n 平方)的时间复杂度对于较大的数据而言并不是一个好的性能度量。
那么在循环中使用 indexOf
是个坏主意吗?在 javascript 中,通常会看到在循环中使用 indexOf
方法的代码,可能是为了衡量相等性或准备一些对象。
我们是否应该在必要时更喜欢对象而不是数组,因为它们提供具有恒定时间性能 O(1) 的查找。
如有任何建议,我们将不胜感激。
最佳答案
在循环内使用 indexOf
可能不是一个好主意,尤其是当您正在搜索的 dataStructure
非常大时。
解决此问题的一种方法是创建一个哈希表或字典,其中包含您可以在 O(N)
时间内通过遍历数据结构并在每次添加时更新它来生成的每个项目的索引数据结构。
如果你在数据结构的末尾push
一些东西,它会花费 O(1)
时间来更新这个表,最坏的情况是你 push 一些东西到数据结构的开头,它将花费 O(N)
。
在大多数情况下,这是值得的,因为获取索引将是 O(1)
时间。
关于javascript - 在循环中使用 indexOf 是个坏主意吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39463517/