[关闭]
@anboqing 2014-12-09T09:21:21.000000Z 字数 2527 阅读 1462

Title:算法设计与分析学习笔记(一):分治法
Date: 2014-12-08 15:55
Category: 算法学习
分治法
Slug: algorithm_devide_method
Author: Boqing Ann
Summary: 分治法的基本思想 ,适用条件,基本步骤

分治法


1.分治法的基本思想


分治法的设计思想是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之

分治法将一个大规模问题分解为若干子问题(子问题是原问题的小模式),将子问题的解合并后就可以得到原问题的解,具体可以使用递归计数来完成。分治有两个特点:

1.子问题相互独立且与原问题形式相同
2.反复分治,使划分得到的子问题小到不能再分时,直接对其求解

2.分治法的适用条件


分治法所能解决的问题一般具有以下特征:

  1. 该问题的规模缩小到一定程度就可以容易的解决。
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构的性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解(关键性质)
  4. 该问题所分解出的各个子问题最好是相互独立的,即子问题之间不包含公共的子问题。

上述第一条特征是绝大多数问题都能满足的,因为计算复杂性一般随着规模的减小而降低。
第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用。
第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征。
如果具备了第一条特征和第二条特征,而子问题的解不可以合并,则可以考虑贪心算法或动态规划
第四条特征涉及分治法的效率,如果各子问题不是独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。


3.分治法的基本步骤


分治法在每一层递归上都有如下三个步骤:

1.分解。 将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2.求解。 若子问题规模较小而容易求解则直接求解,否则递归的解决各个子问题。
3.合并。 将各个子问题的解合并为原问题的解。

人们从大量的实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使得子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。

分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,有些问题的合并方法比较复杂,究竟应该怎样合并,没有统一的模式。

分治法的一般算法框架如下:

  1. divide_and_conquer(problem)
  2. {
  3. if(|problem| < n) adhoc(problem); /*解决小规模的问题*/
  4. divide Problem into smaller subinstances P1,P2,....Pk;/*分解问题*/
  5. for(i = 1; i<= k(子问题个数); ++i){
  6. result[i] = divide_and_conquer(P[i]); /*递归的解各个子问题*/
  7. }
  8. return merge(result[1]...result[k]); /*将各个子问题的解合并为原问题的解*/
  9. }

采用分治法思想设计的算法进行分析时,可用如下递归方程描述算法的运行时间T(n)

T(n)={θ(1),kT(nm)+D(n)+C(n),if n less than if n is great than

在该递归方程中,如果问题的规模足够小,可以直接求解,则T(n) = O(1)。如果问题规模不够小,还需分解为k个规模大小为nm的子问题,而且分析问题与合并问题的时间分别为 D(n) , C(n) ,则T(n)=kT(nm)+D(n)+C(n)
对于该方程,不妨设 n 为 m 的幂 ,记D(n) = C1(n)+C2(n) , 则该递归方程的解为

T(n)=nlogmn+i=0logmn1kiD(n/mi)


4. 分治法的典型实例

4.1 折半查找(二分搜索)

问题描述:给定已按照升序排列好的n个元素 a[0:n-1],现在要在这n个元素中找出一特定元素。

问题分析:采用分治法的思想,充分利用元素之间已经存在的次序关系,将序列划分为两个个数相同的左右两个部分,取最中间的元素和x进行比较,如果等于中间的元素就找到,如果不等于,就递归的在左边(x<中间值)或者右边(x>中间值)二分查找。

注意事项:对于二分查找,一般需要建立两个不变性:

1.当前待查找序列,肯定包含目标元素
2.每次待查找序列的规模都会变小。

1用来防止,把目标元素错过,2可以保证程序最终会终止。每次循环的分支内,保证这样的两个不变性可以满足,那么这样的二分查找程序一般不会含有逻辑错误。

  1. template<class T>
  2. int binary_search(T arr[],T key){
  3. int low = 0;
  4. int high = arr.size()-1;
  5. while(low<=high){
  6. int mid = low + (high-low)/2; // 注意mid =begin+(end-begin)/2,用mid=(begin+end)/2是有溢出危险的
  7. if(arr[mid]<key){
  8. low = mid+1;
  9. }else if(arr[mid]>key){
  10. high = mid-1;
  11. }else{
  12. return arr[mid];
  13. }
  14. }
  15. return -1;
  16. }

Knuth在其The Art of Computer Programming Volume 3:Sorting and Searching的6.2.1节的历史部分中指出,虽然第一篇二分搜索论文在1946年就发表了,但是地一个没有错误的二分搜索程序却直到1962年才出现。

几个错误的例子

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注