c - c 中取消切换 while 循环优化

Question

我很难通过循环取消切换来优化以下 while 循环。我尝试应用 wiki 中的示例，但是我很难将其应用到 while 循环中。我有以下代码:

int n = 5,
    m = 5,
    i = 0,
    val = 0;

while (i < n ) {
  j = 0;

  while (j < m ) {
    if (i < j ) {
      val = val + i ;
    }
    else if ( j == i ) {
      val = val - 1;
    }
    else {
      val = val + j ;
    }

    j = j + 1;
  }

  i = i + 1;
}

并尝试通过以下方式取消切换:

while (i < n ) {
  j = 0;

  if (i < j ) {
    while (j < m ) {
      val = val + i;
      j = j + 1;
    }
  }

  if ( j == i ) {
    while (j < m) {
      val = val - 1;
      j = j + 1;
    }
  }

  if (i > j) {
    while (j < m) {
      val = val + j;
      j = j + 1;
    }
  }

  i = i + 1;
}

我可能做错了什么。

Answer 1

最好借助铅笔和纸展开此类环。您想要以下网格的总和:

           0   1   2   3   4  |   5   n

    0     -1   0   0   0   0  |   0   0
    1      0  -1   1   1   1  |   1   1
    2      0   1  -1   2   2  |   2   2
    3      0   1   2  -1   3  |   3   3
    m      0   1   2   3  -1  |   4   4

当 n 时，网格可以 segmentation 为三个部分:对角线、正方形部分中对角线旁边的上下三角形以及矩形 block 。和m不同。

让我们用正方形部分来表示网格的尺寸，k²和矩形部分，k·r :

    k = min(n, m)
    r = max(m, n) - k

现在您可以看到这三个部分的总和:

    val = 2·∑(k - i - 1)·i       # two triangles
        + r·∑(i)                 # rectangle
        - k                      # diagonal

(所有总和从 i = 0; i < n; i++ 开始。)该总和可以重新排列为:

    val = 2·(k - 1)·∑(i) - 2*∑(i²) + r·(i) - k
        = (2·k + r - 2)·∑(i) - 2*∑(i²) - k

这减少了两个嵌套循环，两个两个独立的循环来计算自然数及其平方的和。幸运的是，这些总和可以用简单的关系来表示:

    ∑(i) = (n - 1)·n / 2
   ∑(i²) = (2·n - 1)·(n - 1)·n / 6

现在您已经有了一个常数时间公式来计算结果总和:

    int val(int n, int m)
    {
        int k = (n < m) ? n : m;
        int r = ((n > m) ? n : m) - k;

        return (2*k + r - 2) * (k - 1) * k / 2
              - (2*k - 1) * k * (k - 1) / 3 - k;
    }

当然，所有这些与循环展开没有任何关系。