混淆哈希映射的时间复杂度

Question

在 leetcode 上，我发现“忽略”涉及哈希映射的最坏情况时间复杂度是很常见的。我认为在软件采访中，像他们经常做的那样假设“最坏情况”是标准的。下面是我对一个简单问题的解决方案。问题是找到字符串中的第一个非重复字符。我知道散列图平均为 O(1) 查找。但是当遍历字符串并查找散列图时，为什么时间复杂度不是 O(N^2) 而是 O(N)？

#include <unordered_map>

class Solution {
public:
    unordered_map<char, int> m;
    
    int firstUniqChar(string s) {
        for(char c : s) {
            m[c]++;
        }
        for(int i =0; i < s.length(); i++) {
            if(m[s[i]] == 1) {
                return i;
            }
        }
        
        return -1;
    
    }
};

Answer 1

它平均 O(N) 因为哈希映射平均每次查找 O(1) 而你做了 O(N) 个。

平均表示对所有可能的输入进行平均。这意味着可能存在一个输入数组，该数组破坏了特定的哈希值并在每次查找时达到 O(N) 或更糟。

最坏的情况在很大程度上是特定于实现的——例如散列到桶中取决于元素如何存储在每个桶中。如果它们在一个简单列表中，则查找是 O(<duplicates>)，二叉树会将其降低到 O(log<duplicates>)。搜索存在和丢失的密钥之间也可能存在差异。

还有一个很大的假设，即所有散列容器都可以随着存储的元素数量而增长。 IE。保持桶的占用率低。

在采访中提及他们最坏的情况并没有坏处，这表明您知道他们是有极限的。

Answer 2

给定问题的时间复杂度为 O(N)。你可以为它提供一个 perfect hash function，那是不会发生碰撞的。这里这个完美的哈希函数是static_cast<size_t>(256+c)。好吧，如果你在 leetcode 上查看这个问题的最快解决方案，你会发现人们使用普通数组。

混淆哈希映射的时间复杂度

Confusion about time complexity with hash maps

c++

time-complexity