多图的时间复杂性问题

Question

我创建了一个程序来查找数字列表的中位数.数字列表是动态的,可以删除和插入数字(可以输入重复的数字),在此期间,重新评估和打印新的中位数.

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

1)它已经被分类的好处,
2)容易插入,删除,搜索(因为多图实现二进制搜索)
3)允许重复的条目.

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

我写的程序工作并打印出正确的中位数,但速度不够快.我知道unsorted_multimap比multimap快,但是unsorted_multimap的问题是我必须对它进行排序.我必须对它进行排序,因为找到你需要有一个排序列表的中位数.所以我的问题是,使用unsorted_multimap然后快速排序条目是否可行,或者这只是荒谬的？使用矢量,快速导航矢量和使用二分搜索会更快吗？或者也许我忘记了一些我甚至都没想过的神话般的解决方案.

虽然我不是C++的新手,但我会承认,我的时间复杂性技巧在某种程度上是医学上的.

---

我越是看自己的问题,我越开始认为只使用带快速排序和二进制搜索的向量会更好,因为数据结构基本上已经实现了向量.

Answer 1

我越是看自己的问题,我越开始认为只使用带快速排序和二进制搜索的向量会更好,因为数据结构基本上已经实现了向量.

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

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建议.如果你使用fibonacci_heap - 那么你也可以从仲裁位置移除O(N)(如果没有句柄).

如果你有很多更新并需要从仲裁地点删除O(ln(N)) - 那么就像ipc建议的那样使用两个多重集.