有没有一种好方法来优化迭代次数相乘的嵌套 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结果和 for 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;