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