Время сложность найти удовольствие

Question

Можете ли вы объяснить, как функция поиска работает в векторе STL C ++ и какова ее временная сложность?

vector<int> v;

if(find(v.begin(),v.end(),element)==v.end())
do this;
else 
do this

Answer 1

С [alg.find]

Возвращает: Первый итератор i в диапазоне [first, last), для которого выполняются следующие условия: *i == value. Возвращает last, если такой итератор не найден.

Сложность: Не более last - first приложений соответствующего предиката.

Это означает, что он будет выполнять линейное сканирование вперед, пока не будет достигнуто значение, равное вашему element.

Answer 2

Посмотрите на https://en.cppreference.com/w/cpp/algorithm/find

В разделе «Возможная реализация» вы можете выяснить, как это работает. Детали зависят от конкретной реализации, которая может быть разной. В любом случае std::find() придется последовательно перебирать вашу коллекцию, и это определяет сложность времени. То есть О (п).