c ++中集合中查找方法的时间复杂度是多少？

Question

set<int> s;

s.insert(1);
s.insert(2);
...
s.insert(n);

我想知道从1..n开始的数字s.find(k)在哪里需要多长时间k？我假设它是log(n).这是对的吗？

Answer 1

O(log N)搜索单个元素.

§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

Answer 2

的复杂性std::set::find()是O(log(n))仅仅意味着将有数量级的log(n)存储在所述对象的比较set。

如果集合中 2 个元素的比较复杂度为O(k)，则实际复杂度为O(log(n)?k)。
这可能发生在例如一组字符串（k 是最长字符串的长度）的情况下，因为 2 个字符串的比较可能意味着比较它们的大部分（或全部）字符（如果它们以相同的前缀开头或平等的）

该文件说是相同的：

复杂

大小为对数。