分治算法就是简单递归?当然不是的,里边儿可有大学问。

零、渐进记号:

  • 对一个给定函数 g(n),用 Θ(g(n)) 来表达以下函数的集合:

    Θ(g(n)) = { f(n):存在正常量 $C_1$,$C_2$ 和 $n_0$,使得对所有 $n \geq n_0$,有 $0 \leq C_1g(n) \leq C_2g(n)$ }

    Θ 记号渐进地给出一个函数的上界和下界。

  • 对一个给定函数 g(n),用 O(g(n)) 来表达以下函数的集合:

    O(g(n)) = { f(n):存在正常量 $C$ 和 $n_0$,使得对所有 $n \geq n_0$,有 $0 \leq f(n) \leq Cg(n)$ }

    O 记号渐进地给出一个函数的上界

  • 对一个给定函数 g(n),用 Ω(g(n)) 来表达以下函数的集合:

    Ω(g(n)) = { f(n):存在正常量 $C$ 和 $n_0$,使得对所有 $n \geq n_0$,有 $0\leq Cg(n) \leq f(n) $ }

    Ω 记号渐进地给出一个函数的下界

  • 对一个给定函数 g(n),用 o(g(n)) 来表达以下函数的集合:

    o(g(n)) = { f(n):存在正常量 $C$ 和 $n_0$,使得对所有 $n \geq n_0$,有 $0 \leq f(n) < Cg(n)$ }

    o 记号表示一个非渐进紧确的上界

  • 对一个给定函数 g(n),用 ω(g(n)) 来表达以下函数的集合:

    ω(g(n)) = { f(n):存在正常量 $C$ 和 $n_0$,使得对所有 $n \geq n_0$,有 $0\leq Cg(n) < f(n)$ }

    ω 记号表示一个非渐进紧确的下界


一、分治算法介绍:

将原问题分解成几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题地解来建立原问题的解。

分治模式在每层递归时都有三个步骤:

  • 分解原问题为若干子问题,这些子问题是原问题规模较小的实例。
  • 解决这些子问题,递归地求解各子问题。然而,如果子问题的规模足够小,则直接求解。
  • 合并这些子问题的解成原问题的解。

递归式是和分治方法密切相关的,因为使用递归式可以很自然地刻画分治算法的运行时间。一个递归式是一个恒等式或者不等式,它通过更小的输入上的函数值来描述一个函数。相信很多读者对递归的印象都是:时空开销大,确实,在一些情况下基于分治思想的递归算法并不优于平凡算法;但是在另外的情况递归算法有着不错的性能。因此,我们需要懂得如何评判递归算法的开销。

此处将介绍三种求解递归式的渐进界方法:

  1. 代入法:我们猜测一个界,然后用数学归纳法证明这个界是正确的。
  2. 递归树法:将递归式转化为一棵树,其节点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
  3. 主方法(本文采用):可求解形如下述公式的递归式的界:$T(n)=aT(n/b)+f(n)$。其中 $a \geq 1$,$b>1$,f(n) 是一个给定常数。(上述递归式刻画了这样一个分治算法:生成 a 个子问题,每个子问题的规模是原问题的 1/b,分解和合并步骤总共花费时间为 f(n))

接下来我们将运用上述三种方法来介绍如何求解递归式

1. 代入法

  • Step1:猜测解的形式
  • Step2:用数学归纳法求解的常数

以式子 $T(n)=2T(\lfloor \frac{n}{2} \rfloor lg(\lfloor \frac{n}{2} \rfloor))$ 为例:

首先我们依据经验进行猜测,猜测其解为 $T(n)=O(nlgn)$。代入要求证明,恰当选择常数 $c>0$,可有 $T(n) \leq cnlgn$。

然后我们对此前的假设进行证明

  1. 我们假设此上界对所有正数 $m < n$ 都成立,特别是对于 $m = \lfloor \frac{n}{2} \rfloor$,有 $T(\lfloor \frac{n}{2} \rfloor)\leq c\lfloor \frac{n}{2} \rfloor lg(\lfloor \frac{n}{2} \rfloor)$。

  2. 将其带入递归式,得:$T(n)\leq 2(c\lfloor \frac{n}{2} \rfloor lg\lfloor \frac{n}{2} \rfloor)+n \leq cnlg(\lfloor \frac{n}{2} \rfloor)+n = cnlgn-cnlg2+n = cnlgn-cn+n \leq cnlgn$($c\geq 1$)

  3. 很容易发现上述推导存在边界限制条件 $c\geq 1$,而数学归纳法要求我们证明解在边界条件也成立:

    假设 $T(1)=1$ 是递归式唯一边界条件。则对于 $n=1$,边界条件 $T(n)\leq cnlgn \Rightarrow T(1)\leq c1lg1=0$,与 $T(1)=1$ 矛盾。

发现矛盾之后,我们不应慌乱。因为渐进符号仅要求 $n \geq n_0$ 时 $T(n) \leq cnlgn$,其中 $n_0$ 是可自行选择的常数。我们可令 $n_0=2$,很容易算出 $T(2)=4$,$T(3)=5$,两式均能满足约束(选择足够大的 c 即可)。

2. 用递归式求解

此处我们举例:$T(n)=3T(\lfloor \frac{n}{4} \rfloor) + \Theta(n^2)$

可以将上式构造为如下递归树(小量 $\Theta(n^2)$ 可省略),每一个节点的数字为节点代价,左侧蓝色字迹为一层的节点代价之和。

我们对上图的最底层进行分析:依据树的基础知识,树的最底层深度为 $log_4n$,有 $3^{log_4n}=n^{log_43}$ 个节点,每个节点的代价为 $T(1)$,因此,最底层总代价为 $n^{log_43}T(1)$,即 $\Theta(n^{log_43})$。

现在让我们来求所有层次的代价之和,确定整棵树的代价

$T(n)=cn^2+\frac{3}{16}cn^2+{(\frac{3}{16})}^2cn^2+…+{(\frac{3}{16})}^{log_4{n-1}}cn^2+\Theta (n^{log_43})$

$=\sum_{i=0}^{log_4{n-1}}{(\frac{3}{10})}^icn^2 + \Theta(n^{log_43}) $

$< \sum_{i=0}^{\infty}{(\frac{3}{16})}^icn^2+\Theta(n^{log_43})$

$=\frac{1}{1-(\frac{3}{16})}cn^2+\Theta(n^{log_43})$

$=\frac{16}{3}cn^2+\Theta(n^{log_43})$

$=O(n^2)$

至此,对于原始递归式 $T(n)=3T(\lfloor \frac{n}{4} \rfloor) + \Theta(n^2)$,我们推导出了一个猜测 $T(n)=O(n^2)$

现在利用代入法对猜测进行验证,即证明 $T(n)\leq dn^2 \ (d>0)$:

$T(n) \leq 3T(\lfloor \frac{n}{4}\rfloor)+cn^2$

$\leq 3d(\frac{n}{4})^{2}+cn^2$

$=\frac{3}{16}dn^2+cn^2$

$\leq dn^2 \ \ \ \ (d\geq \frac{16}{3}c时)$

3. 用主成分方法求解

主方法为形如 $T(n)=aT(\frac{n}{b})+f(n)\ \ (a\geq1,b>1,f(n)为渐进正函数)$ 形式的递归式提供了一种“菜谱式”的求解方法

递归式的涵义为:将规模为 n 的问题分解为 a 个子问题,每个子问题的规模为 $\frac{n}{b}$。a 个子问题递归地进行求解,每个花费的时间为 $T(\frac{n}{b})$

从技术正确性来看,此递归式实际上并不是良好定义的,因为 $\frac{n}{b}$ 可能并不是整数。但将 a 项 $T(\frac{n}{b})$ 都替换为 $T(\lceil \frac{n} {b}\rceil)$ 或 $T(\lfloor \frac{n} {b}\rfloor)$ 并不会影响递归式地渐进性质。

主定理:令 $a \geq 1$ 和 $b > 1$ 是常数,f(n) 是一个函数,T(n) 是定义在非负整数上的递归式:$T(n)=aT(\frac{n}{b})+f(n)$

$T(n)$ 有如下渐进界(三种情况):

  1. 若对某个常数 $\epsilon > 0$ 有 $f(n)=O(n^{log_ba-\epsilon})$,则 $T(n)=\Theta(n^{log_ba})$
  2. 若 $f(n)=\Theta(n^{log_ba})$,则 $T(n)=\Theta(n^{log_ba}lgn)$
  3. 若对某个常数 $\epsilon > 0$ 有 $f(n)=\Omega(n^{log_ba-\epsilon})$,且对某个常数 $c < 1$ 和所有足够大的 n 有 $af(\frac{n}{b})\leq cf(n)$,则 $T(n) = \Theta(f(n))$

换句话说,就是**比较 $n^{log_ba}$ 和 $f(n)$**,凭借“朴素”的数学知识,如果 $f(n)$ 和 $n^{log_ba}$ 大小相当,则对应情况 2;如果 $f(n)$ 远小于 $n^{log_ba}$ ,则两者之和可以忽略 $f(n)$,对应情况 1;如果 $f(n)$ 远大于 $n^{log_ba}$ ,则两者之和可以忽略 $n^{log_ba}$,对应情况 3。

举例:$T(n)=9T(\frac{n}{3})+n$ (此处 $a=9$,$b=3$,$f(n)=n$)

则我们可以利用主成分方法,$n^{log_ba}=n^{log_39}=\Theta(n^2)$,可得 $f(n)=O(n^{log_39-\epsilon})$,其中 $\epsilon=1$,对应主定理的情况1,从而可以得到 $T(n)=\Theta(n^2)$


二、分治算法 · Strassen 矩阵乘法:

我们熟知矩阵乘法的计算规则:$c_{ij}=\sum_{k=1}^{n} a_{ik}b_{kj}$,

常规方法进行编码(伪代码):

1
2
3
4
5
for i = 1 to n
for j = 1 to n
cij = 0
for k = 1 to n
Cij = Cij + aij * bij

这种方法的时间复杂度为 $O(n^3)$。而使用 Strassen 方法可以得到 $O(n^{2.81})$ 的时间复杂度。

Strassen 方法采用了分治的思想,对矩阵 A,B,C 和 C = A $\times$ B进行分解:

C = A $\times$ B $\Rightarrow $ $\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix} = \begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix} \times \begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}$

如果直接将矩阵的乘法展开,我们可以得到下式:

$\begin{cases} C_{11}=A_{11}\times B_{11} + A_{12}\times B_{21} \\C_{12}=A_{11}\times B_{12} + A_{12}\times B_{22} \\C_{21}=A_{21}\times B_{11} + A_{22}\times B_{21} \\C_{22}=A_{21}\times B_{12} + A_{22}\times B_{22}\end{cases} $

但不难发现,展开式并不能帮助我们减少时间复杂度(因为没有减少举证乘法的计算次数)。

Strassen 方法提出了 7 个多项式:

$\begin{cases} M_{1}=A_{11}(B_{12}-B_{22}) \\M_{2}=(A_{11} + A_{12})\times B_{22} \\M_{3}=(A_{21}+A_{22})\times B_{11} \\M_{4}=A_{22}(B_{21}-B_{11}) \\M_{5}=(A_{11}+A_{22})(B_{11}+B_{22}) \\M_{6}=(A_{12}-A_{22})(B_{21}+B_{22}) \\M_{7}=(A_{11}-A_{21})(B_{11}+B_{12})\end{cases} $

将上述 7 个式子进行线性组合,即可得到 $C_1$,$C_2$,$C_3$,$C_4$。

$\begin{cases} C_{11}=M_5+M_4-M_2+M_6 \\ c_{12}=M_1+M_2 \\ c_{21}=M_3+M_4 \\ c_{22}=M_5+M_1-M_3-M_7 \end{cases}$

该算法的递归方程为:$T(n)=\begin{cases} O(1)& \text{n=2} \\7T(\frac{n}{2})+O(n^2)& \text{n>2} \end{cases}$

可以利用主成分方法求解递归式得到:$T(n)=O(n^{log7})=O(n^{2.81})$

(本例涉及较多的矩阵运算,且算法以数学思想为主)

(各主流编程语言均提供了矩阵运算的库函数,实现较为简单,此处不再提供代码实现。)


三、分治算法 · 最大子序和:

https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

我们可以将上述问题视作求数组 $A[low,high]$ 的最大子序和,同时将最终解答最大子序和记作 $A[i, j]$。

$A[i,j]$ 的位置有三种情况:

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

对于情况 1 和 2,我们都可以递归求解,将子问题分解成规模更小的子子问题;对于情况 3,我们可以将 $A[i,…,mid,…,j]$ 视为 $A[i,mid]$ 和 $A[mid+1,j]$ 的并集,只需要将两侧的结果合并即可。

我们**将对情况 3 的处理单独抽象为函数 maxCrossingSum**:因为是跨 mid 的区间,所以必然是包含 A[mid] 和 A[mid + 1]。因此,为了保证所求得的最大和为连续区间,我们将以 A[mid] 和 A[mid + 1] 为中心,分别向两边遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int maxCrossingSum (int[] nums, int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// 处理[left, mid]间的数据(从mid开始自右向左,维护最大和)
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) leftSum = sum;
}
// 处理[mid+1, right]间的数据(从mid+1开始自左向右,维护最大和)
sum = 0;
for (int i = mid; i >= right; i--) {
sum += nums[i];
if (sum > rightSum) rightSum = sum;
}
// 返回两侧最大和的和
return leftSum + rightSum;
}

接下来这个函数是分治算法的核心部分:按照我们此前的分析,将研究对象以 mid 为中心,分成三种情况,不断递归,减小问题的规模。最后的所求即为三种情况的最大值。当递归至最小问题规模时(即研究区间仅一个元素),则最大子序和即为其本身。

1
2
3
4
5
private int maxSubArraySum (int[] nums, int left, int right) {
if (left == right) return nums[left]; // 最小问题规模
int mid = (left + right) / 2;
return max3(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid + 1, right), maxCrossingSum(nums, left, mid, right));
}

此处的 max3(a, b, c) 函数即为求 a,b,c 之前的最大值,实现如下:

1
2
3
private int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}

最后将处理边界情况、计算数组长度和主算法的调用封装在一起,“为主函数减肥”。

1
2
3
4
5
public int maxSubArray(int[] nums) {
int len = num.length;
if (len == 0) return 0;
return maxSubArraySum(nums, 0, len - 1);
}

我们对上述算法做一个总结:

递归式为 $T(n)=\begin{cases} \Theta(1)& \text{若 n = 1} \\2T(\frac{n}{2})+\Theta(n)& \text{若 n > 1} \end{cases}$

使用主成分方法求解递归式得:$T(n)=\theta(nlnn)$


四、总结:

​ 分治的思想就是将复杂问题分解为数个相同但规模较小的子问题,不断递归,减小问题规模,直至可以简单解决。然而,有时分治递归会存在较高的时间复杂度,我们需要具备计算我们所提出的递归式的时间复杂度(见第一章)。本文详细介绍了三种方法,其中代入法递归式求解法需要一定的数学基础,因此若递归式满足主成分方法的要求,我们一般使用主成分方法快速求解递归式



> 参考资料:《算法导论(原书第三版)》、《计算机算法设计与分析(第五版)》