c++ - 两个相乘的每个子集的加法

Question

我有一个包含元素 {7,2,1} 的数组，我的想法是执行 7 * 2 + 7 * 1 + 2 * 1 这基本上是这个算法:

for(int i=0;i<n-1;++i)
    for(int k=i+1;k<n;++k)
       sum += a[i] * a[k];

其中 a 是数组，其中我有数字，n 是元素的数量，我需要一个更有效的算法来执行此操作，但我没有知道怎么做，有人可以帮我吗？

谢谢!

Answer 1

在一般情况下你可以做得更好。是时候做一些数学了。让我们看看 3 元素版本，我们有:

ab + ac + bc
= 1/2 * (2ab + 2ac + 2bc)
= 1/2 * (2ab + 2ac + 2bc + a^2 + b^2 + c^2 - (a^2 + b^2 + c^2))
= 1/2 * ((a+b+c)^2 - (a^2 + b^2 + c^2))

即:

int sum = 0;
int sum_sq = 0;
for (int i : arr) {
    sum += i;
    sum_sq += i*i;
}
int result = (sum*sum - sum_sq) / 2;

这是 O(n) 乘法，而不是 O(n^2)。在某些时候，这肯定比单纯的实现要好。仅仅 3 个元素是否更好是我还没有计时的事情。