<分区>
我正在研究一些常见算法的解决方案，我遇到了一些我很好奇的事情。我试图通过谷歌搜索和查看一些规范来自己找到答案，但我无法找到我的问题的答案。下面的算法基本上检查第一个数组中的每个项目是否在第二个数组中有一个对应的项目平方。天真的解决方案(如他们所说)将具有某种嵌套循环并被视为 O(n2)。下面写解决方案的人说这是 O(n)。
我不明白这怎么可能是 O(n)，因为他在他的循环中使用了 Javascript“in”运算符。据我所知，运算符会检查它正在比较的值是否存在于对象中。 如果它不循环遍历引擎盖下的对象，它是怎么做到的？这真的是线性时间复杂度吗？
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