Какова сложность времени для метода find в наборе в 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

Answer 2

Сложность std::set::find(), являющаяся O(log(n)), просто означает, что будет порядка log(n) сравнений объектов, хранящихся в set.

Если сложность сравнения 2 элементов в наборе равна O(k), то фактическая сложность будет O(log(n)∗k).
это может произойти, например, в случае набора строк (k будет длиной самой длинной строки), так как сравнение 2 строк может подразумевать сравнение большинства (или всех) их символов (если они начинаются с того же префикса или являются равны)

Документация говорит то же самое:

Сложность

Логарифмический размер.