第2章 递归与分治策略知识点

算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。

2、多项式10()m m A n a n a n a =+++的上界为O(n m )。

3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。

4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。

5、计算下面算法的时间复杂度记为： O(n 3) 。

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]= c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。

7、算法设计的基本要求：正确性 和 可读性。

8、计算下面算法的时间复杂度记为： O(n 2) 。

for （i ＝1；i<n; i++）{ y=y+1;for （j ＝0；j <=2n ；j++ ）x ＋＋；}9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。

10、算法是指解决问题的 方法或过程 。

二、简答题：1、按照时间复杂度从低到高排列：O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3),O( n!)应该排在哪一位？答：O( 2)，O( logn)，O( n 2/3)，O( 20n)，O( 4n 2)，O( 3n )，O( n!)2、什么是算法？算法的特征有哪些？答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

通俗讲，算法：就是解决问题的方法或过程。

2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j++) (1)for(i=1;i<=n;i++) (2) {c[i][j]=0; (3)for(k=1;k<=n;k++) (4)c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

递归和分治法摘要：1.递归和分治法的定义2.递归和分治法的区别3.递归和分治法的应用实例4.递归和分治法的优缺点正文：递归和分治法是计算机科学中常用的两种算法设计技巧。

它们在解决问题时都采用了将问题分解成更小子问题的思路，但在具体实现上却有所不同。

下面，我们来详细了解一下递归和分治法。

1.递归和分治法的定义递归法是指在算法中调用自身来解决问题的方法。

递归函数在执行过程中，会将原问题分解成规模更小的相似子问题，然后通过调用自身的方式，解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法是指将一个大问题分解成若干个规模较小的相似子问题，然后分别解决这些子问题，最后将子问题的解合并，得到原问题的解。

分治法在解决问题时，通常需要设计一个主函数（master function）和一个子函数（subfunction）。

主函数负责将问题分解，子函数负责解决子问题。

2.递归和分治法的区别递归法和分治法在解决问题时都采用了将问题分解成更小子问题的思路，但它们在实现上存在以下区别：（1）函数调用方式不同：递归法是通过调用自身来解决问题，而分治法是通过调用不同的子函数来解决问题。

（2）递归法必须有递归出口，即必须有一个基线条件，而分治法不一定需要。

3.递归和分治法的应用实例递归法应用广泛，例如斐波那契数列、汉诺塔问题、八皇后问题等。

分治法也有很多实际应用，例如快速排序、归并排序、大整数乘法等。

4.递归和分治法的优缺点递归法的优点是代码简单易懂，但缺点是容易产生大量的重复计算，导致时间复杂度较高。

分治法的优点是时间复杂度较低，但缺点是代码实现相对复杂，需要设计主函数和子函数。

总之，递归和分治法都是解决问题的有效方法，具体应用需要根据问题的特点来选择。

递归算法知识点总结一、基本概念递归算法的基本概念是基于递归函数的思想。

递归函数是一个调用自身的函数。

递归算法通常可以分为两种类型：简单递归和复杂递归。

简单递归是指在递归函数中直接调用自身，而复杂递归则是指在递归函数中可能会有多个递归调用。

递归算法通常用于解决可以分解为若干子问题的问题，这种方法通常可以更加简洁地解决问题，但同时也可能会带来一些计算复杂度的问题。

递归算法的设计通常包括以下几个步骤：1. 确定基本情况：在设计递归函数时，通常需要确定一个或多个基本情况。

基本情况通常是指在递归函数中不需要再次调用自身的情况。

2. 确定递归情况：在设计递归函数时，需要确定一个或多个递归情况。

递归情况通常是指在递归函数中需要调用自身的情况。

3. 确定递归方式：当确定了递归函数的基本情况和递归情况之后，就需要确定递归函数的调用方式。

通常有两种方式：直接递归和间接递归。

4. 编写递归函数：根据确定的基本情况、递归情况和递归方式，编写递归函数。

5. 测试递归函数：编写递归函数后，需要对递归函数进行测试，确保递归函数能够正确地解决问题。

二、递归算法的原理递归算法的原理是基于递归函数的调用。

当一个递归函数被调用时，它会将自身的执行环境保存到栈中，并且在栈中分配一些空间。

在递归函数中，如果有一些局部变量，这些变量会在栈中分配空间。

随着递归函数的深入调用，栈中的空间也会不断增加。

在递归函数的执行过程中，通常需要考虑递归栈的压栈和出栈操作。

在递归函数被调用时，会执行一些初始化操作，并将递归参数保存到栈中。

在递归函数中，如果遇到递归情况，会再次调用自身，并且将自身的执行环境保存到栈中。

在递归函数的执行过程中，如果遇到基本情况，就会结束当前递归调用，并且从栈中释放空间。

递归算法的原理是基于递归函数的深度调用的。

当递归函数被调用时，会执行一些初始化过程，并将递归参数保存到栈中。

当递归函数执行完毕后，会从栈中释放空间。

在递归函数的执行过程中，栈中的空间会不断增加和释放。

分治法和动态规划⼀.分治法 1.分治法的设计思路是，将⼀个难以直接解决的⼤问题，分割成⼀些规模⽐较⼩的相同的⼩问题，以便各个击破，分⽽治之。

2.分治法所能解决的问题的⼀般有以下的特征： （1）该问题的规模缩⼩到⼀定的程度就可以容易解决（绝⼤多数的问题都满⾜） （2）该问题是可以分解为若⼲个规模较⼩的相同的问题，即改问题具有最优⼦结构性质（前提，也是绝⼤多数的问题都满⾜的） （3）利⽤该问题分解出的字问题的解可以合并该问题（关键） （4）该问题分解出来的各个⼦问题是相互独⽴的（分治法的效率） （如果具备⼀⼆条，但不具备第三条，可以考虑使⽤贪⼼算法或动态规划） 3.分治法的基本步骤： （1）分解：将原问题分解为若⼲个规模较⼩、互相独⽴、与原问题形式相同的⼦问题。

（2）解决：若⼲问题规模较⼩⽽容易被解决则直接解，否则递归地解各个⼦问题 （3）合并：将各个⼦⽂题的解合并成原问题的解 (记住不是所有的分治法逗逼简单的蛮⼒法简单) 4.分治法的时间性能的与直接计算最⼩问题的时间、合并⼦⽂题解的时间以及⼦问题的个数有关： c n=1T(n)= aT(n/b)+cn^k n>1（其中a,b.c.k都是常数。

这个递推描述了⼤⼩为n的原问题分解为若⼲⼤⼩为n/b的⼦问题，其中a个⼦问题需求求解，⽽cn^k是合并各个⼦问题的解所需要的⼯作量） 当⼦问题的规模之和⼩于原问题的规模时，算法的时间复杂度可达到0(n).⼆.动态规划1.简单的说就是在解决多阶决策的过程中动态的选择最优的过程的⽅法就是动态规划。

2.与分治法的区别：⼀般来说⼦问题不是互相独⽴的，可以理解为是分治法的⼀种改进，不需要求解已有解的⼦问题（已有解的⼦问题⽤表来记录）3.适⽤条件：（1）最优化原理（最优⼦结构）：⼀个最优策略的⼦策略总是最优的---->局部最优，整体最优（2）⽆后效性：每个状态都是过去历史的⼀个完整的总结（3）⼦问题的重叠性：⾼效性（最优⼦结构：当问题的最优解包含其⼦问题的最优解时，称该问题具有最有⼦结构；重叠⼦问题是⼀个递归解决⽅案⾥包含的⼦问题虽然很多，但不同⼦问题很少。

算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。

3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。

(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。

4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。