c++ - multimap 的时间复杂度问题

Question

我创建了一个程序来计算一列数字的中位数。数字列表是动态的，因为可以删除和插入数字(可以输入重复数字)，在此期间，将重新评估并打印出新的中位数。

我使用 multimap 创建这个程序是因为

1) 它已经被排序的好处，
2) 插入、删除、查找方便(因为multimap实现了二分查找)
3) 允许重复条目。

条目数+删除数(表示为N)的约束为:0 < N <= 100,000。

我编写的程序可以运行并打印出正确的中位数，但速度不够快。我知道 unsorted_multimap 比 multimap 快，但是 unsorted_multimap 的问题是我必须对它进行排序。我必须对它进行排序，因为要找到中位数，您需要有一个排序列表。所以我的问题是，使用 unsorted_multimap 然后快速对条目进行排序是否可行，或者这会很荒谬吗？只使用 vector 、对 vector 进行快速排序并使用二分查找会更快吗？或者，也许我忘记了一些我什至没有想到的绝妙解决方案。

虽然我不是 C++ 的新手，但我承认，我在时间复杂度方面的技能有些中等。

---

我越看自己的问题，就越开始认为仅使用带有快速排序和二进制搜索的 vector 会更好，因为数据结构基本上已经实现了 vector 。

Answer 1

the more I look at my own question, the more I'm beginning to think that just using vector with quicksort and binary search would be better since the data structures basically already implement vectors.

如果您只有很少的更新 - 使用未排序的 std::vector + std::nth_element算法是 O(N)。您不需要完全排序，即 O(N*ln(N))。

live demo of nth_element :

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

using namespace std;

template<typename RandomAccessIterator>
RandomAccessIterator median(RandomAccessIterator first,RandomAccessIterator last)
{
   RandomAccessIterator m = first + distance(first,last)/2; // handle even middle if needed
   nth_element(first,m,last);
   return m;
}

int main()
{
   vector<int> values = {5,1,2,4,3};
   cout << *median(begin(values),end(values)) << endl;
}

输出是:

3

---

如果您有很多更新并且只从中间删除 - 使用两个堆作为 comocomocomocomo suggests .如果你会使用 fibonacci_heap - 然后你也会得到 O(N) 从任意位置移除(如果没有句柄的话)。

如果您有很多更新并且需要从任意位置移除 O(ln(N)) - 然后使用两个多重集作为 ipc suggests .