multimap的时间复杂性问题 [英] Time complexity issues with multimap

问题描述

我创建了一个查找数字列表中值的程序。数字列表是动态的，可以删除和插入数字（可以输入重复的数字），在此期间，重新评估和打印新的中值。

I created a program that finds the median of a list of numbers. The list of numbers is dynamic in that numbers can be removed and inserted (duplicate numbers can be entered) and during this time, the new median is re-evaluated and printed out.

我使用多重图形创建了此程序，因为

I created this program using a multimap because

1） br>
2）容易插入，删除，搜索（因为multimap实现二进制搜索）

3）允许重复条目。

1) the benefit of it being already being sorted,
2) easy insertion, deletion, searching (since multimap implements binary search)
3) duplicate entries are allowed.

条目数+删除数（表示为N）的约束是：0< N≤100,000。

The constraints for the number of entries + deletions (represented as N) are: 0 < N <= 100,000.

我写的程序工作和打印出正确的中位数，但它不够快。我知道unsorted_multimap比multimap快，但然后与unsorted_multimap的问题是，我必须排序它。我必须排序，因为找到中位数你需要有一个排序的列表。所以我的问题是，使用unsorted_multimap然后快速排序条目，或者这只是可笑的是实用的吗？它会更快，只使用一个向量，快速排序向量，并使用二进制搜索？或者我可能忘了一些神话般的解决方案，我甚至没有想到。

The program I wrote works and prints out the correct median, but it isn't fast enough. I know that the unsorted_multimap is faster than multimap, but then the problem with unsorted_multimap is that I would have to sort it. I have to sort it because to find the median you need to have a sorted list. So my question is, would it be practical to use an unsorted_multimap and then quick sort the entries, or would that just be ridiculous? Would it be faster to just use a vector, quicksort the vector, and use a binary search? Or maybe I am forgetting some fabulous solution out there that I haven't even thought of.

虽然我不是C ++的新手，但我承认，我的时间复杂性技能有点药物。

Though I'm not new to C++, I will admit, that my skills with time-complexity are somewhat medicore.

我越看我自己的问题，我越开始认为只使用一个快速排序和二分搜索的向量会更好，因为数据结构基本上已经实现向量。

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

推荐答案

如果您的目的是随时跟踪中值，当元素被插入/删除时， min-heap和max-heap。每一个将包含一半的元素...有几个前几天有一个相关的问题：如何实现中间堆

If your purpose is to keep track of the median on the fly, as elements are inserted/removed, you should use a min-heap and a max-heap. Each one would contain one half of the elements... There was a related question a couple of days ago: How to implement a Median-heap

但是，如果您需要搜索特定值以删除元素，仍然需要某种地图。

Though, if you need to search for specific values in order to remove elements, you still need some kind of map.

你说它很慢。每次你需要中值时，你是从地图的开始迭代到第（N / 2）个元素吗？你不需要。您可以通过维护一个迭代器指向它的所有时间和一个计数器的元素数量少于一个跟踪中值。每次插入/删除，比较新/旧元素与中值，并更新迭代器和计数器。

You said that it is slow. Are you iterating from the beginning of the map to the (N/2)'th element every time you need the median? You don't need to. You can keep track of the median by maintaining an iterator pointing to it at all times and a counter of the number of elements less than that one. Every time you insert/remove, compare the new/old element with the median and update both iterator and counter.

另一种看到它的方式是两个多图包含一半元素。一个保持元素小于中值（或等于），另一个保持那些更大。

Another way of seeing it is as two multimaps containing half the elements each. One holds the elements less than the median (or equal) and the other holds those greater. The heaps do this more efficiently, but they don't support searches.

如果你只需要中间几次，你可以使用选择算法。它在Sedgewick的书中描述。平均需要O（n）时间。它类似于快速排序，但它不完全排序。它只是用随机枢轴分割数组，直到最后，它在一侧选择较小的m个元素（m =（n + 1）/ 2）。然后你搜索最大的那些m元素，这是中位数。

If you only need the median a few times you can use the "select" algorithm. It is described in Sedgewick's book. It takes O(n) time on average. It is similar to quick sort but it does not sort completely. It just partitions the array with random pivots until, eventually, it gets to "select" on one side the smaller m elements (m=(n+1)/2). Then you search for the greatest of those m elements, and this is the median.

这篇关于multimap的时间复杂性问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！