《递归与分治策略第一部分》由会员分享，可在线阅读，更多相关《递归与分治策略第一部分（60页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析第第2章章 递归与分治策略递归与分治策略分治（分治（Divide and Conquer）凡治众如治寡，分数是也。 孙子兵法治理大军团就象治理小部队一样有效，是依靠合理的组织、结构、编制。将一个难以直接解决的大问题难以直接解决的大问题，合理分割分割成一些规模较小规模较小的相同问题的相同问题，以便各个击破，这个策略就叫分而治之（分分而治之（分治法）治法）。第第2章章 递归与分治策略递归与分治策略分治法分治法是最为重要的算法设计方法之一。主要思想是：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。因此分治法可以分为两个重要步骤：（1）自顶向下自
2、顶向下：将问题不断分割成小的问题。（2）自底而上自底而上：将小问题解决来构建大问题的解。分治分治和递归递归经常同时应用在算法设计中。第第2章章 递归与分治策略递归与分治策略将要求解的较大规模的问题较大规模的问题分割为 k 个较小规模的子问题。对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归递归的进行下去，直到问题规模足够小，很容易求出其解为止直到问题规模足够小，很容易求出其解为止。第第2章章 递归与分治策略递归与分治策略将求出的小规模的问题的解合并合并为一个更大规模的问题的解，自底向上自底向上逐步求出原来问题的解。第第2章章 递归与分治策略递归与分治策
3、略【例例】找一组数的最大最小数找一组数的最大最小数。直接求解直接求解：需要 n - 1 次比较来求最小数（n 个数两两比较共需要个数两两比较共需要 n 1 次次），然后另外 n - 2 次比较来求最大数（除去最小值的剩下除去最小值的剩下 n 1 个数两两比较共需要个数两两比较共需要 n 2 次次）。总计为（总计为（ 2n - 3）次）次。分治方法分治方法 （Divide and Conquer）: （1）将数据集 S 均分为 S1 和 S2；（2）求解 S1 和 S2 中的最大和最小值；（3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；（4）采用同
4、样的处理方法递归处理 S1 和 S2。第第2章章 递归与分治策略递归与分治策略min_max(S, min, max) if |S| = 2 then min min(S) max max(S) else split S evenly into S1 and S2 min_max(S1, min1, max1) min_max(S2, min2, max2) min min(min1, min2) max max(max1, max2)治治分分合并合并算法描述（为方便起见，假定算法描述（为方便起见，假定 n 是是 2 的指数倍，的指数倍，n 1）：）：第第2章章 递归与分治策略递归与分治策略复
5、杂度公式复杂度公式 T( n ) = 3n/2 2 的推导过程（要会处理类似的问题）：的推导过程（要会处理类似的问题）：第第2章章 递归与分治策略递归与分治策略第第2章章 递归与分治策略递归与分治策略教学内容和要求教学内容和要求（讲授（讲授 6 学时，学时，2 学时上机实验，共学时上机实验，共 8 学时）学时）（1）递归递归、递归算法的设计递归算法的设计（Ackerman 函数、排列问题、整数划分问题）（重点重点）（2）分治法分治法的基本思想、算法效率分析（掌握掌握）（3）二分搜索技术二分搜索技术（熟练掌握熟练掌握）（4）棋盘覆盖（理解理解）（5）合并排序（理解理解）（6）快速排序快速排序（熟
6、练掌握熟练掌握）第第2章章 递归与分治策略递归与分治策略2.1 递归的概念递归的概念（1）直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。（2）由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导这自然导致递归过程的产生致递归过程的产生。（3）分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生分治与递归像一对孪生兄弟，经常同时
7、应用在算法设计之中，并由此产生许多高效算法许多高效算法。第第2章章 递归与分治策略递归与分治策略递归实例递归实例（1）数据结构本身固有递归特性，特别适于用递归描述数据结构本身固有递归特性，特别适于用递归描述：树（二叉树）树（二叉树）树是由 n（n 0）个结点组成的有限集合。若 n = 0，称为空树；若 n 0，则：（A）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （B）除根结点以外的其它结点可以划分为m（ m 0）个互不相交的有限集合T0，T1，Tm-1，每个集合每个集合Ti（i = 0, 1, , m - 1）又是一棵树）又是一棵树，称为根的子根的子树树，每棵子树
8、的根结点有且仅有一个直接前驱，但可以有 0 个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念树的定义是一个递归的定义，即树的定义中又用到了树的概念。第第2章章 递归与分治策略递归与分治策略树的实例树的实例 1 - 红楼梦红楼梦人物关系表人物关系表树的实例树的实例 2 图像处理类谱系图像处理类谱系第第2章章 递归与分治策略递归与分治策略二叉树二叉树是 n（n 0）个结点的有限集，它或者是空集（n = 0），或者由一个根结点及两棵不相交的左子树和右子树组成两棵不相交的左子树和右子树组成。二叉树的前序遍历二叉树的前序遍历 递归算法递归算法第第2章章 递归与分治策略递
9、归与分治策略（2）一些问题本身没有明显的递归结构，但用递归技术来求解，可使设计出的一些问题本身没有明显的递归结构，但用递归技术来求解，可使设计出的算法简捷易懂算法简捷易懂。【例例 1】阶乘函数阶乘函数阶乘函数可递归地定义为：边界条件（一般是非递归定义的初边界条件（一般是非递归定义的初始值）始值）与递归方程递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略int factorial( int n ) if ( n = 0 ) return 1; return n * fact
10、orial( n 1 );算法代码算法代码第第2章章 递归与分治策略递归与分治策略【例例 2】 Fibonacci 数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为 Fibonacci数列数列。它可以递归地定义为：第第2章章 递归与分治策略递归与分治策略第 n 个 Fibonacci 数可递归地计算如下：int fibonacci( int n ) if (n = 0 和 n = 0，定义如下：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略Ackerman 函数的特点函数的特点：“阶乘函数”和“Fibonacci 数列”都可以找到相应的
11、非递归方式定义，如下：Ackerman 函数却无法找到非递归的定义。函数却无法找到非递归的定义。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略Ackerman 函数函数 A ( n，m ) 的自变量的自变量 m 的每一个值都定义了一个单变量函数：的每一个值都定义了一个单变量函数：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略Ackerman 函数总结如下：函数总结如下：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策
12、略递归与分治策略int Ackerman( int n, int m ) if ( m = 0) if ( n = 1 ) return 1; else return ( n + 2 ); else if( n = 0 ) return 1; else return Ackerman( Ackerman( n - 1, m ), m - 1 );算法代码算法代码西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略定义单变量的 Ackerman 函数 A(n) 为：A( n ) = A( n，n )。定义其拟逆函数(n)为：( n ) = min kA( k )
13、n 。即 ( n ) 是使是使 n A( k )成立的最成立的最小的小的 k 值值。A( 0 ) = 1A( 1 ) = 2A( 2 ) = 4A( 3 ) = 16A( 4 ) = 2 多重幂多重幂（其中 2 的层数为 65536）可知： ( 1 ) = 0 ( 2 ) = 1 ( 3 ) = ( 4 ) = 2 ( 5 ) = = ( 16 ) = 3( n )的增长速度非常缓慢。( n )在复杂度分析中常遇到。对于通常所见到的正整数n，有 ( n ) 4 。但在理论上( n )没有上界，随着 n 的增加，它以难以想象的慢速度趋向正无穷大。西安邮电大学计算机学院西安邮电大学计算机学院第第2
14、章章 递归与分治策略递归与分治策略【例例 4】 排列问题排列问题设计一个递归算法生成 n 个元素 r1, r2, , rn 的全排列。全排列全排列：从 n 个不同元素中任取m（m n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当当 m = n 时所有的排列情况时所有的排列情况叫全排列叫全排列。如 1, 2, 3 三个元素的全排列为：1, 2, 3 1, 3, 22, 1, 3 2, 3, 13, 1, 2 3, 2, 1共 3！= 3 * 2 * 1 = 6 种排列西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略全排
15、列的递归算法设计全排列的递归算法设计从实际例子中观察可知：（1） 1 的全排列为：1（2） 1, 2 的全排列为：1, 2 2, 1（3） 1, 2, 3 的全排列为： 1, 2, 3 1, 3, 2 2, 3 的全排列加上的全排列加上 1 所得所得 2, 1, 3 2, 3, 1 1, 3 的全排列加上的全排列加上 2 所得所得 3, 1, 2 3, 2, 1 1, 2 的全排列加上的全排列加上 3 所得所得 即：3 个元素的全排列问题可转化为求个元素的全排列问题可转化为求 2 个元素的全排列问题个元素的全排列问题。.推广结论：n 个元素的全排列问题可转化为求个元素的全排列问题可转化为求 n
16、 - 1 个元素的全排列问题（递归设计）个元素的全排列问题（递归设计）。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略全排列的递归算法全排列的递归算法设 R = r1, r2, , rn 是要进行排列的 n 个元素，Ri = R - ri 。集合 X 中元素的全排列记为 perm( X )。( ri )perm( X ) 表示在全排列 perm( X ) 的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当 n = 1 时，perm( R ) = ( r )，其中 r 是集合 R 中唯一的元素；当 n 1 时，perm( R ) 由 ( r1
17、)perm(R1)，( r2 )perm(R2)，( rn )perm(Rn)构成。 西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略全排列的递归算法说明示例全排列的递归算法说明示例设 R = 1, 2, 3 ，则 n = 3，根据上述算法，产生的全排列为：1 2, 3 2 3 3 2 （即对集合即对集合 2, 3 继续执行递归算法，下同继续执行递归算法，下同）2 1, 3 1 3 3 1 3 1, 2 1 2 2 1 即 R = 1, 2, 3 产生的全排列为：1, 2, 3 1, 3, 22, 1, 3 2, 3, 13, 1, 2 3, 2, 1西安邮
18、电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略全排列在全排列在 IT 公司的笔试面试中比较热门，百度、迅雷等大公司的校园招聘以及公司的笔试面试中比较热门，百度、迅雷等大公司的校园招聘以及程序员和软件设计师的考试中都考过此题。程序员和软件设计师的考试中都考过此题。如下面的百度、迅雷百度、迅雷校招笔试题中的“全排列”：【题目题目】用用 C+ 写一个函数写一个函数, 如如 Foo( const char *str ), 打印出打印出 str 的全排列的全排列, 如如 abc 的全排列的全排列: abc, acb, bca, dac, cab, cba。【分析分析】根据
19、上述描述的算法，可知全排列的递归实现算法全排列的递归实现算法的规律是“全排列全排列是从第一个数字起每个数分别与它后面的数字交换是从第一个数字起每个数分别与它后面的数字交换”。这样根据上述算法可以写出示例代码如下：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略/ 全排列的递归实现（假定集合中的各个元素互不相同）全排列的递归实现（假定集合中的各个元素互不相同）#include #include void Swap( char *a, char *b ) char t = *a; *a = *b; *b = t; 西安邮电大学计算机学院西安邮电大学计算机学院第第
20、2章章 递归与分治策略递归与分治策略/ k 表示当前选取到第几个数表示当前选取到第几个数, m表示共有多少数表示共有多少数. void AllRange(char *pszStr, int k, int m) if ( k = m ) static int s_i = 1; printf( 第%3d个排列t%sn, s_i+, pszStr); else for (int i = k; i = m; i+) / 第第 i 个数分别与它后面的数字交换就能得到新的排列个数分别与它后面的数字交换就能得到新的排列 Swap( pszStr + k, pszStr + i ); AllRange( ps
21、zStr, k + 1, m ); Swap( pszStr + k, pszStr + i ); 西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略void Foo( char *pszStr ) AllRange( pszStr, 0, strlen( pszStr ) 1 ); int main() printf( 全排列的递归实现n); char szTextStr = 123; printf(%s的全排列如下:n, szTextStr); Foo( szTextStr ); return 0; 西安邮电大学计算机学院西安邮电大学计算机学院第第2章章
22、递归与分治策略递归与分治策略运行结果如下：运行结果如下：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略【例例 5】整数划分问题整数划分问题将正整数 n 表示成一系列正整数之和：n = n1 + n2 + + nk，其中 n1 n2 nk 1，k 1。正整数 n 的这种表示称为正整数正整数 n 的划分的划分。求正整数n的不同划分个数。 例如正整数正整数 6 有如下有如下 11 种不同的划分种不同的划分： 6； 5 + 1； 4 + 2，4 + 1 + 1； 3 + 3，3 + 2 + 1，3 + 1 + 1 + 1； 2 + 2 + 2，2 + 2 + 1
23、+ 1，2 + 1 + 1 + 1 + 1； 1 + 1 + 1 + 1 + 1 + 1西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略再如正整数正整数 4 有如下有如下 5 种不同的划分种不同的划分： 4； 3 + 1； 2 + 2，2 + 1 + 1；1 + 1 + 1 + 1注意 4 = 1 + 3 和 4 = 3 + 1 被认为是同一个划分。也可以采用如下方式表示 4 的 5 个划分： 4 , 3, 1 , 2, 2 , 2, 1, 1 , 1, 1, 1, 1 ;第第2章章 递归与分治策略递归与分治策略将正整数 n 的不同划分个数称为正整数正整数
24、n 的划分数的划分数，记作 p( n )。如上述 p( 6 ) = 11。将正整数 n 表示成一系列正整数之和：n = n1 + n2 + + nk，其中 n1 n2 nk 1，k 1。正整数 n 的这种表示称为正整数正整数 n 的划分的划分。如果如果 max n1, n2, , nk 0 )，只有一种划分即 1 ;（2）当当 m = 1 时时，不论 n 的值为多少，只有一种划分即 n 个 1， 1, 1, 1, ., 1 ;西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略（3） 当当 n = m 时时，根据划分中是否包含 n，可以分为两种情况： （3-1）
25、划分中包含 n 的情况，只有一个即 n ； （3-2）划分中不包含 n 的情况，这时划分中最大的数字也一定比 n 小，即 n 的 所有 ( n 1 ) 划分。（ m = n 1，即包含所有max n1, n2, , nk = n 1 的情况） 因此 q( n, m ) = q( n, n ) = 1 + q( n, n 1 );注意：注意：q( n, m ) 中 m 的定义为：如果如果 max n1, n2, , nk = m，则称划分，则称划分 n = n1 + n2 + + nk 属于属于 n 的一个的一个 m 划划分，记为分，记为 q( n, m )。当 n = m 时， max n1,
26、 n2, , nk = m = n，也即 n1, n2, , nk 中的最大值小于或者等于 n 都是可以的，所以上述（3-2）是成立的。第第2章章 递归与分治策略递归与分治策略（4）当当 n m 时时，根据划分中是否包含最大值最大值 m，可以分为两种情况： （5-1）划分中包含 m 的情况，即 m, n1, n2, ., ni , 其中其中 n1, n2, ., ni 的和的和 为为 n - m，可能再次出现 m（ max n1, n2, , ni = m 是可以成立的是可以成立的）， 因此是（ n - m）的 m 划分，因此这种划分个数为 q( n - m, m ); （5-2）划分中不包含
27、 m 的情况，则划分中所有值都比 m 小（ m），即 n 的 ( m 1 ) 划分（一定满足max n1, n2, , nk = m - 1），个数为 q( n, m 1 ); 因此 q( n, m ) = q( n - m, m ) + q( n, m 1 );西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略综上可知：上面的结论具有递归定义特征具有递归定义特征，其中（其中（1）和（）和（2）属于回归条件）属于回归条件，（3）和（4）属于特殊情况，将会转换为情况（5）。而情况（情况（5）为通用情况，属于递推）为通用情况，属于递推的方法，其本质主要是通过减小的
28、方法，其本质主要是通过减小 m 以达到回归条件，从而解决问题以达到回归条件，从而解决问题。递推表达式如下：正整数正整数 n 的划分数的划分数 p( n ) = q( n, n )。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略因此可以给出求出 q( n, m ) 的递归函数代码如下：unsigned long GetIntegerPartitionCount( int n, int m ) if ( n = 1 | m = 1 ) return 1; else if ( n 1 时，需要利用塔座需要利用塔座 c 作为辅助塔座作为辅助塔座。此时要设法将 n
29、- 1 个较小的圆盘依照规则从 a 移至 c 上，然后将剩下的最大塔座从 a 移至 b 上。最后设法将 n - 1 个较小的圆盘依照规则从 c 移至 b 上。由此可见，n 个圆盘的移动问题可分解为两次个圆盘的移动问题可分解为两次 n - 1 个圆盘的移动问题，这又可以个圆盘的移动问题，这又可以递归地用上述方法来做递归地用上述方法来做。由此可以设计出算法如下：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略void hanoi( int n, int a, int b, int c ) / 将塔座将塔座 a 上的上的 n 个圆盘依规则移至塔座个圆盘依规则移至塔
30、座 b 上，上， / 以塔座以塔座 c 作为辅助塔座作为辅助塔座 if ( n 0 ) hanoi( n - 1, a, c, b ); move( a, b ); / 将塔座将塔座 a 上编号为上编号为 n 的圆盘移至塔座的圆盘移至塔座 b 上上 hanoi( n - 1, c, b, a ); 西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略递归小结递归小结优点优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多
31、。解决方法解决方法：在递归算法中消除递归调用，使其转化为非递归算法。（1）采用一个用户定义的栈用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推递推来实现递归函数。这种方法在时空复杂度上均有较大改善，但其适用范围有限。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略2.2 分治法的基本思想分治法的基本思想分治法的基本思想分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相
32、同。递归地解这些子问题递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法所能解决的问题一般具有以下几个特征分治法所能解决的问题一般具有以下几个特征：（1）该问题规模缩小到一定的程度就可以容易地解决该问题规模缩小到一定的程度就可以容易地解决；因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有该问题可以分解为若干个规模较小的相同问题，即该问题具有“最优子结最优子结构性质构性质”。这条特征是应用分治法的前提，它也
33、是大多数问题可以满足的，此特征反映了递归思想的应用。（3）利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划贪心算法或动态规划。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题子问题。这条特征涉及到分治法的效率，如果
34、各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动动态规划态规划较好。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略分治法的一般的算法设计模式如下：分治法的一般的算法设计模式如下：divide-and-conquer(P) if ( | P | = n0) adhoc(P); / 边界条件边界条件 divide P into smaller subinstances P1,P2,.,Pk；/ 分解问题分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); / 递
35、归的解各子问题递归的解各子问题 return merge(y1,.,yk); / 将各子问题的解合并为原问题的解将各子问题的解合并为原问题的解 西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略上述模式中 | P | 表示问题 P 的规模。N0 为一阀值，表示当问题 P 的规模不超过n0 时，问题已容易解出，不必再继续分解。adhoc( P ) 是该分治法中的基本子是该分治法中的基本子算法，用于直接解小规模的问题算法，用于直接解小规模的问题 P。当 P 的规模不超过 n0 时，直接用算法 adhoc( P ) 求解。算法 merge( y1, y2, ., y
36、k )是该分治法中的合并子算法，用于将P 的子问题 P1, P2, ., Pk 的解 y1, y2, ., yk 合并为 P 的解。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的 k 个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种 平衡平衡( balancing )子问题子问题 的思想，它几乎总是比子问题规模不等的做法要好。西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略分治法的复杂性分析分治法的复杂性分
37、析一个分治法将规模为 n 的问题分成 k 个规模为 nm 的子问题去解。设分解阀值n0 = 1，且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题分解为 k个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f( n )个单位时间。用用 T( n ) 表示该分治法解规模为表示该分治法解规模为 | P | = n 的问题所需的计算时间的问题所需的计算时间，则有：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略通常可以用展开递归式的方法来解这类递归方程，反复代入求解得（迭代法求迭代法求方程解方程解）：西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院第第2章章 递归与分治策略递归与分治策略在分析分治法的计算效率时，通常得到的是如下的递归不等式：在讨论最坏情况最坏情况下的计算时间复杂度时，用等号( = )还是用小于等于号( = )是没有本质区别的。Thank you !&Questions?
