递归方程解的渐近阶的求法

教育专区 > 初中教育 > 数学 > 文档预览

18 页 1155 浏览 4 收藏 5.0分

摘要:递归方程解的渐近阶的求法递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。1.代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。2.迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。3.套用公式法这个方法针对形如：T(n)=aT(n/b)+f(n)的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。4.差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。然后对得到的解作渐近阶的估计。5.母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。本章将逐一地介绍上述五种方法，并分别举例加以说明。本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。递归方程组解的渐进阶的求法——代入法用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后

温馨提示：当前文档最多只能预览 5 页，若文档总页数超出了 5 页，请下载原文档以浏览全部内容。

下载文档到电脑，方便使用

下载文档

当前文档最多只能预览 5 页
还有 2 页可预览，继续阅读

本文档由匿名用户于 2020-11-14 05:15:56上传分享

下载原文档(211.00 KB)

你可能在找

高一数学用二分法求方程的近似解4

优游http://www.youyouugame.com/一天在作家群浏览，看到秘书长发的“同舟共济，诗歌在感召——抗疫诗歌专辑”征稿通知，就立马在手机上写草稿了。我在猪年的端午节那段时间从岭南北上，回到了江南老家。那时正是龙船水暴涨的时候，我在雨中参观了湖湘文化源头贾谊故居，参观了湖南第一师范旧址，寻访了长沙的几条古街，就继续北上，跨过长江，到了湖北的境地。在车上观看华中大地，白雾缭绕的田野村庄，如人间仙境。到了长江上游的一座城市，这里竟然是千年古城，人们安居乐业，这还是在湖北境内。我在江边徜徉，绿悠悠的柳树下，有老人在吊嗓子，也许是古戏爱好者吧。

4.7 分 10 页 | 1.73 MB | 2020-11-10 10:18
求双曲线的标准方程的解法比较

求双曲线的标准方程的解法比较题例、求渐近线方程为29yx，且过点(,1)的双曲线的标准32方程. 【解析】求双曲线方程的关键是首先必须确定焦点在什么坐标轴上，在已知渐近线方程与图像上的点的情况下，可以由渐近线的性质来确定，即把点的横坐标代入渐近线方程，所得的值如果小于已知点的纵坐标，就说明双曲线的焦点在 x轴上，否则，焦点就在y轴上；用待定系数法会减轻运算量．法一、解：因为y(9)2设双曲线方程为2931，故双曲线的焦点在x轴上，故32x2y21，a2b292(2)(1)22

3.0 分 1 页 | 41.00 KB | 2019-12-04 20:24
您真的误解我了

您真的误解我了时间：2018-12-0813:42:41|作者：尤宇老师，您还记得四年级那次班会上您狠狠地批评我了吗？至今，那情景我依然历历在目。虽然您以前也批评过我，可是这次却让我十分伤心，因为您误解我了，被冤枉的滋味不好受。许登璐这时说是另外一个同学丢在地上的，然而那个同学努力为自己开脱，结果您以为她是无辜的，把我们得的“A”给了她，还说我们诬陷她。下课了，我的心情像盐、醋、辣椒、酱、糖撒在一起一样，极度悲伤，哭了。

4.9 分 1 页 | 14.94 KB | 2022-04-21 10:42
0基础如何有目的性的学室内软装设计的方法

0基础如何有目的性的学室内软装设计的方法室内设计可以说是现在的一门大热行业，如果说室内设计就像是一块大蛋糕，那所有人都想从这大蛋糕上分走一块，而室内设计中软装设计又是其中必不可少的一项，那么我们0基础的朋友该掌握哪些方法去学习室内软装设计呢一：美学基础于艺术修养的培养要懂得一定的地域文化差异以及民族文化传统礼仪、生活习惯等等，才能搞清楚各种装饰风格的特点与原理，灵活把控各种风格的文化元素，不同元素应用在不同场合能够展现出不同的风格才是我们需要去掌控的二：搭配技法的实践锻炼一定要懂得空间与色彩、风格、材质、灯光之间的搭配应用关系。如果室内空间是作品的躯壳，那么风格就是作品的灵魂，不同的色彩可以表达出不同的情绪，也能间接反映出人的性格。

4.9 分 2 页 | 279.50 KB | 2021-02-08 17:18
编译原理分知识点习题-自上而下语法分析

1.设有文法G[S]：S→ABA→bB|AaB→Sb|a试消除该文法的左递归。解：本题考查消除左递归的方法。应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：（1）将非终结符排序为：U1=S，U2=A，U3=B（2）进入算法排序：i=1时，对文法无影响i=2，j=1时：A→Aa有直接左递归，消去该直接左递归，得A→bBA’A’→aA’|εi=3，j=1时：改写文法，有B→ABb|aj=2时：改写文法，有B→bBA’Bb|a无左递归。

4.9 分 10 页 | 113.50 KB | 2022-12-24 23:42
双曲线题型归纳含(答案)

资料三、典型例题选讲（一）考查双曲线的概念例1设P是双曲线x2y21上一点，双曲线的一条渐近线方程为3x2y0，F1、9a2F2分别是双曲线的左、右焦点．若|PF1|3，则|PF2|（）A． 1或5B．6C．7D．9分析：根据标准方程写出渐近线方程，两个方程对比求出a的值，利用双曲线的定义求出|PF2|的值．解：双曲线3x2y21渐近线方程为y=x，由已知渐近线为3x2y0，2a9a a�2,||PF1||PF2||4，|PF2|4|PF1|.Q|PF1|3,|PF2|0，|PF2|7.故选C．归纳小结：本题考查双曲线的定义及双曲线的渐近线方程的表示法．

3.0 分 8 页 | 332.50 KB | 2019-11-11 05:38
一元二次方程的解法配方法2

4.7 分 1 页 | 486.00 KB | 2020-11-03 23:55
什么是吐字归音

核心提示：吐字归音是我国传统说唱理论中提及咬字方法时所用的一个术语。...吐字归音是我国传统说唱理论中提及咬字方法时所用的一个术语。从汉语音节特点出发，把汉字一个音节的发音过程分为字头、字腹、字尾三个阶段，吐字归音是口腔控制重要一环。吐字归音的要领是：出字出字是指头（声母）和颈（介音，也叫韵头）的发音过程，即“咬字”阶段。咬字要求干净利落、弹发有力，并与韵头迅速结合。如电dian，d是字头，i是韵头，a是字腹，n是字尾。整个字头的发音应具有一定的弹射力，这是整个音节是否有“力度”的关键。

3.0 分 1 页 | 99.23 KB | 2019-06-09 05:58
顺丰快递stp战略分析

顺丰快递stp战略分析一．市场细分?1.快递市场细分的标准：?1）地理因素?快递行业的经营业务和物流行业一样，都是通过在一定的时期内，在不同的空间范围内运输客户的物品，这就必然涉及到地理因素。不同地理区域的经济发展状况，地理环境，交通运输条件等都存在很大差异，而这些差异往往影响到快递企业的物流速度，运送成本，运送方式。而不同地理位置的客户对于快递需求和服务要求是有差别的。企业要识别这些差异，制定出有针对性的营销战略。?2）人口因素?对于快递行业来说，分析人口因素主要包括年龄，收入，社会阶层等。不同年龄段的人对于快递服务的需求程度是显着不同的。

3.0 分 6 页 | 12.28 KB | 2020-02-06 07:22
线性回归方程

环球雅思学科教师辅导讲义讲义编号：组长签字：学员编号：年学员姓名：课签字日期：级：高二课时数：3辅导科目：数学学科教师：闫建斌线性回归方程题18:00-20:00精品文档，你值得期待2014-2-11授课日期及时段线性回归方程基础教学目标重点、难点教学内容1、本周错题讲解2、知识点梳理1．线性回归方程①变量之间的两类关系：函数关系与相关关系②制作散点图，判断线性相关关系③线性回归方程：ybxa（最小二乘法）最小二乘法：求回归直线，使得样本数据的点到它的距离的平方最小的方法 �n��xiyinxy�bi1n�2�xi2nx��i1��aybx注意：线性回归直线经过定点(x,y)n2．相关系数（判定两个变量线性相关性）：r(xix)(yiy)i1nni

3.0 分 11 页 | 330.11 KB | 2020-04-28 15:00