c ++中集合中find方法的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2790993/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is time complexity for find method in a set in c++?
提问by David Rodríguez - dribeas
set<int> s;
s.insert(1);
s.insert(2);
...
s.insert(n);
I wonder how much time it takes for s.find(k)where kis a number from 1..n?
I assume it is log(n). Is it correct?
我想知道1..n 中的数字s.find(k)在哪里需要多长时间k？我假设它是 log(n)。这是正确的吗？
回答by David Rodríguez - dribeas
O( log N ) to search for an individual element.
O( log N ) 来搜索单个元素。
§23.1.2 Table 69
§23.1.2 表 69
expression return note complexity
a.find(k) iterator; returns an iterator pointing to an logarithmic
const_iterator element with the key equivalent to k,
for constant a or a.end() if such an element is not
found
回答by Neetesh Dadwariya
The complexity of std::set::find()being O(log(n))simply means that there will be of the order of log(n)comparisons of objects stored in the set.
的复杂性std::set::find()是O(log(n))仅仅意味着将有数量级的log(n)存储在所述对象的比较set。
If the complexity of the comparison of 2 elements in the set is O(k), then the actual complexity, would be O(log(n)?k).
this can happen for example in case of set of strings (k would be the length of the longest string) as the comparison of 2 strings may imply comparing most of (or all) of their characters (if they start with the same prefix or are equal)
如果集合中 2 个元素的比较复杂度为O(k)，则实际复杂度为O(log(n)?k)。
例如，在一组字符串（k 是最长字符串的长度）的情况下可能会发生这种情况，因为 2 个字符串的比较可能意味着比较它们的大部分（或全部）字符（如果它们以相同的前缀开头或平等的）
The documentationsays the same:
该文件说是相同的：
Complexity
Logarithmic in size.
复杂
大小为对数。
