multimap的時間複雜性問題

Question

我創建了一個程序來查找數字列表的中位數。數字列表是動態的，因爲可以刪除和插入數字（可以輸入重複數字），在此期間，新的中位數將被重新評估並打印出來。

我創建使用多重映射這個計劃，因爲

1）它被已經被排序的好處，
2）容易插入，刪除，搜索（因爲多重映射實現二進制搜索）
3）重複的條目被允許。

條目+刪除（表示爲N）的數量限制爲：0 < N < = 100,000。

我寫的程序工作並打印出正確的中位數，但速度不夠快。我知道unsorted_multimap比multimap快，但unsorted_multimap的問題是我必須對它進行排序。我必須對它進行排序，因爲要找到需要排序列表的中位數。所以我的問題是，使用unsorted_multimap然後快速排序條目是否可行？還是僅僅是荒謬的？只使用矢量，快速排列矢量並使用二分搜索會更快嗎？或者，我可能忘記了一些我從未想到的神話般的解決方案。我會承認，雖然我對C++並不陌生，但我的技能在時間複雜性上有點藥物。

---

我越是看我自己的問題，更多的我開始以爲只是用用快速排序和折半查找矢量效果會更好，因爲數據結構基本上已經實現了載體。

Answer 1

如果您的目的是隨時跟蹤中位數，因爲元素被插入/移除，您應該使用最小堆和最大堆。每個人都會包含一半的元素...幾天前有一個相關的問題：How to implement a Median-heap

雖然，如果您需要搜索特定值以刪除元素，仍然需要某種地圖。

你說這很慢。每次你需要中位數時，你是否從地圖的開始迭代到第（N/2）個第二元素？你不需要。您可以通過始終保持一個指向它的迭代器和一個小於這個數的元素數的計數器來跟蹤中值。每次插入/刪除時，將新/舊元素與中位數進行比較並更新迭代器和計數器。

看到它的另一種方法是將兩個元素分別包含一半元素。一個元素小於中位數（或相等），另一個則持有這些元素。這些堆可以更高效地執行此操作，但它們不支持搜索。

如果您只需要中位數次就可以使用「select」算法。這在Sedgewick的書中有描述。平均需要O（n）次。它與快速排序類似，但不能完全排序。它只是用隨機樞軸分割陣列，直到它最終在一側選擇較小的m個元素（m =（n + 1）/ 2）。然後你搜索這些m個元素中最大的一個，這就是中位數。

Answer 2

你幾乎肯定會使用矢量更好。可能維護索引的輔助向量將在中間計算之間被移除，以便您可以批量刪除它們。新添加也可以放入一個輔助矢量，排序，然後合併。

Answer 3

我看着自己的問題越多，我開始越想使用帶有快速排序和二分搜索的矢量因爲數據結構基本上已經實現了向量。

如果您只有幾個更新 - 使用未排序的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。

Answer 4

這裏是你如何可以實現在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(); 
    } 
}; 

（Work in action with tests）

的想法是這樣的：

• 保留值的軌道上方和下方兩組的中位數
• 如果添加新值，請將其添加到相應的組。請務必確保下面的集合正好相等於0或1，然後纔是另一個
• 如果刪除了一個值，請將其從集中移除並確保條件仍然成立。

您不能使用priority_queue因爲他們不會讓您刪除一個項目。

Answer 5

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; 
     }