分治法及应用（附练习）_离散数学分治算法例题

基本思想

分治是一个简单但是非常有效的算法，它的思想也很简单，就是将原问题分成几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再将这些问题的结果合并，就得到的原问题的解。
分治法每层的递归都有三个步骤：

1. 分解
2. 递归
3. 合并

本篇文章就介绍几个经典的应用分治算法的例子，并且附带练习题

本文会有很多算法的时间复杂度需要解递归，这里先将主定理给出，之后我会专门写一篇文章介绍接递归的各种方法
主定理只能应用于形如$T(n)=aT(n/b)+f(n)$的递归式，并且其中$a\ge 1,b>1,对于f(n)，\exists n_0\in R，s.t.n>n_0时，f(n)>0$
时间复杂度通过比较$f(n)$和$n^{lo{g}_b^a}$
$Case1:$当$f(n)=O(n^{lo{g}_b^a-\epsilon })，\epsilon >0$，$T(n)=\Theta (n^{lo{g}_b^a})$
$Case2:$当$f(n)=\Theta (n^{lo{g}_b^a}\cdot {\lg }_{}^{k+1}a)，k\ge 0$，$T(n)=\Theta (n^{lo{g}_b^a}\cdot {\lg }_{}^{k}a)$
$Case3:$当$f(n)=\Omega (n^{lo{g}_b^a+\epsilon })，\epsilon >0$，$T(n)=\Theta (f(n))$

归并排序

归并排序的思路也很简单

1. 分解：分解待排序的$n$个元素分成两个具有$n/2$个元素的子序列
2. 递归：递归将各个子序列排序
3. 合并：合并已经拍好的子序列

实现代码：

void part_sort(int* arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int* L = new int[n1+1];
    int* R = new int[n2+1];
    //将[l,m],[m+1,r]分别拷贝到两个新数组中
    for (int i = 0; i < n1; ++i)L[i] = arr[l + i];
    for (int i = 0; i < n2; ++i)R[i] = arr[m + i + 1];
    L[n1] = INT_MAX, R[n2] = INT_MAX;//将两个数组的末尾赋为INT_MAX作为哨兵位，可以简化代码
    //按降序将两个数组合并
    //如果排升序就要改变哨兵位的值位INT_MIN
    int i = 0, j = 0;
    for (int k = l; k <= r; ++k) {
        if (L[i] > R[j])arr[k] = R[j++];
        else arr[k] = L[i++];
    }
}
void merge_sort(int* arr, int l,int r) {
    if (l >= r)return;
    //分解
    int mid = (l + r) / 2;
    //递归
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    //排序
    part_sort(arr, l, mid, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

下面我们分析一下归并排序的时间复杂度，有人会说，这很简单呀，不就是$O(nlogn)$嘛，但是它是怎么怎么推出来的，大多数人学这个算法应该是通过画递归树来求得的（反正我第一次学是这样），这里有更严谨的方法

首先分析一下算法的消耗，递归的时间消耗是$2T(n/2)$，就是分成左右两个$n/2$的子序列嘛，之后是排序每个子序列的消耗是$\Theta (n)$，所以就能得到这个时间消耗的表达式
$$T(n)=\{\begin{array}{cc}\Theta (1)& n=1\\ 2T(n/2)+\Theta (n)& n>1\end{array}$$
再由主定理解这个递归式，$f(n)=\Theta (n^{lo{g}_b^a}l{g}^{k}n)$，是情况二，且$k=0$，就得出$T(n)=\Theta (n^{lo{g}_b^a}l{g}^{k+1}n)=\Theta (nlogn)$。归并排序是一个比较基础的排序，但是也很重要，这里给一道归并排序的练习题：习题

快速幂

之前的文章已经讲过了 详解快速幂（附习题）

斐波那契数列

斐波那契数列应该没人不知道吧，以防万一我先把斐波那契数列的定义写下：
F i = { 0 i = 0 1 i = 1 F i − 1 + F i − 2 i > 1 F_i= \left\{

$$\begin{matrix} 0 & i=0\\ 1 & i=1\\ F_{i-1}+F_{i-2} &i>1 \end{matrix}$$ \right. Fi​=⎩ ⎨ ⎧​01Fi−1​+Fi−2​​i=0i=1i>1​
求斐波那契数列有很多方法，下面我们一一介绍

1.递归求解

直接递归求解，将$F_i$分成$F_{i-1}$和$F_{i-2}$，当$i=0$或$i=1$时分别返回$0$和$1$

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1)return 1;
    return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5

这个方法很简单，但缺点也很明显时间复杂度太高，是指数级的$O({\varphi }^n)$（$\varphi$是黄金分割率）

2.线性dp

int fib(int n) {
    int* F = new int[n+1];
    F[0] = 0, F[1] = 1;
    for (int i = 2; i <= n; ++i) F[i] = F[i - 1] + F[i - 2];
    int res=F[n];
    delete[] F;
    return res;
}
1
2
3
4
5
6
7
8

时间复杂度是线性的$O(n)$，空间复杂度也是$O(n)$，可以将数组该成三个变量来递推也可以，空间复杂度就成$O(1)$了

3.公式法

这里涉及二阶常系数线性齐次差分方程的求解，不了解的可以先了解一下这方面的知识

由斐波那契数列的递推式$F_i=F_{i-1}+F_{i-2}$，可以得到差分方程$F_i-F_{i-1}-F_{i-2}=0$，得到其特征方程，$x^2-x-1=0$，由此得到两个解
λ 1 = 1 + 5 2 λ 2 = 1 − 5 2

$$\begin{matrix} \lambda_1=\frac{1+\sqrt{5} }{2} \\ \lambda_2=\frac{1-\sqrt{5} }{2} \end{matrix}$$ λ1​=21+5 ​​λ2​=21−5 ​​​
有两个不同的实根，所以有通解$F_i=C_1{\lambda }_1^n+C_2{\lambda }_2^n$，将初值条件$F_1=1,F_0=0$带入，就可以得到
$$F_i=\frac{{\lambda }_1^i-{\lambda }_2^i}{\sqrt{5}}$$
这样我们就只需求两个根的$n$次方即可，时间复杂度就可以降到和快速幂一样的情况$O(logn)$

int  fib(int n) {
    double sq5 = sqrt(5);
    double fi1 = (1 + sq5) / 2;
    double fi2 = (1 - sq5) / 2;
    return (pow(fi1, n) - pow(fi2, n)) / sq5;
}
1
2
3
4
5
6

4.矩阵幂

矩阵幂公式
[ F i + 1 F i F i F i − 1 ] = [ 1 1 1 0 ] i

$$\begin{bmatrix} F_{i+1} &F_{i} \\ F_{i}&F_{i-1} \end{bmatrix}$$ = $$\begin{bmatrix} 1 &1 \\ 1 &0 \end{bmatrix}$$ ^i [Fi+1​Fi​​Fi​Fi−1​​]=[11​10​]i
证明：
$base:$
$$\left[\begin{array}{cc}{F}_2& F_1\\ F_1& F_0\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$
$step:$
$$\left[\begin{array}{cc}{F}_{i+1}& F_i\\ F_i& F_{i-1}\end{array}\right]=\left[\begin{array}{cc}{F}_i& F_{i-1}\\ F_{i-1}& F_{i-2}\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$
$$\left[\begin{array}{cc}{F}_{i+1}& F_i\\ F_i& F_{i-1}\end{array}\right]=\left[\begin{array}{cc}{F}_{i-1}& F_{i-2}\\ F_{i-2}& F_{i-3}\end{array}\right]{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^2$$
以此类推，继续把矩阵拆开，最终右边就只剩初始矩阵的$i$次方
$$\left[\begin{array}{cc}{F}_{i+1}& F_i\\ F_i& F_{i-1}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^i$$
这样也可以将斐波那契的求解转换成求幂次的形式，也和快速幂的时间复杂度相同$O(logn)$

int** multiply(int** a, int** b) {
	//两矩阵相乘，因为求斐波那契数列只需要2*2的矩阵，所以就直接用朴素算法了算了
    int** c = new int* [2];
    for (int i = 0; i < 2; ++i)c[i] = new int[2] {0, 0};
    c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return c;
}
int** matrix_pow(int** mat, int n) {//矩阵快速幂
    int** res = new int* [2];
    for (int i = 0; i < 2; ++i)res[i] = new int[2] {0, 0};
    res[0][0] = 1, res[1][1] = 1;
    while (n > 0) {
        if (n & 1) res=multiply(res, mat);
        mat=multiply(mat, mat);
        n >>= 1;
    }
    return res;    
}
int fib(int n) {
    int** mat = new int* [2];
    for (int i = 0; i < 2; ++i) mat[i] = new int[2] {1, 1};
    mat[1][1] = 0;
    mat = matrix_pow(mat, n+1);
    return mat[1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

学完一定要及时练习一下这些方法:斐波那契数列练习

矩阵乘法

两个矩阵相乘如果用朴素算法(就是按乘法规则一个一个元素的乘起来)的话时间复杂度是$O(n^3)$，效率不是很令人满意，该如何优化呢？本文章是介绍分治，所以优化一定是用分治法来优化，分治和矩阵联系起来，可以想到什么？一定是矩阵分块，我们可以将$n\times n$的矩阵分成由$n/2\times n/2$块矩阵`组成的$2\times 2$矩阵
[ c 11 c 12 … c 1 n c 21 c 22 … c 2 n ⋮ ⋮ ⋮ c n 1 c n 2 … c n n ] = [ a 11 a 12 … a 1 n a 21 a 22 … a 2 n ⋮ ⋮ ⋮ a n 1 a n 2 … a n n ] ⋅ [ b 11 b 12 … b 1 n b 21 b 22 … b 2 n ⋮ ⋮ ⋮ b n 1 b n 2 … b n n ]

$$\begin{bmatrix} c_{11} & c_{12} &\dots &c_{1n}\\ c_{21} & c_{22} & \dots&c_{2n}\\ \vdots & \vdots & &\vdots \\ c_{n1}&c_{n2}&\dots&c_{nn} \end{bmatrix}$$ = $$\begin{bmatrix} a_{11} & a_{12} &\dots &a_{1n}\\ a_{21} & a_{22} & \dots&a_{2n}\\ \vdots & \vdots & &\vdots \\ a_{n1}&a_{n2}&\dots&a_{nn} \end{bmatrix}$$ \cdot $$\begin{bmatrix} b_{11} & b_{12} &\dots &b_{1n}\\ b_{21} & b_{22} & \dots&b_{2n}\\ \vdots & \vdots & &\vdots \\ b_{n1}&b_{n2}&\dots&b_{nn} \end{bmatrix}$$ ​c11​c21​⋮cn1​​c12​c22​⋮cn2​​………​c1n​c2n​⋮cnn​​ ​= ​a11​a21​⋮an1​​a12​a22​⋮an2​​………​a1n​a2n​⋮ann​​ ​⋅ ​b11​b21​⋮bn1​​b12​b22​⋮bn2​​………​b1n​b2n​⋮bnn​​ ​
$$\downarrow$$
$$\left[\begin{array}{cc}r& s\\ t& u\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\cdot \left[\begin{array}{cc}e& f\\ g& h\end{array}\right]$$
其中
$$\{\begin{array}{c}r=ae+bg\\ s=af+bh\\ t=ce+dg\\ u=cf+dh\end{array}$$
但是这样子真的优化了矩阵乘法嘛？我们可以分析一下这个算法的时间复杂度，因为有$8$对矩阵相乘，所以递归时间消耗的系数是$8$，每层递归将矩阵划分为$n/2$的块矩阵，所以递归的时间消耗是$8T(n/2)$，加上将这些矩阵相加的时间消耗，可以得到
$$T(n)=8T(n/2)+\Theta (n^2)$$
根据主定理，$\Theta (n^2)=O(n^{lo{g}_2^8})$，情况一，所以时间复杂度$T(n)=\Theta (n^3)$，啊？优化了个寂寞。虽然没有优化，但是这个递归式给了我们优化的思路，我们可以想办法降低递归的时间消耗，就是减少计算矩阵乘法的次数或是改变分块的方式，改变分块的方式显然是行不通的，因为你将一个块矩阵分的小一些，其他块矩阵一定会变大，相当于没怎么变，那就只有减少计算矩阵乘法的次数了。

下面给出的算法非常神奇，一般人真的想不到

Strassen

算法主要想法就是减少矩阵乘法，为此给出了七个式子
P 1 = a ( f − h ) P 2 = ( c + b ) h P 3 = ( c + d ) e P 4 = d ( g − 3 ) P 5 = ( a + d ) ( e + h ) P 6 = ( b − d ) ( g + h ) P 7 = ( a − c ) ( e + f )

$$\begin{align*} P_1&=a(f-h)\\ P_2&=(c+b)h\\ P_3&=(c+d)e\\ P_4&=d(g-3)\\ P_5&=(a+d)(e+h)\\ P_6&=(b-d)(g+h)\\ P_7&=(a-c)(e+f) \end{align*}$$ P1​P2​P3​P4​P5​P6​P7​​=a(f−h)=(c+b)h=(c+d)e=d(g−3)=(a+d)(e+h)=(b−d)(g+h)=(a−c)(e+f)​
通过这七个式子我就可以表示$r,s,t,u$
$$\begin{array}{rl}r& =P_5+P_4-P_2+P_6\\ s& =P_1+P_2\\ t& =P_3+P_4\\ u& =P_5+P_1-P_3-P_7\end{array}$$
这里我就不证明了，如果你有兴趣可以推导试试看，通过这样的构造，每层递归就只需要计算$7$个矩阵乘法，优化后$T(n)=7T(n/2)+\Theta (n^2)$，在根据主定理就可以得到，$T(n)=\Theta (n^{lg7})=\Theta (n^{2.87})$。

分治练习

合并 K 个升序链表
跳石头
Secret Cow Code S