c# - 有没有一种好的方法来优化迭代次数相乘的嵌套 for 循环？

Question

我有一个 for 循环，它通过将循环中的值相乘来创建和:

int i;
int j;

float total = 0;
int x = 1000;

for (i = 0; i < x; i++)
{
    for (j = 0; j < x; j++)
    {
        total += i * j;
    }
}

有没有更好的方式来写这个？当 x 变得较大时，处理所需的时间长得令人难以置信。

我的研究表明嵌套 for 循环已经足够好了，但我想知道是否有办法简化它。

Answer 1

您根本不需要嵌套循环，给定 x 的闭合公式是

total = x * x * (x - 1) * (x - 1) / 4;

请注意整数溢出(注意 long 结果和 x )

long x = 1000;
long total = x * x * (x - 1) * (x - 1) / 4;

编辑:让我们看一下一般情况，我们必须处理任意数字，比如数组 a和 b :

long total = 0;

for (int i = 0; i < a.Length; ++i)
  for (int j = 0; j < b.Length; ++j)
    total += a[i] * b[j];

在这种情况下，我们无法提出闭合公式，但我们可以优化 计算。我们正在寻找 total的

  a[0] * b[0] + a[0] * b[1] + ... + a[0] * b[m] +
  a[1] * b[0] + a[1] * b[1] + ... + a[1] * b[m] +
  ...
  a[n] * b[0] + a[n] * b[1] + ... + a[n] * b[m] = 


= a[0] * (b[0] + b[1] + ... + b[m]) +
  a[1] * (b[0] + b[1] + ... + b[m]) +
  ...
  a[n] * (b[0] + b[1] + ... + b[m]) =


= (a[0] + a[1] + ... a[n]) * (b[0] + b[1] + ... + b[m])  

到目前为止一切顺利，而不是嵌套循环和O(n * m)复杂性我们有两个分开的循环并且只有O(n + m)时间复杂度。

我们经常在 Linq 的帮助下完成此类任务:

using System.Linq;

...

long total = a.Sum(item => (long) item) * b.Sum(item => (long) item)

但是你可以很好地使用旧的循环:

long sumA = 0;

foreach (var item in a)
  sumA += item;

long sumB = 0;

foreach (var item in b)
  sumB += item;

long total = sumA * sumB;