算法比较

最大连续子段和：求\(\max\sum\limits_{k=i}^jA_k\).

算法1：暴力枚举端点 \(T(N)=O(N^3)\)

int MaxSubsequenceSum(const int A[], int N) {
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for (i = 0; i < N; i++)
        for (j = i; j < N; j++) {
            ThisSum = 0;
            for (k = i; k <= j; k++)
                ThisSum += A[k];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}

问题：存在重复计算

算法2：暴力枚举端点 \(T(N)=O(N^2)\)

int MaxSubsequenceSum(const int A[], int N) {
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for (i = 0; i < N; i++) {
        ThisSum = 0;
        for (j = i; j < N; j++) {
            ThisSum += A[j];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

算法3：分治

• 递：分别求解左右区间的最大子段和
• 归：求解跨越中点的最大子段和：从中间向两端扫描

复杂度：\(T(N)=2T(N/2)+cN,\quad T(1)=O(1)\)

\(T(N)=2^kO(1)+cKN\quad \therefore T(N)=O(N\log N)\)

int MaxSubsequenceSum(const int A[], int l, int r) {
    if (l == r) return max(A[l], 0);
    int LeftSum, RightSum, MidSum, mid;
    mid = (l + r) << 1;
    LeftSum = MaxSubsequence(A, l, mid);
    RightSum = MaxSubsequence(A, mid + 1, r);
    int LeftMax = 0, RightMax = 0, ThisSum = 0;
    for (int i = mid; i >= l; i--) {
        ThisSum += A[i];
        LeftMax = max(LeftMax, ThisSum);    
    }
    ThisSum = 0;
    for (int i = mid + 1, i <= r; i++) {
        ThisSum += A[i];
        RightSum = max(RightSum, ThisSum);
    }
    MidSum = LeftSum + RightSum;
    return max(max(LeftSum, RightSum), MidSum);
}

算法4：贪心（在线算法） \(T(N)=O(N)\)

原理：\(f(n)=\max\set{0,f(n-1)+A_n}\)

int MaxSubsequenceSum(const int A[], int N) {
    int ThisSum, MaxSum, j;
    ThisSum = MaxSum = 0;
    for (j = 0; j < N; j++) {
        ThisSum += A[j];
        if (ThisSum > MaxSum) MaxSum = ThisSum;
        else if (ThisSum < 0) ThisSum = 0;
    }
    return MaxSum;
}

对数时间复杂度：

• 二分查找 \(T(N)=O(\log N)\)

  int BinarySearch(const ElementType A[], ElementType X, int N) {
      int Low, Mid, High;
      Low = 0, High = N - 1;
      while (Low <= High) {
          Mid = (Low + High) / 2;
          if (A[Mid] < X) Low = Mid + 1;
          else { 
              if (A[Mid] > X) High = Mid - 1;
              else return Mid;
      }
      return NotFound;
  }
  

算法分析检查：\(T(N)=O(f(N))\Leftrightarrow\lim\limits_{N\to\infty}\dfrac{T(N)}{f(N)}\approx Constant\)