c++ 中查找方法的时间复杂度是多少? [英] What is time complexity for find method in a set in 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

这篇关于c++ 中查找方法的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！