Что такое временная сложность std :: multiset :: count в C ++?

Question

Меня смущает количество операций, выполняемых при вызове count (x) для некоторого элемента x в мультимножестве размера n .

Am. Я исправляю, что число операций равно log (n) + #_of_matches_of_x, что означает logarithmi c по количеству элементов в мультимножестве плюс число совпадений целевого элемента x среди всех элементов мультимножества?

Спасибо за ваше время!

Answer 1

Как упомянуло справочную ссылку , сложность подсчета составляет:

Logarithmi c в размере контейнера плюс линейный в количество найденных элементов.

Причина в том, что std::multimap представляет собой древовидную структуру данных с контейнером на каждом узле дерева. Таким образом, для вызова std::multimap::count вы должны сначала найти ключ в дереве O(log(All elements)), а затем сосчитать элементы в этом найденном узле (O(found elements)).

Answer 2

Этот сайт четко заявляет, что сложность multiset :: count составляет

Логарифмический размер c и линейный по количеству совпадений.

Или вы можете проверить это один .

Логарифмический c в размере контейнера плюс линейный в количестве найденных элементов.

Что ж, я вытащил для вас интересную статью. ( Ссылка )