3个不同数组的所有元素的总和

I want and optimized algorithm to find sum of each and every element of array.

我想要和优化算法来找到数组的每个元素的总和。

for example let 3 array:

例如让3个数组:

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

then final sum will be equal to:

然后最终总和将等于:

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

I tried doing but the algorithm I used had time complexity O(n^3), so I want anything less than this complexity.

我尝试过,但我使用的算法有时间复杂度O(n ^ 3),所以我想要的东西少于这个复杂性。

Here is my algorithm:

这是我的算法:

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

2 个解决方案

#1

For this example, a, b and c have 4, 2 and 2 elements respectively. If you want to add them in every combination, there will be 4 * 2 * 2 = 16 terms to add. In those terms, each element of a will appear 4 times, because it will be added to 2 * 2 = 4 combinations of elements of b and c. Similarly, each element of b (or c) will appear 8 times, because it will be added to each 4 * 2 = 8 combinations of each elements of a and c (or b).

对于该示例,a,b和c分别具有4个,2个和2个元素。如果您想在每个组合中添加它们,则需要添加4 * 2 * 2 = 16个术语。在这些术语中,a的每个元素将出现4次,因为它将被添加到b *和c的2 * 2 = 4个元素组合中。类似地,b(或c)的每个元素将出现8次,因为它将被添加到a和c(或b)的每个元素的每个4 * 2 = 8个组合中。

So, in the final sum, each element of a will appear 4 times and each element of b and c will appear 8 times. Once you figure that out, you can do fewer number of multiplications and additions to get the result.(Just sum of elements of individual arrays and then multiply these sums by 4 , 8 and 8 respectively).

因此,在最后的总和中,a的每个元素将出现4次,b和c的每个元素将出现8次。一旦你弄明白,你可以做更少的乘法和加法来得到结果。(只是各个数组的元素之和,然后分别乘以4,8和8)。

#2

Each element of a will appear in sums with each element of b and each element of c.

a的每个元素将以b的每个元素和c的每个元素的总和出现。

This means that every element in a will appear in a number of sums equal to b.length * c.length.

这意味着a中的每个元素都会以等于b.length * c.length的多个总和出现。

This is also easy to see from the brute force pseudo-code: (modified for readability)

从蛮力伪代码中也很容易看出:(为了便于阅读而修改)

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

Generalising this, we come up with the following algorithm:

概括了这一点,我们提出了以下算法:

Sum all elements a, multiply the result by b.length * c.length.

求和所有元素a,将结果乘以b.length * c.length。

Sum all elements b, multiply the result by a.length * b.length.

求和所有元素b,将结果乘以a.length * b.length。

Sum all elements c, multiply the result by a.length * b.length.

对所有元素c求和,将结果乘以a.length * b.length。

Return the above three values added together.

返回上面添加的三个值。

This is an O(n) algorithm, where n is the total number of elements or average number of elements per array.

这是一种O(n)算法,其中n是元素的总数或每个数组的平均元素数。

#1

#2