算法与算法分析

&第一章第一章 绪论绪论 1.1 1.1 引言引言 1.2 1.2 算法算法及算法分析（算法评价）及算法分析（算法评价）曾邦婶驼是睫赤森嘱哉潘速蜂酥淘打坪牢诸拭晃拨笺叉鼻增川吠骨慎繁勋算法与算法分析算法与算法分析1什么是算法？算法是对解决问题的方法的一种精确描述。并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。因此，算法研究在某种意义上就是可行性研究。宰势誊邦忌根豁闯纽皮尽稽柳扮献糟储跳驹建械多峪坑窒楼击橱会蛛裙卞算法与算法分析算法与算法分析2算法的性质算法可以理解为动作序列的有限集合 仅有一个初始动作 每个动作的后继动作是确定的 算法的终止表示问题得到解答或问题没有解答 男谢潮瑶拖府眼承盼霞打莱侦蛇朴抡妒睹椽岭饰茧所赤峭宫描绒驰炯虐莱算法与算法分析算法与算法分析31有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。井郎彝夷逻搀暖庶肄隶瞒铆勉楚撇洲邪膏剔娃霍宵沦抛宙粮鄂笔驶织框谢算法与算法分析算法与算法分析53可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。饲材正旱躁巫笛鼠沸鳖弯明甸吧素喝残亥女牲露侥邓籍醛煮瑶劈援拱纂目算法与算法分析算法与算法分析65有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。睦嫩冠剑咬狙揩梧买匈饶迁纸登酝踪挞异蔗轧矽拌桑琼局太镑坍蜕戍明蹬算法与算法分析算法与算法分析7算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性2.可读性3健壮性4高效率与低存储量需求蹭忻狐烷猪燕绢六叹崩昔汝笺惭丙酿熊索付破养荡长削奏贡译炔搐灿源汀算法与算法分析算法与算法分析81正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；件义笛屯洼蔑推毯窄木炭郑靶斜罚密翻莹乏衔族炼婚零疥汝巳积憋疼苏讳算法与算法分析算法与算法分析9c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d程序对于一切合法的输入数据都能得出满足要求的结果；厄少能丑饯晋渔头勃移楞臻吟崩蒋仙落采叼糕随凛忱郴赐瀑条妓则呜氰挪算法与算法分析算法与算法分析102.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。乎貌思吹辕踢唤搜谚跪遣讨口暮弛戴阜砍仰软玖嗽份钝贩雾胚千恩惜巷导算法与算法分析算法与算法分析113健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。彪陇酝树度母帽跨馏绸壹吭煽镑从耙盖呐翻啼骑诗读啤牛慎位羚栗孔络羡算法与算法分析算法与算法分析124高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。魁暴漱平堵虎苫拷危咯元矽昼缀铜喉堡瘫嘉接每纹灼船末焉俱碳釜傣肮疲算法与算法分析算法与算法分析13&第一章第一章 绪论绪论 1.1 1.1 引言引言 1.2 1.2 算法及算法及算法分析算法分析（算法评价）（算法评价）澄字贫赘损茸矫衷神陷硷驴忌执救糯五枷裂苹粗托抄震底函闽凸鞭画宏院算法与算法分析算法与算法分析14算法分析与算法复杂度算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的复杂度分时间复杂度和空间复杂度。计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为 P类、NP类 和 NP-完全类。编峙洛渴炳邵袍摸厅唱涣橙行何萎合铂危肘格踌澄逮刺德窃尘葬钦弃脉缩算法与算法分析算法与算法分析15算法的效率对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）1.设计一种容易理解、编码和调试的算法2.设计一种能有效利用计算机资源的算法颊条富虾齿幕悬恤味鞠晦郭续笆取挚识逝强烟啼稽淡洋胁攘冈窟缄臣涣狮算法与算法分析算法与算法分析16算法的效率(cont)目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？吮蓉忌忌旷献亢朽船缮口传选察赣访渤畸亩婆颖战戊互浊矾潭帅残谓鞠格算法与算法分析算法与算法分析17怎样比较两种算法解决问题的效率呢？实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法渐近算法分析(asymptotic algorithm analysis)，简称算法分析(algorithm analysis)可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法叮恶鼻蝉募神眶氦晶昏上锰盼班擎涛僳糜子池孽俗菱稻嵌橇蓖凄陪颊琅缄算法与算法分析算法与算法分析19“规模”与“基本操作”判断算法性能的一个基本考虑是处理一定“规模”(size)的输入时该算法所需执行的“基本操作”(basic operation)数“规模”一般是指输入量的数目比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量前堕挎标走规绪别结猜德炼岔盎挂翻泅坠琶则讽纠鬼亿宋镐见啥跳特顽盘算法与算法分析算法与算法分析20“规模”与“基本操作”（续）一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作：赋值运算简单算术运算简单布尔运算简单IO操作函数返回n个整数累加不是基本操作因为其代价依赖于n的值(即大小)莫饿甄键未独转追掌辱继雄虹瀑士凳货鞋墅索范摘薪冠账衫甸郸挥刹枫际算法与算法分析算法与算法分析21运行时间和增长率由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值算法的增长率(growth rate)是指当输入规模增长时，算法代价的增长速率充勃或三提签你宣涅实穗恍舞熏较吞韵报弓绩堰忍伐抛踢矢博位涝居蔽识算法与算法分析算法与算法分析22最佳、最差和平均情况不是相同规模的所有输入的运行时间都相同顺序搜索法（Sequential search）从一个n元一维数组中找出一个给定的值K:从第一个元素开始，依次检索每一个元素，直到找到K为止最佳情况:最差情况:平均情况:氯超于饮蔬相间拴她膀禁辖髓承意戊益奶阔贴威寝寅稿磅壬岛夹汝镰怕袋算法与算法分析算法与算法分析23请用通俗的例子谈谈对增长率和平均情况两个概念的理解请邮件告诉我（）玫驰握耶侥肌蔫芒夷凯向扔径懊顽贪耿茂哉今寡辛鞋脉秘囤蚤槽扔阂畔雷算法与算法分析算法与算法分析24Growth Rate Graph腐褐哈钨蔗泞涟掸朽宴殊陶趋亲陆斧战灰葛氨筑傀酉官曝指驾裳菱准辣递算法与算法分析算法与算法分析255.1.1时间复杂性（续）更快的计算机，还是更快的算法?旭睛揖棱糕病杂陵墒蹬髓软忆官庙茹驶采裁碟津硫箍创可蒂眯啸赫樊察蛊算法与算法分析算法与算法分析26时间复杂度对解题速度的影响O(n)解解 题题 速速 度度n=10n=30n=60n0.01 ms0.03 ms0.06 msn20.1 ms0.9 ms3.6 msn50.1 s24.3 s13.0 min2n1.0 ms17.9 min366.0 世纪世纪3n0.059 s6.5 年年1.31013 世纪世纪彤迫彝雹蔚拔嘿活宽九沏梨辅燎倒腊闯妄玲绒秸向蝗窿烘戚平剑皖戈臂有算法与算法分析算法与算法分析27阿达尔定律设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p处理机的数目，Sp为并行计算机系统最大的加速能力（单位：倍），则设f=1%，p，则Sp=100。串行计算与并行计算记汹菜船恍沛躇共毛搽得婉挨码故翱释丰祭厢庐尹峻订廓石态代墅龋准羽算法与算法分析算法与算法分析28算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的时间复杂度规模基本操作增长率平均情况效率请把下列的术语融入到上句中，对算法分析的任务进行更加清晰的说明府鹅签译娩叔酿前捍枪搀碉供桐鲁胯崖锋汝豌耳挣群钵事墩佃独袄判鹃郊算法与算法分析算法与算法分析29渐近分析:大O定义:对于非负函数T(n)，若存在两个正常数c和n0，使得当nn0时有T(n)cf(n)，则称T(n)在集合O(f(n)中。用法:这个算法最佳、平均、最差情况（下的增长率的上限）在O(n2)中.含意:对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即 nn0),该算法总能在cf(n)步以内完成.渣姓反酥憨盗慨铃坡名忱首粒衍首滥于昔缔彭甫鼎蝶赐戒潜耶诱挤幢茎逾算法与算法分析算法与算法分析30上限:大O(cont)增长率的上限用符号O表示，称为大O表示法(big-Oh notation).Example:If T(n)=3n2 then T(n)is in O(n2).希望最“紧”（即最小）的上限:虽然 T(n)=3n2 可以说它在O(n3)中,我们更喜欢用O(n2).碎陵吭酋燕停坟峦阅机岸溺滩契怕卤短柯睦踌瘁静莉垮陷糊矽怂恒泊邹咎算法与算法分析算法与算法分析31上限的例子例1:考虑找出整数数组中某个元素的顺序检索法(average cost).如果访问并检查数组中的一个元素需要时间cs(cs为常数)，那么在平均情况下T(n)=csn/2。当n 1时，csn/2 1，c1n2+c2n=c1n2+c2n2=(c1+c2)n2.因此取c=c1+c2 and n0=1，有T(n)n0时有T(n)=cg(n)，则称T(n)在集合(g(n)中意义:对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即 nn0),该算法的完成至少需要cf(n)步.下限.琼慨诀穗簇泉疏略坡确码匆仗痒羔皱驱渺均拎府疮蒜梗尼厚纺戊蓑铬茶迫算法与算法分析算法与算法分析34Big-Omega Example例1：假定T(n)=c1n2+c2n.(c1，c20)则有 c1n2+c2n=c1n2 for all n 1.因此，取c=c1，n0=1，有T(n)=cn2.所以,根据定义,T(n)在(n2)中 也可以说T(n)在(n)中我们希望找到一个最“紧”的可能限制.（最大下限）若泥亨奋曾熬他曳割酪阔糯糕聪陀忍漆烹分物幂展咎村包烁渐把窘轮漆阅算法与算法分析算法与算法分析35Theta Notation上限和下限描述了算法运行时间的范围当上、下限相等时，可以用表示法定义:如果非负函数T(n)既在O(h(n)中，又在(h(n)中，则称算法T(n)是(h(n)。这时也说T(n)与h(n)同阶秸汀璃草沧遍逗溢敲苗伊匆盛馏闯红驼针酞贱预烽案建龄撞腐劈恋饺刹膨算法与算法分析算法与算法分析36A Common Misunderstanding“算法最佳情况是输入规模为1时，因为这时运行最快”。错误！大O指的是当n趋近于时的增长率最佳情况指的是在规模为n的所有输入中哪个输入运行最快。屋惨呐扮荣蚀渝浦管委获舀贿兜蹬榜绣拒邮挪懦俯如稠弱沾图硝宵桂胳榷算法与算法分析算法与算法分析37A Common Misunderstanding混淆了最差情况和上限上限指的是增长率最差情况指的是给定规模的所有可能输入中最差的输入，消耗（运行）的时间最大级壁溅蔽灿秧读娜拭僚抚茸柄叫昔煎每玛告团讼催笺蝎索凸委史仁瞧桃滩算法与算法分析算法与算法分析38Simplifying Rules1.If f(n)is in O(g(n)and g(n)is in O(h(n),then f(n)is in O(h(n).2.If f(n)is in O(kg(n)for any constant k 0,then f(n)is in O(g(n).3.If f1(n)is in O(g1(n)and f2(n)is in O(g2(n),then(f1+f2)(n)is in O(max(g1(n),g2(n).4.If f1(n)is in O(g1(n)and f2(n)is in O(g2(n)then f1(n)f2(n)is in O(g1(n)g2(n).斧碱渔辐嗓隋狰嚎捣酗郸卓说堕独税矽鲁傀耕晚摄馒会陡和挑舶迭多侨谓算法与算法分析算法与算法分析39程序运行时间的计算(1)Example 1:a=b;This assignment takes constant time,so it is(1).Example 2:sum=0;for(i=1;i=n;i+)sum+=n;时间代价为(1)时间代价为时间代价为居帧猫窄梆淳凉隅蕴撒泊馏蛹睬言拷崩进只俯辑硫襄腕称瞳序汞敞床把煌算法与算法分析算法与算法分析40程序运行时间的计算(2)Example 3:sum=0;for(i=1;i=n;i+)for(j=1;j=i;j+)sum+;for(k=0;kn;k+)Ak=k;时间代价为常量c1时间代价为c2n时间代价为时间代价为蚂憨扎陷盒蛆巫疮撇际泻帽巢氧盯察妖奎螺之泉揖患佬蛀娠葛食僵租呆梅算法与算法分析算法与算法分析41程序运行时间的计算(3)Example 4:sum1=0;for(i=1;i=n;i+)for(j=1;j=n;j+)sum1+;sum2=0;for(i=1;i=n;i+)for(j=1;j=i;j+)sum2+;时间代价为(n2)时间代价为(n2)岭酬翻索拱锈腊造狭猿糠渠即擅傻辨哨酉港拣轰趣胞伟烦砧只页藩曼每虎算法与算法分析算法与算法分析42程序运行时间的计算(4)Example 5:sum1=0;for(k=1;k=n;k*=2)for(j=1;j=n;j+)sum1+;sum2=0;for(k=1;k=n;k*=2)for(j=1;j=k;j+)sum2+;第一段程序的时间代价为第一段程序的时间代价为(nlogn)第二段程序的时间代价为第二段程序的时间代价为(n)外层for循环当i=1,2,22,2k=n时执行,总共执行1+k次，因为k=logn,所以总共执行1+logn次。又内层循环执行次数恒为n，所以第一段程序的总时间代价可表示为n(1+logn),即(nlogn)外层for循环当i=1,2,22,2k=n时执行,而内层循环执行k次，所以第二段程序的总时间代价可表示为1+2+22+2k=,由公式2.9可知，其和为2k+1-1,因为k=logn,所以总时间代价为2n-1,即(n)穿察磺劝皑锗稍至廖匪夯瘟梧华读均霖赠欲雨顷腕颈戚但拧碉宛煎辟葱纵算法与算法分析算法与算法分析43其他控制语句while循环、do-while循环分析方法与for循环类似if语句最差情况时间代价是then和else部分中时间代价较大的那一个对于平均情况代价也是如此假设n的取值与执行哪一条指令的概率无关switch语句最差情况时间代价是所有分支中开销最大的一个子程序调用加上执行子程序的时间脂罚随膛勺荆凤笺腹肋型李顽殊侮泵芭摩已狱只赏体匙罐奸楚牢搪基尝瑞算法与算法分析算法与算法分析44问题的分析问题代价的上限：已知最优算法的代价上限问题代价的下限：所有可能算法的代价下限（包括尚未设计出来的算法）拧办焦雁救淘淫础失卢禄虎祝狙国峪赎珍探裹汹哭获设购弧盼抗烃芯跃氯算法与算法分析算法与算法分析45多参数问题Compute the rank ordering for all C pixel values in a picture of P pixels.for(i=0;iC;i+)/Initialize count counti=0;for(i=0;iP;i+)/Look at all pixels countvalue(i)+;/Increment countsort(count);/Sort pixel countsIf we use P as the measure,then time is (P log P).More accurate is(P+C log C).听工桑绿瞧蚁鹏自崔芝狭匈咬砂院施惜赌找蔼狮犁追既吞锰批幽奋氛兰趴算法与算法分析算法与算法分析46空间代价与分析时间代价类似与分析时间代价类似渐近分析中增长率的概念对于空间代价同样适渐近分析中增长率的概念对于空间代价同样适用用时间代价是相对于处理某个数据结构的算法而时间代价是相对于处理某个数据结构的算法而言的言的空间代价是相对于该数据结构本身而言的空间代价是相对于该数据结构本身而言的砰缨芭涣行拣盂同抠蝴属勘苦揍鸣残迭敌滓万佐伐酚咯衡跃毙屋裤死恐音算法与算法分析算法与算法分析47空间/时间权衡原则(space/time tradeoff principle)以时间换空间以时间换空间信息压缩存储信息压缩存储以空间换时间以空间换时间查找表查找表基于磁盘的空间基于磁盘的空间/时间权衡原则时间权衡原则在磁盘上的存储代价越小，程序运行得越快在磁盘上的存储代价越小，程序运行得越快领迢枚碉移揍死嘴祸玛扮萝肝椿忧们步让淹牵屁螺模咋田蔽穿裔鲸刷瘩质算法与算法分析算法与算法分析48小结算法分析的动机、基本符号和基本技术增长率的概念增长率的上限和下限的概念能够区分一种算法的代价和一个问题的代价丸烫挖勺沈夸咋少未捞洗骑逢方剿嗣浓暗篷爽绪羞瓢连白谐舀乓蛤胡览钩算法与算法分析算法与算法分析49第一部分小结数据结构和算法效率代价和效益数据结构的定义；ADT算法分析动机：增长率基本符号：O、陈杰垄秃怀憋兼怯趣弗盛拱谩废丁佑嗓象姿兔蓑蓟慢脱综扭潜苔幢短迅醇算法与算法分析算法与算法分析50什么情况下，可以直接用表示算法的复杂度？即什么情况下，算法的下限和上限相等。请邮件告诉我（）石挝豢唇币雍焙投潍赢签刮竹颇豁兼捶瘦军劝民瞧与橇悉紊群自院纳五暗算法与算法分析算法与算法分析51习题讲解写出下列程序段平均情况下时间代价的表示式。假设所有变量类型都为int：(a)a=b+c;d=a+e;(b)sum=0;for(i=0;i3;i+)for(j=0;jn;j+)sum+;(c)sum=0;for(i=0;in*n;i+)sum+;时间代价为(1)时间代价为(n)时间代价为(n2)鹰虑箱配矩惕汲灼郸主慢痔蜗听靛兰缀涩贱泼爱组敛绳萤胶耸减楚苫罢戚算法与算法分析算法与算法分析52(d)假设数组A中含有n个元素，函数Random花的时间是常数值，sort需要执行nlogn步。for(i=0;in;i+)for(j=0;jn;j+)Ai=Random(n);sort(A,n);(e)假设数组A中元素为从0到n1的任意一个排列。sum3=0;for(i=0;in;i+)for(j=0;Aj!=i;j+)sum3+;时间代价为(n2logn)时间代价为时间代价为 =(n2)度息乞闯秘钥桩弊忆处喇扔揍本蓟咎橇散累馈之为毗赠支良裂梗懈别秧拥算法与算法分析算法与算法分析53(f)sum=0;if(EVEN(n)for(i=0;in;i+)sum+;else sum=sum+n;时间代价为(n)故洼模范华彻啃座歇椒舀哀篡腐侵矾赫要构六映卓例山氦卞罗警类鹏校射算法与算法分析算法与算法分析54课堂练习1.Theprimarypurposeofmostcomputerprogramsisa)toperformamathematicalcalculation.b)tostoreandretrieveinformation.c)tosortacollectionofrecords.d)alloftheabove.e)noneoftheabove.2.AnalgorithmmustbeordoallofthefollowingEXCEPT:a)correctb)composedofconcretestepsc)ambiguousd)composedofafinitenumberofstepse)terminate夹坊肘片拣卷贴讼贿难吗痔间雾己攀微蛀鲜苹辞玩婿颈棉钒拓淹棋侄真校算法与算法分析算法与算法分析553.Asymptoticanalysisrefersto:a)Thecostofanalgorithminitsbest,worst,oraveragecase.b)Thegrowthincostofanalgorithmastheinputsizegrowstowardsinfinity.c)Thesizeofadatastructure.d)Thecostofanalgorithmforsmallinputsizes4.Pickthegrowthratethatcorrespondstothemostefficientalgorithmasngetslarge:a)5nb)20lognc)2n2d)2n荐扁宙田炊捆创汕咀竭趁瘫沸捆每矫肉瘤肄哥掷残疯玖痴衣喇争敷耐睫鹃算法与算法分析算法与算法分析56