c++ 这段代码的时间复杂度?很困惑

ovfsdjhp  于 2023-06-25  发布在  其他
关注(0)|答案(1)|浏览(141)
unordered_map<int,int> mymap;
        for(int i = 0; i < nums.size(); i++){
            mymap[nums.at(i)]++;
        }

        priority_queue <pair<int,int>> maxheap;
        for(auto it = mymap.begin(); it != mymap.end(); it++){
            maxheap.push({it->second,it->first});
        }

        vector<int> result;
        
        for(int i = 0; i < k; i++){
            result.push_back(maxheap.top().second);
            maxheap.pop();
        }

        return result;

我很困惑,因为在leetcode上,我循环并插入map的第一个for循环被计算为简单的O(n)时间。时间复杂度O(n^2)时间复杂度是O(n)的。
时间复杂度是O(n)的,所以我很困惑为什么第一个for循环的时间复杂度是O(n)

gmxoilav

gmxoilav1#

在内部,unordered_map是使用哈希表实现的,提供给Map的键被哈希到哈希表的索引中,这就是为什么数据结构的性能很大程度上取决于哈希函数,但平均而言,从哈希表中搜索,插入和删除的成本是O(1)

相关问题