克服n^2運行時程序

有沒有辦法在C++ 11中克服嵌套循環遞歸？我的程序運行緩慢。或者說，是否有更有效的方法來解決以下公式z=|a-b|*|x-y|，其中a，b，x和y是10000整數數組中的元素？克服n^2運行時程序

下面是代碼：

#include <iostream> 
#include <fstream> 
#include <cmath> 
using namespace std; 

ifstream in("int.in"); 

int main() 
{ 
    long long n, n1, z, x, y, in2=0; 
    in>>n 
    long long l[n], p[n]; 
    for(x=0;x!=n;x++) 
     in>>l[x]>>p[x]; 
    for(x=0;x!=n;x++) 
    { 
     for(y=x+1;y<n;y++) 
     { 
      ineq+=(abs(l[x]-l[y])*abs(p[x]-p[y]))); //executes slow 
      /*n1=l[x]-l[y]; //Alternative algorithm 
      if(n1<0) 
       n1*=-1; 
      z=p[x]-p[y]; 
      if(z<0) 
       z*=-1; 
      in2+=n1*z;*/ 
     } 
    } 
    cout<<in2<<"\n"; 
}

我試圖改變數據類型short int，long，long long和unsigned，但它要麼傾倒垃圾值或執行``分割核心Fault`錯誤。

對於絕對值公式，我最初嘗試使用硬編碼方法（註釋掉），但它似乎輸出垃圾值。我也試圖用abs()函數ineq+=abs(l[x]-l[y])*abs(p[x]-p[y]));優化abs解決方案，但它似乎執行速度較慢。我不知道我可以實現的其他優化，所以請推薦一些。

首選Linux友好型解決方案。謝謝。

側注：a，b，x和y的值都在1<=a,b,x,y<=10000的範圍內。注意：這個程序從文件「int.in」中讀取，取第一個整數（項目數），並按對（l [x]和p [x]是對）讀取每條新行。

我注意到：我也試過只使用多維數組，但是我在某處讀取一維數組在CPU緩存中，而多維數據分散在內存中，速度較慢。

來源

2015-05-06 Zuayo Beta

你能解釋一下爲什麼你計算這個值是多少？那麼建議一種替代算法可能會更容易。 – cfh

相關，你想要在大局中完成什麼？例如，我認爲傅立葉變換運行在'n log n'中，所以如果你可以將它移動到FFT域，你將獲得加速。 – jww

而z可以是什麼？你想**所有**解決方案還是隻有一個？ –

的問題可以用另一種方式來得出：你的公式z=c*d（當然c is |a-b|和d is |x-y|）在尋找c和d（正）。

所以先訂購你的數組。然後查找z=c*d的解決方案，然後找到哪個a和b使c == a - b爲真，x和y使d == x - y爲真。

一旦完成，你已經獲得了所有讓你真正的公式，因爲ABS（A-B）相同的ABS（B-A）

來源

2015-05-06 08:53:27

克服n^2運行時程序

回答

相關問題