分治法

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

先把题目贴出来吧。

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)

三个步骤

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

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

 

典型案例

1、求解x的n次幂

(1)  朴素解法

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

分治法

  1. extern int power_naive(int x, int n)
  2. {
  3.     int power = 1;
  4.     int i;
  5.     for (i = 0; i < n; i++)
  6.         power = power * x;
  7.     return power;
  8. }

(2)分治法

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

分治法

 

  1. extern int power_dnc(int x, int n)
  2. {
  3.     if (n == 1) {
  4.         return x;
  5.     }
  6.     if (n % 2 == 0){
  7.         int tmp = power_dnc(x, n/2);
  8.         return tmp * tmp;
  9.     } else {
  10.         return power_dnc(x, (n+1)/2) * power_dnc(x, (n-1)/2);
  11.     }
  12. }

 

2、求解Fibonacci数列

斐波那契数列的定义:

分治法

(1)朴素解法
分治法

  1. extern int fibonacci_naive(int n)
  2. {
  3.     if (0 == n)
  4.         return 0;
  5.     else if (1 == n)
  6.         return 1;
  7.     else
  8.         return fibonacci_naive(n-1) + fibonacci_naive(n-2);
  9. }

(2)线性的解法

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

  1. extern int fibonacci_linear(int n)
  2. {
  3.     int i;
  4.     int ans[n];
  5.     ans[0] = 0;
  6.     ans[1] = 1;
  7.     for(i=2; i <= n; i++)
  8.         ans[i] = ans[i-1] + ans[i-2];
  9.     if (0 == n)
  10.         return 0;
  11.     if (n == 1)
  12.         return 1;
  13.     return ans[n];
  14. }

 

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

分治法

 

3、矩阵乘法

分治法

实现

  1. #define MAX 10
  2. extern void matrix2_multiply_naive(int result[MAX][MAX], int mat1[MAX][MAX], int mat2[MAX][MAX], int m, int n, int p)
  3. {
  4.     int i, j, k;
  5.     int sum;
  6.     for (i = 0; i < m; i++){
  7.         for (j = 0; j < p; j++){
  8.             sum = 0;
  9.             for (k = 0; k < n; k++){
  10.                 sum += mat1[i][k] * mat2[k][j];
  11.             }
  12.             result[i][j] = sum;
  13.         }
  14.     }
  15. }

其他案例

深入阅读

 

原文地址:http://www.hahack.com/wiki/algorithms-divide-and-conquer.html

  • 微信
  • 赶快加我聊天吧
  • weinxin
  • 博客交流群
  • 海纳百川,大家来水
  • weinxin
言曌

发表评论

:?::razz::sad::evil::!::smile::oops::grin::eek::shock::???::cool::lol::mad::twisted::roll::wink::idea::arrow::neutral::cry::mrgreen: