JavaScript是否“插入"?操作员在后台执行循环? [英] Does the JavaScript "in" operator execute a loop under the hood?

问题描述

我正在研究一些常见算法的解决方案，遇到了一些我很好奇的问题.我试图通过谷歌搜索并查看一些规范来自己找到答案，但找不到我的问题的答案.下面的算法基本上检查第一个数组中的每个项目在第二个数组中是否有对应的项目平方.天真的解决方案(如他们所说)将具有某种嵌套循环，并被视为O(n2).写下下面解决方案的人说这是O(n).

I was studying some solutions to common algorithms and I ran across something that I am curious about. I tried to find the answer myself by googling and looking at some of the specifications but I am unable to find the answer to my question. The below algorithm basically checks to see if every item in the first array has a corresponding item squared in the second array. The naive solution (as they say) would have some sort of nested loop and be considered O(n2). The person who wrote the solution below said this is O(n).

我不知道这怎么可能是O(n)，因为他在循环内使用Javascript"in"运算符.据我所知，运算符将检查以查看其比较的值是否存在于对象中. 如果它没有循环通过引擎盖下的物体，该怎么办?这真的是线性时间复杂度吗?

I don't understand how this can be O(n) because he is using the Javascript "in" operator inside of his loop. As far as I can tell that operator checks to see if the value it's comparing exists in the object. How does it do that if it is not looping through the object under the hood? Is this really a linear time complexity?

function same(arr1, arr2) {

  if (arr1.length !== arr2.length) {
    return;
  }

  let frequencyMap1 = {};
  let frequencyMap2 = {};

  for (let val of arr1) {
    frequencyMap1[val] = (frequencyMap1[val] || 0) + 1;
  }

  for (let val of arr2) {
    frequencyMap2[val] = (frequencyMap2[val] || 0) + 1;
  }

  for (let key in frequencyMap1) {
    if (!(key ** 2 in frequencyMap2)) {
      return false;
    }

    if (frequencyMap2[key ** 2] !== frequencyMap1[key]) {
      return false
    }
  }

  return true;
}

console.log(same([1, 2, 3], [1, 4, 9])); // true

推荐答案

在对象中查找键为O(1)... in 中的，只有 in 中的运算符是不同的.

Finding a key in an object is O(1). for .. in and just only in operator is different.

无论对象中有多少键，您都可以在恒定时间内访问它. Object 或 Map 具有用于查找键的哈希表.

No matter how many keys are in an object, you can access it in constant time. Object or Map has a hash table to find a key.

这篇关于JavaScript是否“插入"?操作员在后台执行循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！