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

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

主要内容

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

最大子序列和问题

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

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

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

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);
}

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

若若

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

矩阵乘法的Strassen算法

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

若若

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

若若

得到的解为，其中，优于前面的算法。

求解递归式

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

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

主定理描述如下：令和是常数，是一个函数，是定义在非负整数上的递归式：

其中，将解释为或，那么有如下渐近界：

  1. 若对某个常数有，则
  2. 若，则
  3. 若对某个常数有，且对某个常数和所有足够大的，有，则

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

习题解答

练习题

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 解答：本题需要为最大子序列和问题实现一个线性时间的算法。思想如下：从数组的左边界开始，从左至右处理，记录到目前为止已经处理过的最大子数组。若已知的最大子数组，基于如下性质将解扩展为的最大子数组：的最大子数组要么是的最大子数组，要么是某个子数组。实现代码如下：

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. ，此时，，，，由于，其中，因此根据主定理，
  2. ，此时，，，，由于，因此根据主定理，
  3. ，此时，，，，由于，其中，且对某个常数和所有足够大的有，因此根据主定理，
  4. ，此时，，，，由于，其中，且对某个常数和所有足够大的有，因此根据主定理，