算法设计与分析 课件 第3、4章 分治法；动态规划.pptx

计算机算法设计与分析第三章分治法

学习目标掌握分治法的基本思想掌握分治法的特点和基本框架掌握分治法解决实际问题

3.1分治法基本思想孙子兵法兵势篇曰：凡治众如治寡，分数是也。其大致意思就是管理大规模部队和管理小股部队是一样的，分开治理就是了。这就是分治法在军事上的运用。分治法的基本思想就是将一个较难以解决的规模大的问题，分割成多个相似的规模较小的子问题，先求出小规模子问题的解，然后将各小规模子问题的解组合起来就是规模大的问题的解。其中的一个关键点是分割的子问题一定要相似，这样就可以采取同样的方法来求解，从而将问题简化。

例3.1二分查找问题。在一个升序的含n个元素的数组a[]中查找x，输出x在数组a中的下标位置，若没查到返回-1。分析：可以考虑使用分治思想来解决，具体做法是设计三个变量left，mid和right将整个数组分成3个部分a[left,mid-1],a[mid],a[mid+1,right]。如果a[mid]x，则使用相同的办法在较小范围[left,mid-1]中查找；如果a[mid]=x，则已查找到，返回mid即可；如果a[mid]x，则使用相同的办法在较小范围[mid+1,right]中查找。以上过程都没查找到的话，则数组中不存在x，返回-1。3.1分治法基本思想

例3.2二分归并排序。将含有n个元素的数组a[]按关键字大小升序排列。以数组a[8]={8,4,5,7,1,3,6,2}为例来分析。3.1分治法基本思想

3.2分治法的特点和基本框架当采用分治法时，一般原问题都需要具备以下几个特征：（1）难度递降：即原问题的解决难度，随着数据的规模的缩小而降低，当降低到一定程度时，问题很容易解决。（2）问题可分：原问题可以分解为若干个规模较小的同类型问题，即该问题具有最优子结构性质。这是应用分治法的前提。（3）解可合并：利用所有子问题的解，可合并出原问题的解。这个特征很关键，能否利用分治法完全取决于这个特征。（4）相互独立：各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题。如果子问题之间不独立，则分治法需要重复地解决公共的子问题，造成效率低下的结果。

设P是要求解的问题，|P|为问题P的输入规模，现将分治法求解问题的基本框架描述如下：Divide-and-Conquer(P)：if|P|≤cthenS(P) //当问题规模较小时，很容易求出解endifdividePintoP1,P2,...,Pk//将原问题分割为规模小的子问题fori=1tokdoxi=Divide-and-Conquer(Pi)//递归求解每个子问题endforreturnMerge(x1,x2,...,xk)//将子问题的解合并成原问题的解3.2分治法的特点和基本框架

3.3分治法的时间复杂度分析分治法的实现一般都是采用递归算法。分析分治法的时间复杂度需要使用其递推公式来推导。分治法中通常的递推方程有以下两种类型：第一类是归约后子问题规模比原问题规模呈常数级减少。递推方程为如Hanoi塔问题使用分治法，将n个圆盘的问移动题归约为两个n-1圆盘移动子问题，也就是归约后的子问题规模只比原问题规模少1。递推方程为解得：

第二类是归约后子问题规模比原问题规模呈倍数减少。该算法的时间复杂度可以通过以下递推公式求出：根据1.4.4节介绍的MasterTheorem主定理结论可知：3.3分治法的时间复杂度分析

3.4.1分治法的典型实例——快速排序快速排序是数据结构中经典且高效的一种排序算法，它在实践中应用非常广泛。设待排的数组为A，快速排序的基本思想为：用数组的首元素作为标准将A划分为前、后两部分，前部分元素都比首元素小，后部分元素都比首元素大，这两部分就构成两个新的子问题。算法接着分别对这两部分递归地进行排序，各子问题排序完成后自然整个数组也就排序完成。算法的关键在于怎样划分数组A而将其归约成两个相同结构的子问题。

3.4.1分治法的典型实例——快速排序快速排序算法Quicksort(A,p,r) //p和r分别为数组A的首元素和尾元素的下标输入：数组A[p..r],1≤p≤r≤n输出：从A[p]到A[r]按照升序排好序的数组Aifprthenq←Partition(A,p,r) //划分数组，找到首元素A[p]在排好序后的位置qA[p]?A[q] //交换A[p]，A[q]中元素的值Quicksort(A,p,q-1) //对前部分继续递归地用快速排序算法Quicksort(A,q+1,r) //对后部分继续递归地用快速排序算法endif

其算法中的Partition函数是划分的过程函数，它实现的就是以A[p..r]的首元素A[p]作为标准，输出q表示A[p]应该处在