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

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

Answer 2

std::set::find() 的复杂度为 O(log(n)) 只是意味着将有 log(n ) 存储在集合中的对象的比较。

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

文档 也有同样的说法：

复杂性

大小为对数。