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）。