计算数组中所有对和平方和的有效解决方案是什么？

What is the efficient solution for computing the sum of all pair sum square in an array?

给定一个数组 $A[0\cdots n-1]$ 我们需要计算 $\sum_{i = 0}^{n-1}\sum_{j=0}^{n-1}\left((A[i] + A[j]) \times (A[i] + A[j])\right)$ 。 time-efficient 解的运行时间是多少？

我认为方程time-efficient解的运行时间

$S=\sum_{i = 0}^{n-1}\sum_{j=0}^{n-1}\left((A[i] + A[j]) \times (A[i] + A[j])\right)$

将是 n^2（二次时间）但解是 n（线性时间）.

有人能给我解释一下吗n（线性时间）？

只是你需要重写公式。内部公式是 $(A[i] + A[j])\times (A[i] + A[j]) = A[i]^2 + A[j]^2 + 2 A[i]A[j]$ 。因此，你可以取出 $A[i]$ 来自内部总和：

$\sum_{i = 0}^{n-1}\left(n \times A[i] + \sum_{j = 0}^{n-1}\left(A[j]^2\right) + 2A[i] \times \sum_{j = 0}^{n-1}\left(A[j]\right)\right)$

现在我们只需要计算 $B= \sum_{j = 0}^{n-1}(A[j]^2)$ , $C = \sum_{j = 0}^{n-1}(A[j])$ , 和 $\sum_{i = 0}^{n-1}(n \times A[i] + B + 2A[i] \times C)$ 。由于每个都可以在 O(n) 中完成，我们可以在 O(n).

中找到最终结果

请注意，您可以在 O(n^2) 中通过两个嵌套循环（如您所说）来完成。但它没有优化。您也可以在矩阵乘法 (Strassen algorihtm) 中找到类似的技术。

计算数组中所有对和平方和的有效解决方案是什么？

What is the efficient solution for computing the sum of all pair sum square in an array?

algorithm

time-complexity