map - map.find() 时间复杂度

Question

如果我有地图：

map myMap<string,vector<int>>

找到一个键，然后遍历向量以找到一个特定的 int，最佳、平均和最坏情况的时间复杂度是多少？

我知道 map.find() 方法是 O(log n)，但是我必须在向量中搜索 int 的事实是否会改变时间复杂度？

谢谢

Answer 1

如果你说这是 C++ 会有所帮助。std::map 通常实现为二叉树，这就是查找操作的 O(log(n)) 的来源。

它是 O(log(n) + m)，其中 n 是地图的大小，m 是（每个）向量的大小。我假设您只进行一次查找，然后遍历与您的键对应的整个向量。

由于 log(n) 增长缓慢，除非你的向量非常小，否则 log(n) 应该 < m，因此你的算法应该是 O(m)。