1.4.2 时间复杂度为 O ( n ² )的算法

从嵌套循环算法中删除一层循环，通常可以减少算法的运行时间。那么，怎样删除一层循环呢？答案是，不一定总能删除。例如，代码清单1-2中的算法有一些不必要的计算。在计算第 i 到第 j+ 1个元素的和时，算法用了一个循环。事实上，在上一次循环计算从第 i 到第 j 个元素的和时，已经得到了第 i 到第 j 个元素的连续子序列和。而 ，因此，只需要再做一次加法即可。利用这一结果，将代码清单1-2中最内层的循环用一个加法替代，就得到了代码清单1-3所示的改进算法。

代码清单1-3　最大连续子序列和的 O ( n ² )两重循环算法

int maxSubsequenceSum(int a[], int size, int &start, int &end) {
  int maxSum = 0;  // 已知的最大连续子序列之和
　
  for (int i = 0; i < size; i++) {    // 连续子序列的起始位置
    int thisSum = 0;                  // 从i开始的连续子序列之和
    for (int j = i; j < size; j++) {  // 连续子序列的终止位置
      thisSum+= a[j];  // 计算从第i到第j个元素的连续子序列之和
      if (thisSum > maxSum) {
        maxSum = thisSum;
        start = i;
        end = j;
      }
    }
  }
  return maxSum;
}　

代码清单1-3所示的 O ( n ² )算法有一个两重循环而不是三重循环，时间复杂度是 O ( n ² )。 Zy1WhHMoHP8SC07u8HzKGLkBGaL54IHGxCGPAyI3FGv+kXmfKDscJDa7ZRiw8XnN