计算机算法设计与分析..求解递归方程的方法

算法设计与分析知到章节测试答案智慧树2023年最新天津大学第一章测试1.下列关于效率的说法正确的是（）。

参考答案:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;效率主要指处理机时间和存储器容量两个方面;效率是一个性能要求，其目标应该在需求分析时给出2.算法的时间复杂度取决于（）。

参考答案:问题的规模;待处理数据的初态3.计算机算法指的是（）。

参考答案:解决问题的有限运算序列4.归并排序法的时间复杂度和空间复杂度分别是（）。

参考答案:O(nlog2n);O(n)5.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

（）参考答案:错6.用渐进表示法分析算法复杂度的增长趋势。

（）参考答案:对7.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

（）参考答案:对8.某算法所需时间由以下方程表示，求出该算法时间复杂度（）。

参考答案:O(nlog2n)9.下列代码的时间复杂度是（）。

参考答案:O(log2N)10.下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（）。

参考答案:3n/2-3/2第二章测试1.可用Master方法求解的递归方程的形式为（）。

参考答案:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.2.参考答案:对3.假定，, 递归方程的解是. ( )参考答案:对4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。

针对该问题的任何算法需要的时间复杂度的下限必为。

( )参考答案:错5.使用Master方法求解递归方程的解为（）.参考答案:6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。

一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。

若给定集合S，则可在时间内找到这条分界线L。

递归方程求解方法综述递归方程是数学中常见的一种表示方式，它描述了一个数列或函数之间的递推关系。

递归方程求解方法是指寻找递归方程的解析解或近似解的过程。

在许多应用领域，递归方程都是非常重要的，例如在计算机科学、自然科学及经济学等各个领域。

本文将从递归方程的求解方法综述入手，介绍常见的求解方法，包括代入法、特征根法、母函数法等，并举例说明其应用。

一、代入法代入法是求解递归方程的常见方法之一、它的基本思想是通过猜测法求得递归方程的解的形式，然后通过代入递归方程验证该猜测解是否成立。

如果成立，我们就可以得到递归方程的解析解；如果不成立，我们需要修改猜测解的形式，重复上述过程直到找到正确的解。

例如，考虑递推关系式$f(n) = 2f(n-1) + 3$，其中$f(0)=1$。

我们首先猜测$f(n) = a\cdot 2^n + b$，代入递推关系式可得：$a\cdot 2^n + b = 2(a\cdot 2^{n-1} + b) + 3$。

整理得$a\cdot 2^n + b = 2a\cdot 2^{n-1} + 2b + 3$。

化简可得$a\cdot 2^{n-1} = 2b + 3$。

由此可知，$b = \frac{a\cdot 2^{n-1} - 3}{2}$。

将$b$的值代入原方程得到$a\cdot 2^n + \frac{a\cdot 2^{n-1} - 3}{2} = 2(a\cdot2^{n-1} + \frac{a\cdot 2^{n-1} - 3}{2}) + 3$。

进一步化简可得$a = 6$。

因此，递归方程的解析解为$f(n) =6\cdot 2^n + \frac{3}{2}(2^n - 1)$。

二、特征根法特征根法是求解线性递归方程的常用方法。

这种方法基于线性递归方程的特征方程和特征根的性质，通过求解特征方程的根来得到递归方程的解析解。

考虑递归关系式$f(n) = af(n-1) + b$，其中$f(0)=c$。

求解递归式的方法递归式是计算机科学中常见的数学表示方法，用于描述一个函数或算法在运行过程中自我调用的特性。

在求解递归式时，我们希望找到一个封闭的表达式，从而得到问题的解析解。

本文将介绍几种常见的求解递归式的方法。

一、递归展开法递归展开法是求解递归式的一种常用方法。

它的基本思想是将递归式进行展开，直到得到一个不再含有递归项的等式。

通过这种方式，我们可以得到递归式的解析解。

例如，考虑递归式T(n) = T(n-1) + n，其中T(1) = 1。

我们可以使用递归展开法来求解这个递归式。

将递归式展开一次，得到T(n) = T(n-2) + (n-1) + n。

接着，再次展开，得到T(n) = T(n-3) + (n-2) + (n-1) + n。

继续展开，我们可以得到T(n) = T(n-k) + (n-k+1) + (n-k+2) + ... + (n-1) + n。

当展开到T(n) = T(1) + 2 + 3 + ... + (n-1) + n时，我们可以发现这个式子等于等差数列的和，即T(n) = 1 + 2 + 3 + ... + (n-1) + n。

利用等差数列求和公式，我们可以得到T(n) = (n+1)*n/2。

因此，递归式T(n) = T(n-1) + n的解析解为T(n) = (n+1)*n/2。

二、主定理主定理是求解递归式的另一种常用方法。

它适用于一类常见的递归式，即形如T(n) = aT(n/b) + f(n)的递归式。

其中，a是递归式中递归调用的次数，b是递归式中问题规模的缩小比例，f(n)是递归式中除了递归调用外的其他操作。

主定理的基本思想是通过比较递归式中不同部分的增长速度，判断递归式的解析解的形式。

主定理的具体表述如下：设递归式T(n) = aT(n/b) + f(n)，其中a≥1，b>1，f(n)是一个非负函数。

1. 如果存在一个常数ε>0，使得f(n) = O(n^log_b(a-ε))，则T(n) = Θ(n^log_b(a))。

【算法复习】求解递归式的⽅法求解递归式的⽅法【代⼊法】代⼊法求解分为两步：猜测解的形式⽤数学归纳法求出解的常数C，并证明正确性，关键步骤是⽤猜测的解代⼊到递归式中。

做出好的猜测（没有⼀般⽅法，只能凭经验）与见过的解类似，则猜测之。

先证较宽松的上、下界，减⼩猜测范围。

我们可以从下界Ω(n)开始，上界O(n^2)，然后逐渐收敛⾄(nlog2n)细节修正有时猜测解是正确的，但数学归纳法却不能直接证明其细节，这是因为数学归纳法不是强⼤到⾜以证明其细节。

这时可从猜测解中减去⼀个低阶项以使数学归纳法得以满⾜避免陷阱与求和式的数学归纳法类似，证明时渐近记号的使⽤易产⽣错误。

如：证明O(n)时必须严格证明≤cn，不能讲其换做cn+n变量变换有时改动变量能使未知递归式变为熟悉的式⼦。

例如：【代⼊法例题】【递归树法】递归树最适合⽤来⽣成好的猜想，然后可⽤代⼊法来验证猜测是否正确需要关注：达到边界条件所需的迭代次数迭代过程中的和式。

若在迭代过程中已估计出解的形式，亦可⽤代⼊法【递归树法例题】【Master原理】Master定理也叫主定理。

它提供了⼀种通过渐近符号表⽰递推关系式的⽅法。

应⽤Master定理可以很简便的求解递归⽅程。

定理4.1（主定理）令a≥1和b>1是常数，f(n)是⼀个函数，T(n)是定义在⾮负整数上的递归式： T(n) = aT(n/b) + f(n)其中我们将n/b解释为。

那么T(n)有如下渐近界：主定理的三种情况，经过分析，可以发现都是把f(n)与⽐较。

第⼀种情况是更⼤，第⼆种情况是与f(n)相等，第三种情况是f(n)更⼤。

【主定理例题】。

递归方程求解方法综述摘要：随着计算机科学的逐步发展，各种各样的算法相继出现，我们需要对算法进行分析，以选择性能更好的解决方案。

算法分析中计算复杂度常用递归方程来表达，因此递归方程的求解有助于分析算法设计的好坏。

阐述了常用的3种求解递归方程的方法：递推法、特征方程法和生成函数法。

这3种方法基本上可以解决一般规模递归方程的求解问题。

关键词：递归；递推法；特征方程；生成函数0引言寻求好的解决方案是算法分析的主要目的，问题的解决方案可能不只一个，好的方案应该执行时间最短，同时占有存储空间最小，故算法分析一般考虑时间复杂性、空间复杂性两方面的参数。

在算法分析时我们采用时间耗费函数来表示时间参数，用当问题规模充分大时的时间耗费函数的极限表示时间复杂度。

一般算法对应的时间耗费函数常用递归方程表示，找出递归方程的解，就可以表示其对应算法复杂度的渐进阶，从而比较算法的优劣。

因此研究递归方程的解法意义重大。

下文将分析并给出常用递归方程的3种解法。

1递归方程的解法递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的规模要小。

对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型。

根据递归方程的一般形式，常用的解法有三种，分别是递推法、公式法及生成函数法。

下面就分别来分析其求解过程。

1.1递推法当递归方程形式简单且阶数较低时，一般可以采用递推法求解，根据一步一步递推找到方程的递推规律，得到方程的解。

下面举例说明： t(1)=0t(n)=2t(n/2)+n2(n≥2)t(n)=2t(n/2)+n2=2(2t(n/22)+(n/2)2)+n2=22t(n/2)2+2n2/22+n2=22(2t(n/23)+(n/22)2)+2n2/22+n2=23(2t(n/23)+22n2/(22)2)+2n2/(22)1+n2…=2kt(n/2k)+∑k-1i=02in2(22)i递推到这里我们就可以发现递归规律，找到递归出口， t(1)=0，令n=2k 则可以得到如下结果：t(n) =2kt(1) +∑k-1i=0n2(1/2)i)=n2(1-(1/2)k1-1/2)=2n2-2n 上面得到方程的解，我们来分析其对应算法复杂性的渐进阶，根据渐进阶定理有：设有函数f(n)，g(n）均是规模n的函数，则o(f(n))+o(g(n))=o(max(f(n), g(n)))。

递归算法递推公式求解递归算法是一种自我调用的算法，它通过不断将问题分解为更小的子问题来求解问题。

递归算法的核心是递推公式，也称为递归式，它描述了如何将问题分解为子问题，并如何从子问题的解中得到原问题的解。

递推公式通常具有以下形式：T(n) = aT(n/b) + f(n)其中，T(n) 表示问题规模为n 时的时间复杂度，a 表示每次递归调用的次数，b 表示每次递归调用后问题规模缩小的比例，f(n) 表示除了递归调用外的其他操作的时间复杂度。

为了求解递推公式，我们可以使用以下方法：1.迭代法：通过迭代递推公式的方式逐步计算出T(n) 的值。

这种方法比较直观，但对于较大的n 值，迭代次数可能非常多，计算量也会非常大。

2.替换法：通过猜测T(n) 的形式，并将其代入递推公式中进行验证。

如果猜测正确，则可以得到T(n) 的解。

这种方法需要对问题有一定的了解和猜测能力。

3.大师定理：大师定理是一种求解递推公式的通用方法。

它可以根据递推公式的形式，直接给出T(n) 的时间复杂度。

大师定理有多种形式，其中最常用的是以下三种：a. 如果f(n) = O(n^c)，其中c < log_b(a)，则T(n) = O(n^log_b(a))。

b. 如果f(n) = O(n^c)，其中c = log_b(a)，则T(n) = O(n^c * log_n)。

c. 如果f(n) = O(n^c)，其中c > log_b(a)，且对于所有足够大的n，有af(n/b) <= f(n)，则T(n) = O(f(n))。

需要注意的是，大师定理只是一种求解递推公式的工具，它并不能解决所有类型的递推公式。

在实际应用中，我们需要根据具体问题选择合适的求解方法。

递归式的三种求解⽅式求解递归式对于分冶算法的重要性不⾔⽽喻以下介绍了三种求解递归式的⽅法1，代换法：缺点：代换法主要的缺点在于，对于任何递归式，我们先得去猜其解，对于猜错了同学，如果不幸猜出的结果和正确结果相差太⼤，虽然可以推导，但是意义不⼤；优点：代换法相较于递归树法更为严谨，相较于主定理应⽤范围更⼴，主定理只能求解类似于T(n) = aT(n/b)+n/c这种形式的递归式；下⾯给出⼀个递归表达式T(n) = 2T(n/2)+n，求其解；⾸先猜⼀下其解为O(nlgn);那么我们只需要证明T(n)<cnlgn即可先假设T(n)<cnlgn对于n/2也成⽴，那么T(n/2)<=c(n/2)lg(n/2)也成⽴那么必然的T(n)<=2(c(n/2)(lgn/2))+n-=cnlgn-cnlg2+n<=cnlgn-cn+n以上表达式，在c>=1时永远成⽴，得证递归式T(n) = 2T(n/2)+n的解为O(nlgn)其他递归式的求解⽅式和上⾯的⼤体相似；2,递归树法递归树⽅法利⽤了将递归式分解为⼀棵递归树的形式来更加直观的求解递归式；缺点：递归树⽅法求解递归式因为丢弃了很多低阶项，所以不够严谨；优点：递归树⽅法求解递归式从视觉上更为直观，简单。

⼀般可以先运⽤递归树求解，然后利⽤代换法更加严谨得证明⽤递归树求解的解的数学上的正确性；下⾯求T(n) = 2T(n/2)+n的解⾸先将上述递归表达式⽤递归树表达出来，不会画图，⽐较丑。

以上递归式的深度为lgn,每层的代价为n,⾃然推导出T(n) = T(n/2)的解为O(nlgn)以上递归式的求解⽐较简单更为复杂的求解参考算法导论；3,主定理主定理是最为简单求解递归式的解的⽅法，也是我最为喜欢的⼀种分析⽅法主定理给出如下的如下形式的通⽤的递归式:T(n) = aT(n/b)+f(n)主定理套公式分为以下三种情况符号打得⼼累直接截图：以上为三种递归式的求解⽅法。