算法导论第 4 章：分治策略

发表于 分类于 Waline： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

主要内容

本章介绍的第一个算法求解最大子序列和问题，第二个算法求解矩阵乘法问题。递归式与分治法紧密相关，本章介绍三种方法求解递归式：代入法、递归树法和主方法。

最大子序列和问题

买股票问题可以转化为最大子序列和问题。只有当序列中包含负数，最大子序列和问题才有意义。

用暴力解法求解该问题，运行时间为\(\Theta(n^2)\)。还可以用分治法求解最大子序列和问题。将序列等分为左右两个子序列，任何连续子序列所处的位置必然式如下三种情况之一：完全位于左子序列中、完全位于右子序列中以及跨越了左右序列的中点。那么，算法的工作就是先递归求解两个子序列，然后寻找跨越中点的最大子序列，最后在三种情况中选取和最大者。

书中的伪代码既求解了最大和，也返回了数组的位置。为了简化流程，我给出的代码只求解最大和。求解跨越中点的最大子序列和的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 左子序列为A[low..mid]   右子序列为A[mid+1..high]
int FindMaxCrossingSubarraySum(int A[], int low, int mid, int high)
{
    int left_sum = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i--) {
        sum += A[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }
    
    int right_sum = INT_MIN;
    sum = 0;
    for (int i = mid+1; i <= high; i++) {
        sum += A[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }
    
    return (left_sum + right_sum);
}

递归求解过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int max3(int a, int b, int c)
{
    int t = (a > b) ? a : b;
    return (t > c) ? t : c;
}

// 对于数组A[n]，调用FindMaxSubarraySum(A, 0, n-1)即可
int FindMaxSubarraySum(int A[], int low, int high)
{
    if (low == high) {
        return A[low];
    }
    
    int mid = low + (high - low)/2;
    int left_sum = FindMaxSubarraySum(A, low, mid);
    int right_sum = FindMaxSubarraySum(A, mid+1, high);
    int cross_sum = FindMaxCrossingSubarraySum(A, low, mid, high);
    
    return max3(left_sum, right_sum, cross_sum);
}

上述求解跨越中点的最大子序列和所需时间为\(\Theta(n)\)，所以上述递归解法的递归式为：

\[ T(n) = \begin{cases} \Theta(1) & \mbox{若} n=1 \\\\ 2T(n/2)+\Theta(n) & \mbox{若} n>1 \end{cases} \]

所以，它的运行时间为\(T(n) = \Theta(n \lg n)\)。其实该问题还有个线性时间的算法，并且未使用分治法，请参考习题4.1-5。

矩阵乘法的Strassen算法

根据矩阵乘法的定义去计算，运行时间为\(\Theta(n^3)\)。还可以通过将矩阵分解为子矩阵，利用分治法计算矩阵乘积，递归公式为：

\[ T(n) = \begin{cases} \Theta(1) & \mbox{若} n=1 \\\\ 8T(n/2)+\Theta(n^2) & \mbox{若} n>1 \end{cases} \]

可以利用上述递归式求得\(T(n)=\Theta(n^3)\)，并不优于直接的方法。Strassen方法的核心思想是令递归树不那么茂盛一点，只递归进行7次而不是8次，递归公式如下：

\[ T(n) = \begin{cases} \Theta(1) & \mbox{若} n=1 \\\\ 7T(n/2)+\Theta(n^2) & \mbox{若} n>1 \end{cases} \]

得到的解为\(T(n)=\Theta(n^{\lg 7})\)，其中\(\lg 7 \approx 2.81\)，优于前面的算法。

求解递归式

求解递归式有如下三种方法：

  1. 代入法：首先猜测解的形式，然后用数学归纳法求出解中的常数，并证明解时正确的。但想出一个好的猜测可能会很困难。
  2. 递归树法：画出递归树，生成好的猜测，然后利用代入法验证猜测是否正确。
  3. 主方法：直接提供一种「菜谱」式的求解方法。

主定理描述如下：令\(a \ge 1\)和\(b > 1\)是常数，\(f(n)\)是一个函数，\(T(n)\)是定义在非负整数上的递归式：

\[ T(n) = aT(n/b) + f(n) \]

其中，将\(n/b\)解释为\(\lfloor n/b \rfloor\)或\(\lceil n/b \rceil\)，那么\(T(n)\)有如下渐近界：

  1. 若对某个常数\(\epsilon>0\)有\(f(n) = O(n^{\log_b a-\epsilon})\)，则\(T(n)=\Theta(n^{\log_b a})\)
  2. 若\(f(n) = \Theta(n^{\log_b a})\)，则\(T(n) = \Theta(n^{\log_b a} \lg n)\)
  3. 若对某个常数\(\epsilon>0\)有\(f(n) = \Omega(n^{\log_b a+\epsilon})\)，且对某个常数\(c<1\)和所有足够大的\(n\)，有\(af(n/b) \le cf(n)\)，则\(T(n) = \Theta(f(n))\)

对于三种情况的每一种，我们将\(f(n)\)与函数\(n^{\log_b a}\)进行比较。直觉上，两个函数的较大者决定了递归式的解。但需要注意的是，上述三种情况并未覆盖\(f(n)\)的所有可能性，有的情况不能使用主方法来求解递归式。

习题解答

练习题

4.1-1 解答：返回整个数组中最大的数以及它的下标。

4.1-2 解答：暴力求解的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int brute(int A[], int n)
{
    int max_sum = INT_MIN;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += A[j];
            if (sum > max_sum) {
                max_sum = sum;
            }
        }
    }

    return max_sum;
}

4.1-3 解答：性能交叉点需要在机器上经过大量测试才能得到，略。修改后，性能交叉点会变小。

4.1-4 解答：最简单的办法是，将求得的最大和与0比较，取更大的一个。

4.1-5 解答：本题需要为最大子序列和问题实现一个线性时间的算法。思想如下：从数组的左边界开始，从左至右处理，记录到目前为止已经处理过的最大子数组。若已知\(A[1..j]\)的最大子数组，基于如下性质将解扩展为\(A[1..j+1]\)的最大子数组：\(A[1..j+1]\)的最大子数组要么是\(A[1..j]\)的最大子数组，要么是某个子数组\(A[i..j+1], 1 \le i \le j+1\)。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int FindMaxSubarraySum(int A[], int n)
{
    int max_sum = INT_MIN;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += A[i];
        if (sum > max_sum) {
            max_sum = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }

    return max_sum;
}

4.5-1 解答：

  1. \(T(n)=2T(n/4)+1\)，此时\(a=2\)，\(b=4\)，\(f(n)=1\)，\(n^{\log_b a} = n^{\log_4 2} = n^{0.5}\)，由于\(f(n)=O(n^{log_4 {2-\epsilon}})\)，其中\(\epsilon = 0.1\)，因此根据主定理，\(T(n)=n^{0.5}\)
  2. \(T(n)=2T(n/4)+\sqrt{n}\)，此时\(a=2\)，\(b=4\)，\(f(n)=n^{0.5}\)，\(n^{\log_b a} = n^{\log_4 2} = n^{0.5}\)，由于\(f(n)=\Theta(n^{log_4 2})\)，因此根据主定理，\(T(n)=n^{0.5} \lg n\)
  3. \(T(n)=2T(n/4)+n\)，此时\(a=2\)，\(b=4\)，\(f(n)=n\)，\(n^{\log_b a} = n^{\log_4 2} = n^{0.5}\)，由于\(f(n)=\Omega(n^{log_4 {2+\epsilon}})\)，其中\(\epsilon=2\)，且对某个常数\(c=2/3<1\)和所有足够大的\(n\)有\(2f(n/4) = n/2 \le cf(n) = 2n/3\)，因此根据主定理，\(T(n)=\Theta(n)\)
  4. \(T(n)=2T(n/4)+n^2\)，此时\(a=2\)，\(b=4\)，\(f(n)=n^2\)，\(n^{\log_b a} = n^{\log_4 2} = n^{0.5}\)，由于\(f(n)=\Omega(n^{log_4 {2+\epsilon}})\)，其中\(\epsilon=14\)，且对某个常数\(c=1/3<1\)和所有足够大的\(n\)有\(2f(n/4) = n^2/8 \le cf(n) = n^2/3\)，因此根据主定理，\(T(n)=\Theta(n^2)\)