c++ 中查找方法的时间复杂度是多少?
set<int> s;
s.insert(1);
s.insert(2);
...
s.insert(n);
我想知道 s.find(k) 需要多少时间，其中 k 是 1..n 中的数字?我假设它是 log(n).这是正确的吗?
I wonder how much time it takes for s.find(k) where k is a number from 1..n?
I assume it is log(n). Is it correct?
推荐答案
O( log N ) 来搜索单个元素.
O( log N ) to search for an individual element.
§23.1.2 表 69
§23.1.2 Table 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
相关文章