multimap的时间复杂度问题

Question

我创建了一个程序，用于查找一组数字的中位数。这组数字是动态的，可以插入和删除数字（可以输入重复数字），在此过程中，新的中位数会被重新计算并打印出来。

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

1）它已经排好序了；

2）插入、删除、搜索都很容易（因为multimap实现了二进制搜索）；

3）允许重复的条目。

数字输入和删除的约束条件（表示为N）为：0 < N <= 100,000。

我编写的程序可以正常运行并输出正确的中位数，但速度不够快。我知道unsorted_multimap比multimap更快，但unsorted_multimap的问题在于我需要对其进行排序。我必须对其进行排序，因为要找到中位数，你需要有一个已排序的列表。所以我的问题是，使用unsorted_multimap然后快速排序条目是否可行，还是说这个方法荒谬无比？使用vector，对其执行快速排序，然后使用二进制搜索是否更快？或者也许我忘记了一些我甚至没有想到的神奇解决方案。

虽然我不是C++的新手，但我承认，我的时间复杂度技能有点中等水平。

看着自己的问题，我越看越觉得，只使用vector，进行快速排序和二进制搜索会更好，因为数据结构基本上已经实现了vector。

- user1066524

---

我认为对于这个问题来说，映射并不是一个好的数据结构。最佳性能可能会来自一个向量，尽管我还没有比较过这两种方法。 - evanmcdonnal

@evanmcdonnal，我认为你可能是对的。我想使用向量在快速排序和二分查找方面可能会同样快。 - user1066524

我认为这个问题是一个重复的问题：https://dev59.com/wXM_5IYBdhLWcg3waSb9 - Jose Luis Blanco

@JoseLuisBlanco：这并不完全是因为集合可能正在缩小。 - ipc

向量比多重映射快，但仍然不够快...这很奇怪。也许我以某种其他方式减慢了它的速度。 - user1066524

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)) - 则使用两个multisets，如ipc建议的。

- Evgeny Panasyuk

Answer 2

如果您的目的是在插入/删除元素时实时跟踪中位数，您应该使用min-heap和max-heap。每个堆都将包含一半的元素...几天前有一个相关问题：如何实现中位数堆 尽管如此，如果您需要搜索特定值以便删除元素，仍然需要某种类型的映射。

您说它很慢。您是否每次需要中位数时都从地图开头迭代到第（N / 2）个元素？您不需要这样做。您可以通过始终保持指向其的迭代器和小于该迭代器的元素数量的计数器来跟踪中位数。每次插入/删除时，将新/旧元素与中位数进行比较并更新迭代器和计数器。

另一种看待它的方式是作为包含每半个元素的两个multimaps。其中一个保存小于中位数（或相等）的元素，而另一个保存大于中位数的元素。堆可以更有效地执行此操作，但它们不支持搜索。

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

- comocomocomocomo

Answer 3

以下是如何每次更新时以O(log N)的时间复杂度实现：

template <typename T>
class median_set {
public:
  std::multiset<T> below, above;

  // O(log N)
  void rebalance()
  {
    int diff = above.size() - below.size();
    if (diff > 0) {
      below.insert(*above.begin());
      above.erase(above.begin());
    } else if (diff < -1) {
      above.insert(*below.rbegin());
      below.erase(below.find(*below.rbegin()));
    }
  }

public:
  // O(1)
  bool empty() const { return below.empty() && above.empty(); }

  // O(1)
  T const& median() const
  {
    assert(!empty());
    return *below.rbegin();
  }

  // O(log N)
  void insert(T const& value)
  {
    if (!empty() && value > median())
      above.insert(value);
    else
      below.insert(value);
    rebalance();
  }

  // O(log N)
  void erase(T const& value)
  {
    if (value > median())
      above.erase(above.find(value));
    else
      below.erase(below.find(value));
    rebalance();
  }
};

(测试中的实际工作)

想法如下:

• 在两个集合中跟踪中位数上方和下方的值
• 如果添加新值，请将其添加到相应的集合。始终确保下面的集合比另一个多0或1个。
• 如果删除值，请从集合中删除它并确保条件仍然成立。

你不能使用priority_queue，因为它们不允许你删除一个项目。

- ipc

---

你不能使用 priority_queues ，因为它们不允许你删除单个项目。fibonacci_heap 支持元素擦除，其操作是：top - O(1)，push - O(1)，erase - O(ln(N))。但是，如果要擦除元素而没有句柄，则搜索该元素的时间复杂度为 O(N)，因此擦除将是 O(N)。http://www.boost.org/doc/libs/1_53_0/doc/html/heap/data_structures.html - Evgeny Panasyuk

Answer 4

Can any one help me what is Space and Time complexity of my following C# program with details.
//Passing Integer array to Find Extreme from that Integer Array
   public int extreme(int[] A)
        {
            int N = A.Length;
            if (N == 0)
            {
                return -1;
            }
            else
            {
                int average = CalculateAverage(A);
                return FindExtremes(A, average);
            }
        }
// Calaculate Average of integerArray
        private int CalculateAverage(int[] integerArray)
        {
            int sum = 0;
            foreach (int value in integerArray)
            {
                sum += value;
            }
            return Convert.ToInt32(sum / integerArray.Length);
        }
//Find Extreme from that Integer Array
        private int FindExtremes(int[] integerArray, int average) {
            int Index = -1; int ExtremeElement = integerArray[0];
            for (int i = 0; i < integerArray.Length; i++)
            {
                int absolute = Math.Abs(integerArray[i] - average);
                if (absolute > ExtremeElement)
                {
                    ExtremeElement = integerArray[i];
                    Index = i;
                }
            }
            return Index;
        }

- Shankar Kamble

Answer 5

你最好使用向量。可能需要维护一个索引辅助向量，在中位数计算之间删除它们，以便可以批量删除。新添加的内容也可以放入辅助向量中，进行排序，然后合并。

- Steve

---

向量比多重映射快，但仍然不够快。我正在使用快速排序和二分查找。 - user1066524