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

ovfsdjhp  于 2023-06-25  发布在  其他
关注(0)|答案(1)|浏览(173)
  1. unordered_map<int,int> mymap;
  2. for(int i = 0; i < nums.size(); i++){
  3. mymap[nums.at(i)]++;
  4. }
  5. priority_queue <pair<int,int>> maxheap;
  6. for(auto it = mymap.begin(); it != mymap.end(); it++){
  7. maxheap.push({it->second,it->first});
  8. }
  9. vector<int> result;
  10. for(int i = 0; i < k; i++){
  11. result.push_back(maxheap.top().second);
  12. maxheap.pop();
  13. }
  14. return result;

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

gmxoilav

gmxoilav1#

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

相关问题