Что такое временная сложность для метода находки в наборе в C++?

Question

Что такое временная сложность для метода находки в наборе в C++?

set<int> s;

s.insert(1);
s.insert(2);
...
s.insert(n);

Интересно, для какого количества времени требуется s.find(k) где k число от 1.. n? Я предполагаю, что это - журнал (n). Это корректно?

11

c++ stl find set

задан 7 May 2010 в 19:14

1 ответ

Другие вопросы по тегам:

c++ stl find set

Похожие вопросы:

score 17 · 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