Какова временная сложность метода поиска в наборе в С++?

set<int> s;

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

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


c++ set find stl
person Community    schedule 07.05.2010    source источник
comment
Вы имеете в виду log(n) вместо n log(n)?   -  person Thomas    schedule 07.05.2010

Ответы (2)


arrow_upward
20
arrow_downward

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
person David Rodríguez - dribeas    schedule 07.05.2010
comment
Хорошая информация, но §23.1.2 Таблица 69 не очень хороша без названия книги. - person snibbets; 18.10.2012
comment
@snibbets: Когда имеешь дело со стандартизированным языком, книга является стандартом. На момент ответа это будет стандарт С++ 03. В текущем стандарте C++11 это будет §23.2.4 Таблица 102. - person David Rodríguez - dribeas; 18.10.2012

arrow_upward
5
arrow_downward

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

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

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

Сложность

Logarithmic in size.

person Neetesh Dadwariya    schedule 29.06.2015