许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵守分治法(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演算法的数值稳定性较差。

其他案例

深入阅读


  1. “Exponential time is bad; polynomial time is good.”-- Erik Demaine

Comments