『算法导论』第 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 解答:

a)$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}$
b)$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$
c)$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)$
d)$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)$

思考题

待完成。