C++ 中 std::multiset::count 的时间复杂度是多少？
What is the Time Complexity of std::multiset::count in C++?
我对在 大小 n[=19 的多重集中为某些 元素 x 调用 count(x) 时发生的操作数感到困惑=].
我说的对吗，操作次数是log(n) + #_of_matches_of_x，意思是multiset中元素个数的对数加上目标元素x在所有元素中的匹配次数在多重集中？
感谢您的宝贵时间！
这个site明确说明multiset::count的复杂度是
Logarithmic in size and linear in the number of matches.
或者您可以查看此 one。
Logarithmic in the size of the container plus linear in the number of the elements found.
好吧，我为您挑选了一篇有趣的文章。 (Link)
如reference link所述，计数的复杂度为：
Logarithmic in the size of the container plus linear in the number of
the elements found.
原因是std::multiset是一个树状数据结构，每个树节点都有一个容器。所以，当调用std::multiset::count时，你应该首先在树O(log(All elements))中找到键，然后计算找到的节点中的元素(O(found elements))。
我对在 大小 n[=19 的多重集中为某些 元素 x 调用 count(x) 时发生的操作数感到困惑=].
我说的对吗，操作次数是log(n) + #_of_matches_of_x，意思是multiset中元素个数的对数加上目标元素x在所有元素中的匹配次数在多重集中？
感谢您的宝贵时间！
这个site明确说明multiset::count的复杂度是
Logarithmic in size and linear in the number of matches.
或者您可以查看此 one。
Logarithmic in the size of the container plus linear in the number of the elements found.
好吧，我为您挑选了一篇有趣的文章。 (Link)
如reference link所述，计数的复杂度为：
Logarithmic in the size of the container plus linear in the number of the elements found.
原因是std::multiset是一个树状数据结构，每个树节点都有一个容器。所以，当调用std::multiset::count时，你应该首先在树O(log(All elements))中找到键，然后计算找到的节点中的元素(O(found elements))。