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

map的复杂度是插入、删除、查找等，但迭代总是线性的。

给定内循环中的 n 次迭代（地图的大小），无论是否是地图，在彼此内部有两个这样的 for 循环将产生 O(N^2) 复杂时间外循环的大小（向量的大小，在您的代码中与地图的大小相同）。

Answer 2

您的第二个 for 循环运行 nums.size() 次，所以我们称其为 N。看起来地图的条目数与 nums 一样多，因此它包含相同的 N 个条目。那么大小为 N 的两个 for 循环是 N*N 或 N^2.

map 调用的 begin 和 end 函数是常量时间，因为它们每个都有一个指针引用，据我所知：

C++ map.end function documentation

请注意，如果您确实有两个 for 循环，但外部循环的大小为 N，内部循环的大小不同，比如 M，那么复杂度为 M*N，而不是 N^2。在这一点上要小心，但是如果两个循环的 N 相同，则 N^2 是运行时。

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

What is the runtime complexity of std::map in C++?

c++

arrays

dictionary

runtime

vector