为何频率计数器法判断变位词的时间复杂度是O(n)而非O(n²)？

原实现代码 #

const anagram = (str1, str2) => {
    str1 = str1.split('');
    str2 = str2.split('');
    
   let frequencyCounter1 = {};
   let frequencyCounter2 = {};

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

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

   for(let key in frequencyCounter1) {
       if(!(key in frequencyCounter2)) {
           return false;
       }

       if(frequencyCounter1[key] !== frequencyCounter2[key]) {
           return false;
       }
   }

    return true;
}

anagram('racecar', 'racecar');

问题描述 #

本次挑战要求使用频率计数器模式判断str2是否为str1的变位词，给出的解法声称时间复杂度为O(n)。但存在如下语句：

if(!(key in frequencyCounter2)) {
    return false;
}

这是否意味着需要遍历对象来检查键是否存在，从而形成嵌套循环，导致时间复杂度变为O(n²)？

解答 #

完全不会，核心原因是：JavaScript普通对象的键查找是**O(1)**的哈希表操作，不是遍历。

当你用key in obj或者直接访问obj[key]时，底层是通过哈希映射直接定位到对应键的位置，不需要遍历对象的所有键。所以整个代码的时间复杂度依然是线性的：

• 前两个循环分别遍历两个字符串，时间复杂度是O(n) + O(m)（n、m为两个字符串的长度），属于线性时间范畴。
• 最后遍历frequencyCounter1的键，循环次数最多是字符串中不同字符的数量（最坏情况是O(n)），但每次循环里的键检查和值对比都是O(1)操作，所以这部分也是线性时间。

另外提个小问题：原解法有个漏洞——如果str2比str1长，且包含str1的所有字符但多了其他字符，比如anagram('a', 'aa')，这个解法会错误返回true。解决办法可以是先判断两个字符串长度是否相等，或者最后再遍历frequencyCounter2的键，确保所有键都存在于frequencyCounter1中。

内容的提问来源于stack exchange，提问作者Brixsta