我有一个包含元素 {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
是元素的数量,我需要一个更有效的算法来执行此操作,但我没有知道怎么做,有人可以帮我吗?
谢谢!
最佳答案
在一般情况下你可以做得更好。是时候做一些数学了。让我们看看 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 个元素是否更好是我还没有计时的事情。
关于c++ - 两个相乘的每个子集的加法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42444616/