c++ - C++中std::map的运行时复杂度是多少？

Question

我仍然对C++中std::map的运行时复杂度感到困惑。我知道以下算法中的第一个for循环需要O(N)或线性运行时。但是，第二个for循环在映射上有另一个for循环。这会增加整体运行时的复杂性吗？换句话说，以下算法的整体运行时复杂度是多少？是O(N)还是O(Nlog(N))还是其他东西？

    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        
        vector<int> result;
        map<int, int> mp;
        
        for (int i = 0; i < nums.size(); i++) {
            mp[nums[i]]++;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            int numElements = 0;
            for (auto it = mp.begin(); it != mp.end(); it++) {
                if (it->first < nums[i]) numElements += it->second;
            }
            result.push_back(numElements);
        }
        
        return result;
    }

Answer 1

映射的复杂性是插入，删除，搜索等的复杂性。但是迭代始终是线性的。
给定内部循环中的n次迭代(映射的大小)，对于外部循环的每次迭代，在彼此内部具有两个这样的for循环将产生O(N ^ 2)复杂性时间(无论是否为映射)。 vector 的大小，在您的代码中与 map 的大小相同)。