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个不同阵列的所有元素的总和

回答

相关问题