c++ - 有序映射字符串搜索与 int 搜索之间的时间复杂度

Question

我试图了解有序 map 的查找功能所采用的时间复杂度。例如

测试.cpp

map1<std::string, int> = {["name1", 1],["name2", 2],["name3", 3],["name4", 4]};
map2<int, int> = {[1, 10],[2, 20],[3, 30],[4, 40]};

现在最坏的时间复杂度是:

map2.find(2) // would be O(log n)
map1.find("name2") // would be O(log n) + length("name2")

最坏的时间复杂度是否适合 map2？如果没有，谁能解释一下？

Answer 1

Is the worst time complexity right for the map2?

什么是正确的取决于您正在分析的复杂性。 map 查找的对数复杂度描述了 map 元素之间的比较次数。无论 map 中元素的类型如何，这都是相同的。

如果您根据比较函数的子操作来分析复杂度，那么总复杂度将是查找复杂度和比较的最坏情况复杂度的乘积(假设我们正在分析最坏情况复杂度，并且不平均)。

字符串比较的复杂度(字符比较的数量)与字符串之间最长公共(public)初始子字符串的长度成线性关系。

因此，字符串映射查找的比较子操作复杂度为O(m * log n)，其中n为映射的大小，m为字符串元素最长公共(public)初始子串的长度 map 。 m 的上限是最长字符串的长度。