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

Question

set<int> s;

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

我想知道 s.find(k) 需要多少时间，其中 k 是 1..n 中的一个数字？ 我假设它是 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