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
  }

该算法的 Big O 可以认为是 O(n) 还是应该是 O(n^2)，因为：

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

被认为循环遍历obj2的所有项目（搜索）

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

Answer 1

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

因此，总算法为 O(n)。