第4章-分治策略

发表于 | 分类于
字数统计: 3k | 阅读时长 ≈ 13

分治策略

from 算法导论（CLRS）

分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

  • 分解：将问题划分为形式相同、规模更小的子问题。
  • 解决：递归求解子问题。
  • 合并：将子问题的解组合成原问题的解。

递归式与分治法是紧密相关的，使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个等式或不等式，它通过更小的输入上的函数值来描述一个 函数，例如：

本章将介绍三种求解递归式的方法：

  • 代入法：猜测一个界，利用数学归纳法证明该界正确。
  • 递归树法：将递归式转换成一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
  • 主方法：求解形如 $T(n) = aT(n/b) + f(n)$ 的递归式的界。

在声明、求解递归式时，我们常常忽略向下取整、向上取整及边界条件等细节。

4.1 最大子数组问题

问题描述 股票低价买入，高价卖出使得收入最大。寻找使得收入最大的买入、卖出日期。

问题变换 考虑每日价格的变化值，可使该问题可以转化为下述最大子数组问题——寻找数组 A 的和最大的非空连续子数组。

使用分治策略的求解方法

假定我们要寻找子数组 $A[low..high]$ 的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。然后考虑求解两个子数组 $A[low..mid]$ 和 $A[mid+1..high]$ 。那么 $A[low..high]$ 任意连续子数组 $A[i..j]$ 所处的位置有以下三种可能：

  1. 完全位于子数组 $A[low..mid]$ 中
  2. 完全位于子数组 $A[mid+1..high]$ 中
  3. 跨越了中点

前两种情况仍是最大子数组问题，只是规模更小。因此我们只需寻找跨越中点的最大子数组，然后在三种情况中选取和最大者。

我们很容易在线性时间内求出跨越中点的最大子数组。此问题并非原问题规模更小的实例，因为它加入了限制——求出的子数组必须跨越中点。任何跨越中点的子数组都由两个子数组 $A[i..mid]$ 和 $A[mid+1..j]$ 组成。因此我们只需找出形如 $A[i..mid]$ 和 $A[mid+1..j]$ 的最大子数组，然后将其合并即可。

函数 FIND-MAX-CROSSING-SUBARRAY 返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high):
left_sum = - inf
sum = 0
for i = mid downto low
	sum = sum + A[i]
	if sum > left_sum
		left_sum = sum
		max_left = i
right_sum = - inf
sum = 0
for j = mid+1 to high
	sum = sum + A[j]
	if sum > right_sum
		right_sum = sum
		max_right = j
return (max_left, max_right, left_sum+right_sum)

有了线性时间的 FIND-MAX-CROSSING-SUBARRAY 函数，我们就可以设计求解最大子数组问题的分治算法的伪代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
	return(low, high, A[low])	// base case: only one element
else 
	mid = (low+high)/2
	(left_low, left_high, left_sum) = 
		FIND-MAXIMUM-SUBARRAY(A, low, mid)
	(right_low, right_high, right_sum) = 
		FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
    (cross_low, cross_high, cross_sum) = 
		FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
	if left_sum >= right_sum && left_sum >= cross_sum
		return (left_low, left_high, left_sum)
	else if right_sum >= left_sum && right_sum >= cross_sum
		return (right_low, right_high, right_sum)
	else
		return (cross_low, cross_high, cross_sum)

分治算法的分析

接下来，我们建立一个递归式来描述上述递归过程的运行时间。对问题进行简化，假设原问题的规模为 2 的幂，这样所有子问题的规模均为整数。我们用 $T(n)$ 表示 FIND-MAXIMUM-SUBARRAY 求解 n 个元素的最大子数组的运行时间。首先

当 n > 1 时为递归情况。每个子问题为 $T(n/2)$，而调用 FIND-MAX-CROSSING-SUBARRAY 函数的时间为 $\Theta(n)$

所以

我们可以用主方法求得 $T(n) = \Theta(n \lg n)$。

4.2 矩阵乘法的 Strassen 算法

若 $A = (a_{ij})$ 和 $B = (b_{ij})$ 是 $n \times n$ 的方阵，则对 $i, j = 1, 2, \dots, n$，定义乘积 $C = A \cdot B$ 中的元素 $c_{ij}$ 为：

我们需要计算 $n^2$ 个矩阵元素，每个元素是 $n$ 个值的和，矩阵乘法算法如下所示：

1
2
3
4
5
6
7
8
9
SQUARE-MAXTRIX-MULTIPLY（A,B）
n = A.rows
let C be a new n × n matrix
for i = 1 to n
	for j = 1 to n
		c_ij = 0
        for k = 1 to n
        	c_ij = c_ij + a_ik·b_kj
return C

这是一个 $\Theta(n^3)$ 的算法，你最初可能认为任何矩阵乘法都要花费 $\Omega(n^3)$ 时间，因为矩阵乘法的自然定义就需要进行这么多次的标量乘法。但是这是错误的，本节将介绍 Strassen 著名的 $n \times n$ 矩阵相乘的递归算法，其时间复杂度为 $\Theta(n^{lg7})$

简单的分治算法

为简单起见，使用分治算法计算矩阵积 $C = A \cdot B$ 时，假定三个矩阵均为 $n \times n$ 矩阵，其中 $n$ 为 2 的幂。我们做出这样的假设是因为在每个分解步骤中，$n \times n$ 的矩阵都被划分为 4 个 $n/2 \times n/2$ 的子矩阵。

因此，可以将公式 $C = A \cdot B$ 改写为：

该公式等价于如下四个等式：

每个公式对应两对 $n/2 \times n/2$ 矩阵的乘法及 $n/2 \times n/2$ 积的加法。我们可以利用这些公式设计一个直接的递归分治算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B):
	n = A.rows
	let C be a new n*n matrix
	if n == 1:
		c11 = a11 * b11
	else partition A, B and C
		C11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B11)
		+ SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B21)
		C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B12)
		+ SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B22)
		C21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B11)
		+ SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B21)
		C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B12)
		+ SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B22)
	return C

这段伪代码掩盖了一个微妙但重要的实现细节：如何实现分解矩阵？我们无需创建新的矩阵，只需要使用下标即可，这样通过下表计算指明子矩阵使得分解矩阵的复杂度变为了 $\Theta(1)$。那么整个算法的时间复杂度满足：

根据主算法，我们可以求出该分治算法的时间复杂度为：

因此，简单的分治算法并不优于直接的矩阵相乘过程。

Strassen 方法

Strassen 算法的核心思想是令递归树不那么茂盛一点，即只递归 7 次而不是 8 次。减少一次矩阵乘法带来的代价可能是额外几次加法，但只是常数次。

Strassen 算法不那么直观，它包含 4 个步骤：

  1. 将输入矩阵 $A$, $B$ 和输出矩阵 $C$ 分解为子矩阵。（$\Theta(1)$）
  2. 创建 10 个 $n/2 \times n/2$ 的矩阵 $S_1, S_2, \dots, S_{10}$ ，每个矩阵保存步骤 1 中创建的两个子矩阵的和或差。($\Theta(n^2)$)
  3. 用步骤 1 中创建的子矩阵和步骤 2 中创建的 10 个矩阵，递归地计算 7 个矩阵积 $P_1, P_2, \dots, p_7$ 。每个矩阵 $P_i$ 都是 $n/2 \times n/2$ 的。
  4. 通过 $P_i$ 矩阵的不同组合进行加减运算，得到矩阵 $C$ 的子矩阵 $C_{11}, C_{12}, C_{21}, C_{22}$。花费时间 $\Theta(n^2)$。

那么， Strassen 算法运行时间 $T(n)$ 的递归式为：

我们用常数次矩阵加法的代价减少了一次矩阵乘法的代价，这样得到的时间复杂度为：$T(n) = \Theta(n^{\lg 7})$。

我们来深入 Strassen 算法的一些细节。在步骤 2 中，创建如下 10 个矩阵：

由于必须进行 10 次 $n/2 \times n/2$ 矩阵的加减法，因此，该步骤花费 $\Theta(n^2)$ 时间。

在步骤 3 中，递归计算 7 次 矩阵乘法：

在步骤 4 中，对步骤 3 创建的 $P_i$ 矩阵进行加减法运算，计算出 $C$ 的 4 个子矩阵。

这样，我们确实降低了矩阵乘积的时间复杂度。

4.5 用主方法求解递归式

定理 4.1（主定理）：令 $a \geq 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个函数，$T(n)$ 是i定义在非负整数上的递归式：

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

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

习题

习题 1

习题 2