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

主要内容

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

最大子序列和问题

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

用暴力解法求解该问题,运行时间为\(\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)\)