分治法

avatar 2017年10月10日22:07:35 4 2789 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)

三个步骤


分治模式在每层递归时都有三个步骤:
  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
  • 个人淘宝
  • 店铺名:言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar
  • 版权声明: 发表于 2017年10月10日 22:07:35
  • 转载注明: 分治法

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0