javascript - for 循环内部 "in"运算符的大 O

Question

考虑这个片段:

const obj1 = {1:1, 2:1, 3:1}
const obj2 = {1:1, 4:1, 9:1}

for(let key in obj1){
    if(!(key ** 2 in obj2)) return false
  }

这个算法的大O可以考虑O(n)还是应该是O(n^2)因为:

if(!(key ** 2 in obj2))

被认为是循环遍历obj2的所有项(搜索)

** 注意**:假设obj1和obj2的长度相等

Answer 1

JavaScript 对象实际上是一个哈希表，因此查找键的复杂度为 O(1)。

因此，整个算法的复杂度为 O(n)。