算法设计与分析DesignandAnalysisofComputerAlgorithm.ppt

西南科技大学计算机学院软件教研室 第二章 分治与递归 1、基本要求 要求掌握递归与分治策略的基本思想，程序模式和算法分析方法。 第二章 分治与递归 2、教学内容 一般方法 斯特拉森矩阵乘法 二分检索 快速排序 2.1 分治法的一般方法 分治策略的抽象化控制 分治策略思想的形式化描述： 在很多考虑使用分治法求解的问题中，往往把输入分成与原问题类型相同的两个子问题，即，取k=2。为了能清晰地反映出使用分治策略设计实际算法的基本步骤，下面用一个称之为抽象化控制的过程对算法的控制流向作出非形式的描述。 此过程中的基本运算由一些没定义其具体含义的其它过程来表示。在过程中还使用了一个全程量数组A（1：n），用它来存放（或指示）这n个输入。这个过程DANDC是函数，它最初由DANDC（l，n）所调用。DANDC（p，q）解算输入为A（p：q）情况下的问题。 分治策略的抽象化控制 Procedure DANDC(p,q) global n,A(1:n);integer m,p,q; //1≤p≤q≤n// if SMALL(p,q) then return(G(p,q)) else m?DIVIDE(p,q) //p≤m≤q// return(COMBINE(DANDC(p,m),DANDC(m+1,q))) endif End DANDC 虽然以分治法为基础，将要解算的问题分成与原问题类型相同的子问题来求解的算法用递归过程描述是很自然的，但为了提高效率，往往需要将这一递归形式转换成迭代形式。 分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。它的—般的算法设计模式如下： 其中，|P| 表示问题P的规模。n0为—阈值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接用算法adhoc(P)求解，算法merge(y1，y2，…，yk)是该分治法中的合并子算法，用于将P的子问题P1，…，Pk的解y1，…，yk 合并为P的解。 根据分治法的分割原则，应把原问题分为多少个子问题才比较适宜?每个子问题是否规模相同或怎样才为适当?这些问题很难给予肯定的回答。 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k＝2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 从分治法的一般设计模式可以看出，用它设计出的算法一般是递归算法。因此，分治法的计算效率通常可以用递归方程来进行分析。 一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。为方便起见，设分解阈值n0＝1，且adhoc解规模为1的问题耗费1个单位时间。另外，再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法divide-and-conquer(P)解规模为|P|＝n的问题所需的计算时间，则有： 二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个子结点，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。 二叉树的性质 性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k0）。 可以用数学归纳法证明。 性质2 深度（高度）为k的二叉树最大结点数为2k-1（k0）。 证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。即为： 20+21+…+2k-1=2k-1 二叉树的性质 性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 证明：设二叉树度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有