分治法

言曌 2017年10月10日22:07:35 4 3058 views

博主分享免费Java教学视频，B站账号：Java刘哥，长期提供技术问题解决、项目定制：本站商品点此

最近开始做算法题，在做到“求最大子数组”的时候，看到提示中说到了要用分治法，于是学习一下，这个学期的算法课里其实也讲了。

先把题目贴出来吧。

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.



For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

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

下面这个是麻省理工学院的视频，网易云课堂的。下面的内容基本都是来自该视频。

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

三个步骤

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

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

典型案例

1、求解x的n次幂

(1) 朴素解法

朴素解法需要 $Θ (n)$ 的时间复杂度，即直接计算

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

（2）分治法

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

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);
}
}

2、求解Fibonacci数列

斐波那契数列的定义：

（1）朴素解法

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);
}

（2）线性的解法

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

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];
}

(3) 分治法求解：平方递归

3、矩阵乘法

实现

#define MAX 10
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;
}
}
}