c# - 我可以有一个更快的嵌套循环来降低算法复杂度吗？

Question

我有一个新手问题。

假设我有以下简单的嵌套循环，其中m和n不一定相同，但都是非常大的数字：

x = 0;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      delta = CalculateDelta(i,j);
      x = x + j + i + delta;
   }
}

现在我有了这个：

x = 0;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      delta = CalculateDelta(i,j);
      x = x + j + i + delta;

      j++;

      delta = CalculateDelta(i,j);
      x = x + j + i + delta;
   }
}

规则：由于这个增量计算，我确实需要遍历循环的所有元素。

我的问题是：

1）第二种算法比第一种算法快，还是一样？我有这个疑问，因为对我来说第一个算法的复杂度为 O(m * n)，而第二个算法的复杂度为 O(m * n/2)。还是不需要较低的复杂性使其更快？

2）有没有其他方法可以在没有类似 a 的情况下加快速度Parallel. For？

3）如果我使用 a Parallel. For，它真的会更快吗，因为我可能需要对x变量进行同步锁定？

谢谢！

标签： c#.nettime-complexitycomputation-theorycode-complexity

Answer 1

绝对不是，因为时间复杂度可能由被调用的次数决定CalculateDelta()，无论你是内联调用、在单个循环内还是在任意数量的嵌套循环内调用，调用都会被调用 m*n 次。

现在你有一个错误（这就是我决定在@Peter-Duniho 已经非常全面地完成之后添加答案的原因）

如果n很奇怪，您会进行比预期更多的迭代 - 几乎可以肯定得到错误的答案或使您的程序崩溃......