3個不同陣列的所有元素的總和

我想要和優化算法來找出數組的每個元素的總和。3個不同陣列的所有元素的總和

例如讓3陣列：

a = [1,2,3,4]; 
b = [5,6]; 
c = [8,9];

然後最終總和將等於：

sum(1,5,8)+sum(1,5,9)+sum(1,6,8)+sum(1,6,9)+sum(2,5,8)...+sum(4,6,9)

我試圖做，但我所使用的算法有時間複雜性爲O（n^3 ），所以我希望任何東西都不會超過這種複雜性。

這是我的算法：

sum = 0  
for(i=0;i<a.size();i++) 
     for(j=0;j<b.size();j++) 
      for(k=0;k<c.size();k++) 
       sum = sum+a[i]+b[j]+c[k];

來源

2017-06-03 Mayank Joshi

你試過了什麼？ – Novaterata

我不確定你在做什麼。如果您正在嘗試做我認爲的事，那是一個階乘時間算法。編輯你的問題。 – Makogan

另外，這不是一個二維數組。 – Makogan

對於這個例子，a，b和c分別具有4,2和2個元素。如果您想在每個組合中添加它們，則會添加4 * 2 * 2 = 16條款。在這些術語中，a的每個元素將出現4次，因爲它將被添加到b和c的元素的組合中。類似地，b（或c）的每個元素將出現8次，因爲它將被添加到每個元素a和c（或b）的每個元素的組合中。

因此，在最後的總和中，a的每個元素將出現4次，並且b和c的每個元素將出現8次。一旦你知道了，你可以做更少的乘法和加法來得到結果（只是單個數組元素的總和，然後將這些和分別乘以4,8和8）。

來源

2017-06-03 03:18:29 0605002

爲了進一步優化，預先計算每個數組的總和，然後將其乘以其他兩個數組的大小的乘積。 – ithenoob

a的每個元素將以b的每個元素和c的每個元素的總和出現。

這意味着a中的每個元素都會以等於b.length * c.length的總和出現。

這也很容易從蠻力僞代碼看：（修改可讀性）

for i = 0 to a.length 
    for j = 0 to b.length  // happens once for each i 
     for k = 0 to c.length // happens b.length times for each i 
     sum += a[i] + ... // happens b.length * c.length times for each i

要概括這一點，我們提出瞭如下算法：

總和的所有元素a，將結果乘以b.length * c.length。
總和所有元素b，將結果乘以a.length * b.length。
總和所有元素c，將結果乘以a.length * b.length。
將上述三個值加在一起。

這是一個O(n)算法，其中n是每個陣列的元素總數或平均元素數。

來源

2017-06-03 07:09:01 Dukeling

3個不同陣列的所有元素的總和

回答

相關問題