两个子集的相加乘以

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个元素是否更好是我没有时间的东西.

Answer 2

@ chux的建议主要是重新分配操作:

a _i*a _{i + 1} + a _i*a _{i + 2} + ... + a _i*a _n

- >

a _i*(a _{i + 1} + ... + a _n)

结合避免不必要地重新计算(a _{i + 1} + ... + a _n)项的部分和,通过利用每个与输入数组的一个元素的值不同的事实.

这是一个带O(1)开销的一次通过实现:

int psum(size_t n, int array[n]) {
    int result = 0;
    int rsum = array[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        result += array[i] * rsum;
        rsum += array[i];
    }

    return result;
}

索引右侧的所有元素的总和i从迭代到变量的迭代保持不变rsum.没有必要在数组中跟踪它的各种值,因为我们只需要循环的一次迭代的每个值.

这与输入数组中的元素数量成线性比例.您会看到操作的数量和类型与@ Barry的答案非常相似,但是不需要类似于他的最后一步,这样可以省去一些操作.

正如@Barry在评论中观察到的那样,迭代也可以在另一个方向上运行,同时跟踪右手部分的左手部分和.这将与@ chux的描述略有不同,但它依赖于完全相同的原则.