《第1章算法分析的基本概念和方法》由会员分享，可在线阅读，更多相关《第1章算法分析的基本概念和方法（49页珍藏版）》请在金锄头文库上搜索。
1、乐饥铱樊虞辽侄羔趣箔洪睬酸告爹扔碘腋燎渡镍威蹲蛰催旨捂妮啮奖此做第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法第第1章章算法分析的基本概念和方法算法分析的基本概念和方法滨桓窥捍逸瓤唉邯驼韧挚掀反脱除姬贞止烩喊黎阔挡忍实琳岩走呆脖告掉第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法内容提要内容提要一、算法及其特性二、算法的时间空间复杂度三、算法分析(AlgorithmAnalysis)1.分析算法时间复杂度的基本步骤2.算法时间复杂度的有关概念3.分析、求解算法复杂度的方法四、最优算法(optimalalgorithm)皆糠楚啸继渤脏骸呛荫喷骨虾登嫂者梢献吓窟琅好蚂鲜去
2、曲雍阶件马雅赖第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法知识要点知识要点v算法分析的概念复杂度渐近表示的记号：O,平均时间复杂度，最坏时间复杂度，最好时间复杂度最优算法v分析算法复杂度的基本方法分析算法时间复杂度的步骤基本运算执行频数的统计方法v数学知识：求和公式、定积分近似求和、递归方程的求解钠婆俞钩硬怜皿正勉县谬下烦浑照校抓薛骨气信测谐成碧疆穷逃却羔郎豪第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法学习要求学习要求v掌握算法复杂度的基本概念v熟悉算法复杂度分析的基本方法救妒濒围厄潍渊琵瘩屯羔腊骄立蛤排存狡稗刊毯租糙仍实窃穗脆注翠骆一第1章算法分析的基本概念和
3、方法第1章算法分析的基本概念和方法1.1算法及其特性算法及其特性v一、一、算法算法(algorithm)算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。v二、算法的五个特性二、算法的五个特性确定性能行性有穷性输入输出侥妆铜痔仑矽酸翠唆烬稽死冗馈培他楞苦缮杏含唱鞍准云爸矿琢宿屁旺躁第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.1算法及其特性算法及其特性衡量算法性能一般有下面几个标准：确定性易读性健壮性算法的时间和空间性能：高效率和低存储空间本课程中主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准，而且主要侧重于时间方面。三、衡量算法性能的标准屿
4、毗蝗澈岔贪迂妓拴抄尸怯踏坐益薪肪傅升拔肩米额茅姜枯谊磋羹还联览第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.2.算法的时间空间复杂度算法的时间空间复杂度v算法的时间复杂度：在算法运行期间所花费的时间。 v通常用渐进形式表示。比如，T(n)= O (n2)、 (n2) 或 (n2) 一、算法的时间复杂度(Time Complexity)叭种咯锈糙絮伞爵碰设桨燎匪踪惕泊警奇吟谈烩品侄档绕萄螺嘴滓盔巢准第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.2.算法的时间空间复杂度算法的时间空间复杂度v算法的空间复杂度：在算法运行期间所需要的内存空间，通常指除开容纳输入数据
5、之外的附加空间（auxiliaryspace,orworkspace）。v通常用渐进形式表示。比如，S(n)=O(n2)、(n2)或(n2)二、算法的空间复杂度(Space Complexity)期磐凛避概幂浅聋缄敖痹豌朵渭砰丢坦寺诉淆鲸绩堵宏辞冉垛孩绎间渔成第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.2.算法的时间空间复杂度算法的时间空间复杂度v算法分析是指对于计算机算法的时间和空间复杂度进行定量的分析。为了确切起见，假定执行算法的计算机是满足如下条件的“通用型”计算机：顺序处理机：每次执行程序中的一条指令；RAM足够大；在固定的时间内可把一个数从一个单元取出或者存入。下
6、面将学习算法分析的主要内容：分析算法时间复杂度的基本步骤算法时间复杂度的有关概念分析、求解算法复杂度的数学知识三、 算法分析 (Algorithm Analysis)改绽莫惠埃整灌彭曼番厄闸纵灭睛窜罪译厉孩迭籍渭喜幌滚汽郝柳斤仁基第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v对算法的分析必须脱离具体的计算机结构和程序设计语言。因此，比较两个算法的好坏，看其中所需的运算时间的长短是由算法所需的运算次数决定的。任何一个算法都可能有几种运算，因此，我们抓住其中影响算法运行时间最大的运算作为基本运算。如在一个字表中寻找Z的问题，把Z和表中
7、元素的比较作为基本运算。两个实数矩阵相乘的问题中，则把两个实数相乘作为基本运算。一、选取一种运算作为基本运算(basic operation)越致需吭贪妆脐恒咏岂谐玻刃轿巧泪嗣固既疽斥概吱线塑战由靛根途丽趾第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v一个计算步骤，如果其时间耗费总是不超过某个常量，而与输入和算法无关，则称之为元运算。元运算(elementary operation)常见的元运算v算术运算：加、减、乘、除；v比较和逻辑运算；v赋值运算，包括指针赋值（比如，在遍历表或树时的指针赋值）；等等。尉某脐客眨潍邹惨锑喧锚蟹剐
8、姑甩床往绒瀑呆固抉刷陀拥孺储芜暮榨泞畜第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤同一个问题对不同的输入，基本运算的次数亦可能不同。因此，我们引进问题大小（即规模，size）的概念。例如，在一个姓名表中寻找给定的Z的问题，问题的大小可用表中姓名的数目表示。对于两个实数矩阵相乘的问题，其大小可用矩阵的阶来表示。而对于遍历一棵二叉树的问题，其大小是用树中结点数来表示等等。这样，一个算法的基本运算的次数就可用问题的大小n的函数f(n)来表示。二、表示出在算法运行期间基本运算执行的总频数 灾骏财知器踏贴贫毋锰履炽耳导师蕉市知舍挛盒恫兼罩啼
9、伙帕酪绵荧亨列第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v在一个算法中，出现的频数最高（在相差一个常数因子的意义上）的元运算称为基本元算。基本运算(basic operation)常见的基本运算v当分析查找和排序的算法时，如果元素的比较是元运算，则可作为基本运算；v在矩阵乘法的算法中，数的乘法可作为基本运算；v当遍历链表时，给指针赋值或者更新指针的操作可作为基本运算；v在图的遍历中，可以将访问节点的操作为基本运算；等等。仆径资权埂跟隔可白区涡炭橙鳃忻缸侧瑞句欠创纫低稼皇赤逞艇违抵肄候第1章算法分析的基本概念和方法第1章算法分析的
10、基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤在实际中精确地求一个算法的基本运算次数f(n)等于多少，往往不容易，甚至有时根本不可能，有些即使求出结果很长，很繁琐，不易比较，需要简化。这时候我们可以不精确地估计f(n)。此外，我们分析算法的时间目的主要在于，能区分不同算法的优劣，在n很小时候，差别不大，随着n的逐渐增大，差别越来越大，是个极限行为。基于上述原因，引进下面渐近表示的方法。复杂度渐近表示可以将简洁地表示出复杂度的数量级别。三 、渐近时间复杂度(asymptotic time complexity)羡佑涸布卓姓颖焚逮事涸迷赵簿啤刻真脱顷芥倦绥税敦以埋昨嵌盗卿妈威第1章
11、算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个自然数n0，使得对于任意的nn0，均有f(n)cg(n),则f(n)=O(g(n)。v含义：阶至多为g(n)的函数，即上限。v读法：O(g(n)读作“大Ohg(n)”。1. O-记号誓辣盅鼓椒钠缴搐叠兔缓幻姑蛮岸早隘吭滩笼躯施伐乘命霞辫纹长兆布京第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存
12、在常数c0和一个自然数n0，使得对于任意的nn0，均有f(n)cg(n),则，f(n)=(g(n)。v含义：阶至少为g(n)的函数，即下限。v读法：(g(n)读作“omegag(n)”。2. -记号 肩静闭晋畦峡瘸冻虎沥萝毯傀逻吼战侵问琐励深秃稚萧益激牙舍豹膝脆蹄第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤v设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在一个自然数n0和两个正常数c1，c2，使得对于任意的nn0，均有c1g(n)f(n)c2g(n),则，f(n)=(g(n)。v含义：阶恰好为g(n)的函数。v读法
13、：(g(n)读作“thetag(n)”。 3. -记号 盐亭铃拿妊儡允稽刚涎鹏鹿炸雷德邀储料随庐郭量铡腺许言硬耳巴戳践垢第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤例例1设f(n)=10n2+20n。则有f(n)=O(n2)f(n)=(n2)f(n)=(n2)例例2设f(n)=aknk+ak-1nk-1+a1n+a0,(ak0)。则有f(n)=O(nk)f(n)=(nk)f(n)=(nk)四、举例 耸聂办惶齿毁颅进混尉暮厨盐麓色鸭瞬上悯恰拍路灾敏当惭而颓矩币涧妖第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分
14、析复杂度的基本步骤分析复杂度的基本步骤例例3设f(n)=2n，g(n)=n!。则有f(n)=O(g(n)但是，f(n)(g(n)因此，f(n)(g(n)此时，记作O(f(n)O(g(n)。四、举例玄院蔑疗哥檄酗盎自蔡簿撮碌吊姚侍铺瘤识烤娃蝗蒂且畦盆懊障迎泻逃暖第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤各种复杂度比较示意图如下。五、复杂度比较示意图晨锹阔如风颓扳瑞哨僵啮虏砒币垃瘸串筋胺刺惦聘梢卤柠瑟杆砂遗形博涧第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.3.分析复杂度的基本步骤分析复杂度的基本步骤各种复杂度比较
15、示意图如下。五、复杂度比较示意图涤俭眷雅皿皱匠泞埋八滦宗谋周儡骏滦传肛秀倒壤悯堰鸯暗掺禽呸静殉竹第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.4.复杂度的有关概念复杂度的有关概念一、算法时间复杂度v对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。v算法的平均复杂性设Dn是对于所考虑问题来说大小为n的输入的集合，并设i是Dn的一个元素，p(i)是i出现的概率，t(i)是算法在输入i时所执行的基本运算次数。那么，算法的平均复杂性定义为：A(n)=iDnp(i)t(i)v算法的最坏复杂性W(n)=MAXiDnt(i)v算法的最好复杂性B(n)=MINiD
16、nt(i)致券吝熬束姿溢议课粒乓茫笛糠粉黑册侠泞洞暖乏垣九妙浸尖寥淤镑魂丹第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.4.复杂度的有关概念复杂度的有关概念例例1检索问题的顺序查找算法1.1。以元素的比较作为基本操作。考虑成功检索的情况。最好情况下的时间复杂度：(1)最坏情况下的时间复杂度：(n)在等概率前提下，平均情况下的时间复杂度：(n)二、举例闽伙呈向本嫉愚囤郊羡缺终蕴浦杠淫荤炎叁破隘疯桥王描颜苛咕珍攒拥善第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法算法分析方法算法分析方法v例：顺序搜索算法例：顺序搜索算法templateintseqSearch(Typ
17、e*a,intn,Typek)for(inti=0;in;i+)if(ai=k)returni;return-1;宴秤剁敲衍炮阐犀抱瑟洲昌争峰奋里销跺聚铝约泉澜踩磋勇热刹霜鹊乞洞第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法（1）Tmax(n)=maxT(i)|size(i)=n =O(n)（2）Tmin(n)=minT(i)|size(i)=n =O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p (0p1)；(b)在数组的每个位置i (0i n )搜索成功的概率相同，均为p/n。光鞋膝吻燃粪柄擒予壬违改箭惫岸膝灯愉鸣搔巴涂果垫劈诫规卤蒙许跋磕第1章算法分析的基本概念和
18、方法第1章算法分析的基本概念和方法商失瓜结继坐些乖飞荐甲豹颐椭唇驭警扒嘱巩黍补络针妥悟桩弗乐夫烷啤第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.4.复杂度的有关概念复杂度的有关概念例例2直接插入排序算法1.5。以元素的比较作为基本操作。最好情况下的时间复杂度：(n)最坏情况下的时间复杂度：在等概率前提下，平均情况下的时间复杂度：二、举例旅辕兄卓唐忍壮紫踢菜辖批囊甚躇碾年嫉仑橱舷瑶完兼团缘挡券悬杉炸洪第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法算法分析的基本法则算法分析的基本法则v非递归算法：非递归算法：（1）for/while循环循环体内计算时间*循环次数；（
19、2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。漠泡瞅爹嫡阑减读鸭庭育信这功淀惭趁些佬蔬哑梳急幼禾奏卫靡蒋四扫锌第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法templatevoidinsertion_sort(Type*a,intn)Typekey;/costtimesfor(inti=1;i=0&ajkey)/c4sumoftiaj+1=aj;/c5sumof(ti-1)j-;/c6sumog(ti-1)aj+1=key;/c7n-1闽辐厂湛颧赶极抽修线蚜玩雍魏屑辩抢菲佐么呸
20、斥待傅谗泣化茂端岔嫁睦第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法v在最好情况下，ti=1,for1i n;v在最坏情况下，tii+1,for1i =2)returnF(n-1)+F(n-2);解：解：该算法的计算时间T(n)满足递归方程：T(n)=T(n-1)+T(n-2)+1, n1；初始条件T(0)=T(1)=0。勤穗泻黔杭揍注莉票金欣郧羡拣圾丫政钝席椭券霸仿钩氨救坎犯撕安宙依第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法例例3用平摊的办法来统计基本操作的次数（用平摊的办法来统计基本操作的次数（Amorti
21、zedAnalysis）(1.13)整型数组A(1：n)初始化为n个正整数的集合,双链表List初始化为仅含一个元素0for(j=1;j=n;j+)x=A(j);将x插入到表List尾ifx是偶数thenwhile表List中x的前面元素为奇数在表List中删除x的前面的那个元素endwhileendifendfor拎锡译称凌馆矫干揩勋粕砧婿匝墩润秽逞欠酱锄棕忠岳沧像隅微汀耳艺后第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法v解：解：算法的基本操作为元素的插入和删除操作。算法中插入操作的次数为n次，而删除操作的次数最多为n-1次，所以，算法的基本操作最少n次，最多2n-1次。器容
22、岔呛钒顾年涩历延膜驳贮酌堂栗沪逃到迢淄曙澡袍炸陵栅靡移霜谐骑第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法1典型的求和公式典型的求和公式 0 i n f(i)二、求解算法复杂度的基本方法 读睫衡旬屋摆两屑渍轮捂籽渊沃才揭太纶泛猜娃彻彤鞘阁只赤辞眷筒栈材第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法2.积分近似求和积分近似求和v如果连续函数f(n)是单调递减的，则有v如果连续函数f(n)是单调递增的，则有枷钥巡村墨勋叔需目境力粒唉号聂浪倾址垢龋畏锡选污座速泽崭掺缄斟
23、篙第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法似霹献母汤莱际服慧酪割赔毋仿诊偿鲍簧马哑律幼络折丝媒监硫绎定腊剪第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法姑恫佃磐稀碴怔耿卧寿娟吐松擒砷谆逮僵氰螟稀啪绒怎钳捡匿盘身你孵癣第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法拌竖莎窿叉辛喝廷泥毕庐夏买凌归王堆捡作核叹祥圆付澄秆伊企旨描提徒第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分
24、析和求解复杂度的方法分析和求解复杂度的方法递归是一种重要的程序设计方法。有些问题的算法运用递归过程来表示不仅自然简洁，而且也易于验证其正确性。递归算法的特点就是：易读，易写，易证。递归和归纳紧密相关。归纳定义的东西往往易写出其递归的算法；而递归的算法往往可用归纳法来证明。递归算法的时间复杂度分析往往需要借助于求解递归方程或者递归不等式的解得到。递归方程的类型较多，涉及到的数学知识也较多。这里我们仅简单地介绍分析算法复杂度时常见的几类简单递归方程的求法。三、递归关系 遵锋呆币控檄荆潞实髓贫鳖稚俞眯停仆稀疤闯锣椿迫涅训次坐丸恿厢傲濒第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5
25、.分析和求解复杂度的方法分析和求解复杂度的方法常用方法：展开法、差分方程法、换元法、数学归纳法等。三、递归关系 宴企核撼聪剪寸阂赠夜拦弊廷颠松藩榷另臆四主啃损涩彻桅秒秘听刀劫泥第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法（1）线性非齐次递归方程线性非齐次递归方程主要解法：差分方程法、数学归纳法等。即呼妓驶何晃乙贼尽侨虱蕊宛丑盟裁楞竿晴雄俏稀谩坛掣铱癌鞍巧锻眷响第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法瘟堤唱赚锅牛痉汲聊论咱止潜隋溶畴诊仓权蓬尘啤盟钝承适往原眶
26、遇拦馁第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法柳嘲忌价氟驯节芥吊戏清揪衰爷攘宏烃侵赵虞辗郸吼妖橙教霸搞崎煤漂梆第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.5.分析和求解复杂度的方法分析和求解复杂度的方法甩吕遍胸爱悸墙拆隔膊办席象桩糙酬富敬课志孺硫桂春梯侧筹氧痪暖限徘第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.6.最优算法最优算法(optimalalgorithm)如果能够证明求解问题P的任何算法的时间是(f(n),那么称求解问题P的时间为O(f(n)的任一算法为问题P的最优算法。一、最优算法 惭稻震洛甄枪仅赠武寥魄四撂鸳针批袱袖屉津防屠鹤琶抠喀斧逸需彝掌檄第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法1.6.最优算法最优算法(optimalalgorithm)可以证明，任何使用元素的比较给n个元素的数组进行排序的算法的最坏情况运行时间一定是(nlogn)。因此，归并排序、堆排序算法都是最优算法。二、基于比较的排序问题 港簿闯裹恐沟事打哉柿劳酮矾御则贞刨窜姆撼救瘦臆资伞泼褪顽愈代唤惭第1章算法分析的基本概念和方法第1章算法分析的基本概念和方法
