在C++中改進優先級隊列中的時間複雜度

在下面的代碼中，儘管它適用於較小長度的向量，我有一個數組的數組。我必須將最大數字加到價格上，然後將該數字減1。再次查找最大數字等等。我必須重複這個過程k次。有比時間複雜度較低的優先級隊列更好的數據結構嗎？在C++中改進優先級隊列中的時間複雜度

下面是使用代碼矢量排序：

struct mclass { 
     public: bool operator()(int x, int y) { 
      return (x > y); 
     } 
    } 
    compare; 
    long priceCalculate(vector <int> a, long k) { 

     long price = 0; 
     sort(a.begin(), a.end(), compare); 
     while (--k >= 0) { 
      if (a[0] > 0) { 

       price = price + a[0]; 
       a[0] = a[0] - 1; 

       sort(a.begin(), a.end(), compare); 
      } 
     } 
     return price; 
    }

而這也是大輸入長度給予暫停。

來源

2016-07-07 hmims

你究竟想要做什麼？ – NathanOliver

我真的不明白你的代碼在做什麼。你有這堆元素，你取出頂部，將它添加到'價格'，減少它，並重新插入到隊列中，並重復這個'k-1'次。對於'a'，你有沒有關於'k'在一般情況下有多大的想法？如果'k'和'a'一樣大，你可以對矢量進行排序並避免使用優先級隊列（因爲彈出n個元素總是需要O（n log n）時間）。 – Bakuriu

用代碼邏輯編輯問題。 – hmims

對於矢量解決方案，您應該能夠通過避免循環內部的sort獲得性能。

後

a[0] = a[0] - 1;

，你可以這樣做的（僞）下面的代碼，而不是調用sort：

tmp = 0; 
for j = 1 to end-1 
{ 
    if a[0] < a[j] 
     ++tmp 
    else 
     break 
} 
swap a[0], a[tmp]

正確地放置在排序向量的遞減值，即由於矢量是從start開始排序的，你只需要找到第一個小於或等於遞減值的元素，並用[0]交換前一個元素。這應該比通過整個向量的sort更快。

// Vector after decremt 
9, 10, 9, 5, 3, 2 
    ^
    tmp = 1 

// Vector after swap 
10, 9, 9, 5, 3, 2

// Vector after decremt 
9, 10, 10, 5, 3, 2 
    ^
     tmp = 2 

// Vector after swap 
10, 10, 9, 5, 3, 2

算法的

實例性能

我比較我與從OP矢量示例方法：

k = 1000 vector.size = 10000000 vector filled with random numbers in range 0..9999 compiled with g++ -O3 My approach: real 0.83 user 0.78 sys 0.05 OPs vector approach real 119.42 user 119.42 sys 0.04

來源

2016-07-07 15:22:02 4386427

的分類代碼有兩個性能問題：

您訴諸在每次迭代vector<>。即使您的排序算法是插入排序（在這種情況下最好），它仍然需要觸摸矢量中的每個位置，然後才能聲明vector<>排序。
更糟糕的是，您正在將要使用的值排序在向量的前面，需要後續調用sort()才能移位幾乎所有元素。

因此，您可以通過

反轉排序順序實現巨大的加速，讓你只用vector<>結束交互。
僅排序一次，然後通過從末端掃描到正確位置並在那裏插入新值來更新vector<>。

您還可以採取什麼你的算法是做仔細一看：它永遠只能在具有恆定值，去除它的條目，並重新插回，減一，在vector<>的尾部工作它的前面。我認爲你應該能夠用這些知識大大簡化你的算法，從而導致更加顯着的加速。最後，您可以完全從vector<>中刪除尾部：它完全由其長度和值來描述，並且可以在一次操作中操作其所有元素。一旦你通過優化它，你的算法應該沒有時間......

來源

2016-07-07 15:49:21 cmaster

在C++中改進優先級隊列中的時間複雜度

回答

相關問題