我对在大小n 的多个集合中为某些元素x 调用count(x)时发生的操作数量感到困惑。
我是否正确地确定运算数为log(n)+ #_of_matches_of_x，即多集中元素数的对数加上多集中所有元素中目标元素x的匹配数？
谢谢你的时间!
最佳答案
正如reference link所提到的，count的复杂度为:
Logarithmic in the size of the container plus linear in the number of the elements found.
原因是
std::multimap是一个树状数据结构，每个树节点处都有一个容器。因此，对于调用std::multimap::count来说，您应该首先在树O(log(All elements))中找到键，然后计算找到的节点(O(found elements))中的元素。
关于c++ - C++中std::multiset::count的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61017677/