分治法

许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵守分治法（Divide and Conquer）的思想：将原问题分解成几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

三个步骤

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

1. 分解（Divide） 原问题为若干子问题，这些子问题是原问题的规模较小的实例。
2. 解决（Conquer） 这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
3. 合并（Combine） 这些子问题的解成原问题的解。

典型案例

求解x的n次幂

朴素解法

朴素解法需要 \(\Theta(n)\) 的时间复杂度，即直接计算 \(\overbrace{x\cdot{}x\cdot{}\cdot{}\ldots{}\cdot{}x}^{n}\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * power_naive	-	a naive way to calculate the power of a number.
 * @param x	the base number.
 * @param n	the power
 * 
 * @return the power of the number.
 */

extern int power_naive(int x, int n)
{
    int power = 1;
    int i;
    for (i = 0; i < n; i++)
        power = power * x;
    return power;
}

分治法

分治法的解法则可以达到 \(\Theta(\lg{n})\) 的时间复杂度。

\[ x^{n} = \begin{cases} x^{n/2} \cdot x^{n/2} & \mbox{，如果} n \mbox{为偶数} \\ x^{(n+1)/2} \cdot x^{(n-1)/2} & \mbox{，如果} n \mbox{为奇数} \end{cases}\]

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/** 
 * power_dnc	-	a divide-and-conquer way to calculate the power of number
 *
 * @param x the base number
 * @param n the power
 *
 * @return the power of the number
 */
extern int power_dnc(int x, int n)
{
    if (n == 1) {
        return x;
    }
    if (n % 2 == 0){
        int tmp = power_dnc(x, n/2);
        return tmp * tmp;
    } else {
        return power_dnc(x, (n+1)/2) * power_dnc(x, (n-1)/2);
    }
}

求解Fibonacci数列

斐波那契数列的定义：

\[ F_n = \begin{cases} 0 & \mbox{，如果} n \mbox{为0} \\ 1 & \mbox{，如果} n \mbox{为1} \\ F_{n-1} + F_{n-2} & \mbox{，如果} n\ge{}2 \end{cases}\]

朴素解法

朴素解法（直接递归求解）需要指数级^[1]的时间（准确点讲是 \(\Omega(\phi^{n})\)，其中 \(\phi\) 是黄金分割比 \(\frac{1+\sqrt{5}}{2}\)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * fibonacci_naive	-	the naive way to solve fibonacci series.
 * @param n	the nth num of the series.
 *
 * The naive way to solve fibonacci series.
 * Very slow version.
 *
 */
extern int fibonacci_naive(int n)
{
    if (0 == n)
        return 0;
    else if (1 == n)
        return 1;
    else
        return fibonacci_naive(n-1) + fibonacci_naive(n-2);
}

线性的解法

朴素解法在计算斐波那契数列的时候做了很多不必要的重复计算。使用动态规划、自底向上递归求解的策略可以将Fibonacci数列的计算规模降低到线性级别，即 \(O(n)\) 的时间复杂度。主要的思想基于这点：计算新的值时，用到前两个数的结果。可以用借助一维数组来实现。

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

/**
 * fibonacci_linear	-	a linear way to solve fibonacci series.
 * @param n	the nth num of the series.
 *
 * A bottom-up way to solve fibonacci series.
 * Can solve the problem in Linear time.
 *
 */
extern int fibonacci_linear(int n)
{
    int i;
    int ans[n];

    ans[0] = 0;
    ans[1] = 1;

    for(i=2; i <= n; i++)
        ans[i] = ans[i-1] + ans[i-2];

    if (0 == n)
        return 0;
    if (n == 1)
        return 1;
    return ans[n];
}

分治法求解：平方递归

\[ \begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} \]

即

\[ \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \]

显然对斐波那契数列的求解变成了求矩阵 \(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 的 \(n\) 次幂，用到上面求乘方的算法可以将时间复杂度将为 \(O(lg{n})\) 。

实现

1

TODO

矩阵乘法

定义：若 \(A = (a_{ij})\), \(B = (b_{ij})\) 是 \(n\times{}n\)的方阵，则对\(i, j = 1, 2, \ldots{}n\)，定义乘积 \(C = A \cdot B\)中的元素 \(c_{ij}\) 为： \[C_{ij}=\sum_{k=1}^{n}a_{ik}\cdot{}b_{kj}\]

实现

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

#define MAX 10
/** 
 * matrix2_multiply_naive	-	multiply two matrix
 * @param result	-	the multiplying result
 * @param mat1		-	matirx1, which's size is mxn
 * @param mat2		-	matrix2, which's size is nxp
 * @param m
 * @param n
 * @param p
 *
 */
extern void matrix2_multiply_naive(int result[MAX][MAX], int mat1[MAX][MAX], int mat2[MAX][MAX], int m, int n, int p)
{
    int i, j, k;
    int sum;
    for (i = 0; i < m; i++){
        for (j = 0; j < p; j++){
            sum = 0;
            for (k = 0; k < n; k++){
                sum += mat1[i][k] * mat2[k][j];                
            }
            result[i][j] = sum;
        }
    }
}

分块解法

通常的做法是将矩阵进行分块相乘，如下图所示：

\[ \overbrace{\begin{pmatrix} C_0 & C_1 \\ C_2 & C3 \end{pmatrix}}^{C} = \overbrace{\begin{pmatrix} A_0 & A_1 \\ A_2 & A3 \end{pmatrix}}^{A} \times \overbrace{\begin{pmatrix} B_0 & B_1 \\ B_2 & B3 \end{pmatrix}}^{B} \]

即

\[A_{i,j}, B_{i,j}, C_{i,j} \in F^{2^{n-1} \times 2^{n-1}}\]

于是

\[ C_{1,1} = A_{1,1} B_{1,1} + A_{1,2} B_{2,1} \]

\[ C_{1,2} = A_{1,1} B_{1,2} + A_{1,2} B_{2,2} \]

\[ C_{2,1} = A_{2,1} B_{1,1} + A_{2,2} B_{2,1} \]

\[ C_{2,2} = A_{2,1} B_{1,2} + A_{2,2} B_{2,2} \]

分块相乘总共用了8次乘法，因而需要 \(\Theta(n^{\log_{2} 8})\) 即 \(\Theta(n^3)\) 的时间复杂度。

Strassen算法

引入新矩阵

\[M_{1} := (A_{1,1} + A_{2,2}) (B_{1,1} + B_{2,2})\] \[M_{2} := (A_{2,1} + A_{2,2}) B_{1,1}\] \[M_{3} := A_{1,1} (B_{1,2} - B_{2,2})\] \[M_{4} := A_{2,2} (B_{2,1} - B_{1,1})\] \[M_{5} := (A_{1,1} + A_{1,2}) B_{2,2}\] \[M_{6} := (A_{2,1} - A_{1,1}) (B_{1,1} + B_{1,2})\] \[M_{7} := (A_{1,2} - A_{2,2}) (B_{2,1} + B_{2,2})\]

可得：

\[C_{1,1} = M_{1} + M_{4} - M_{5} + M_{7}\] \[C_{1,2} = M_{3} + M_{5}\] \[C_{2,1} = M_{2} + M_{4}\] \[C_{2,2} = M_{1} - M_{2} + M_{3} + M_{6}\]

在求解\(M_1\)，\(M_2\)，\(M_3\)，\(M_4\)，\(M_5\)，\(M_6\)，\(M_7\)时需要使用7次矩阵乘法，其他都是矩阵加法和减法。因此时间复杂度下降为 \(O(n^{log_2 7}) = O(n^{2.807})\) 。有得必有失，Strassen演算法的数值稳定性较差。

其他案例

• 归并排序
• 快速排序
• 二分查找
• 最大子数组问题

深入阅读

• MIT算法导论：分治法（1）