C++：算法复杂度为 std::next 和 std::nth_element for std::multiset

Question

对于 C++ 中的 std::multiset，std::next 和 std::nth_element 的算法（时间）复杂度是多少？我对最新的 gcc 实现很感兴趣，特别是如果它很重要的话。我在 std::multiset 中有一组数字，我需要计算它们的中位数。我有一种感觉，对于平衡二叉树，应该可以在 O(log N) 中执行此操作（如果树是完全平衡的，甚至可以在 O(1) 中执行此操作，因此中值元素位于树）。

using Set = std::multiset<double>;
const Set x = {/*some numbers*/};
if(x.empty()) return 0;
const Set::size_type size = x.size();
const Set::size_type size2 = size/2;
const Set::const_iterator it = std::next(x.begin(), size2);
return size%2==1 ? *it : 0.5*(*std::next(it,-1) + *it);

如果数字在 std::vector 中，我可以在 O(1) 中完成。要在 std::multiset 中找到第 N 个元素，我使用 std::next，但我在想 std::nth_elment 是否会更好（我希望他们都使用 std::multiset 已排序的事实）。

如果我计算中位数的方法不是最优的，请提出更好的方法。

非常感谢您的帮助！

Answer 1

std::next 你移动的距离是 O(k)。

如果你有一个多重集，实际上没有其他方法可以得到中位数。

像这样在容器上写一个更高效的高级操作是可以的，但是std不包含它。

您可以保留两个多重集并使用拼接操作平衡它们，这样中位数始终是第二个容器的第一个元素。这将具有渐近良好的性能特征。

它可能会使其他操作更加痛苦。

C++：算法复杂度为 std::next 和 std::nth_element for std::multiset

C++: algorithmic complexity of std::next and std::nth_element for std::multiset

c++

time-complexity

median

multiset

binary-search-tree