在減少大O複雜度方面尋找一種高效的算法

給定一個有N個元素的排序數組。需要找到所有元素差異的絕對總和。例如：給定4個元素1,2,3和4. | 1-2 | + | 1-3 | + | 1-4 | + | 2-3 | + | 2-4 | + | 3-4 | = 10.這是我在java中的代碼：在減少大O複雜度方面尋找一種高效的算法

List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers 
public static int lsum(int N)//consider the arraylist to be sorted in ascending order. 
{ 
    int sum =0; 

    for(int i=0;i<N;i++) 
    { 
     int w =a.get(i); 
     for(int j =i;j<N;j++) 
     { 
      int z = a.get(j); 
      sum =sum +(z-w); 
     } 

     } 
    return(sum); 

}

尋找一個有效的算法，而不是我使用{0（n^2）複雜度}的微不足道的算法。這是需要此功能的更大程序的要求。輸入（元素數量）可以大到10^5。

來源

2013-10-19 Sushim Mukul Dutta

請前往http://codereview.stackexchange.com。 –

@JeroenVannevel沒有太多的幫助，沒有收到任何答案，因此重新張貼。 –

如果您先排序元素，則可以將運行時間降至O(n log n)。

這裏的想法是，如果a[]是有序和b[i]整數列表和其他數字a[i]之間的差異的總和，然後b[i+1]可以直接在b[i]，i，a[i+1] - a[i]條款計算，並且數組的長度。

我不會說究竟如何，但這裏有一個提示。 Math.abs(a[i+1] - a[j])與Math.abs(a[i] - a[j])有什麼不同？其中j是Math.abs(a[i+1] - a[j])更大？哪個j更小？

現在，在您計算這些值之後，b[i]之間會包含兩次差異。你想要的值就是它們的和除以2

來源

2013-10-19 23:11:22

分爲如果數組是x_1 <= x_2 <= .. <= x_n

涉及x_r項的總和是U_r + (2r -n) x_r - L_r

其中U_r = x_{r+1} + x_{r+2} + ... + x_n 和L_r = x_1 + x_2 + ... + x_{r-1}

現在你可以計算所有U_i在O（n）時間內一次通過陣列。 L_i可以寫成U_i和元素的總和。

因此可以在O（n）時間內計算整個和。

有些玩弄數學應該會給你一個單人 pass算法。

（我將細節留給你）。

來源

2013-10-19 23:42:33

在減少大O複雜度方面尋找一種高效的算法

回答

相關問題