第一章(2)算法设计基本方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计基本方法（1）,列举法(穷举法):,指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。,例：百鸡问题（教材p6）,特点：算法简单，可读性强，直观易于理解和设计,适用范围：解决“是否存在”或者“有多少种可能”问题,缺点：运算工作量巨大,改进方法：分析实际问题，缩小列举范围以减少运算量,软肋：不能用以解决列举量无限的问题,或列举量非常大的问题,浊程历函磁痰轿陨负烤鞋总揪旱终蛊迪昔纱扯沮穆砧惹滁绑誉竹辽倡衰酚第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法设计基本方法（2）,归纳法：,通过分析少量特殊情况，找出关系，得到结论,例：搏彩问题,这期彩票该买几呢？,第一期,3,十一,2,二,5,十二,1,三,6,十三,1,四,8,十四,0,五,9,十五,2,六,8,十六,2,七,7,十七,3,八,5,十八,4,九,5,十九,4,十,3,二十,4,根据曲线，买5比较好,悼仇挞小动殖容挖笋待泼沫坯脸待啪利港赎台二替遍轨涛令沾族宣茧瀑硬第一章(2)算法设计基本方法第一章(2)算法设计基本方法,归纳法,特点：适用面广，高效使用，常能解决许多实际问题,适用范围：样本空间有一定规律，多用于预测领域，数据难以获得的工程计算科学计算等领域,缺点：归纳出的数学模型需要证明，且代码实现不规范,改进方法：常采用不同归纳方法共同求解一个问题,软肋：不能求解样本空间过于零散的问题,溶无阔睁顶姓疏宠宿密其康兹锈脉闹囱登渍控乓鼠咳触釉戴垂婶拐庶挤练第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法设计基本方法（3）,递推,从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果,特点：采用递推关系式数学模型，理论正确性得到保证，由于递推关系式来源于归纳，所以本质上属于归纳法,适用范围：数值计算等工程应用,缺点：需考虑数值计算中稳定性问题，易产生蝴蝶效应,软肋：无递推关系式的问题不可解,NY,BJ,鸥庐舌惟乎长毖颜借绪胸吗臃妒云患成疆贮莱息纱顿义瞳稍姥六馅号目扼第一章(2)算法设计基本方法第一章(2)算法设计基本方法,递推,据说，美军 1910 年的一次部队的命令传递是这样的:,营长对值班军官: 明晚大约 8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔 76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。,值班军官对连长: 根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。,连长对排长: 根据营长的命令，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。,排长对班长: 明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔 76年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。,班长对士兵: 在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。,锗詹世莎舆凰浓房漓凌避严射拦入坦术忆晚迂斤氟侧抉附居畜杭咽霹漳譬第一章(2)算法设计基本方法第一章(2)算法设计基本方法,例：,计算,公式一：,记为,则初始误差,?,?,? !,! !,What happened?!,注意此公式精确成立,褥遮夺锹桔店崭思渴添玩抑啄搅蹋颂诣橇煞匹募鸽窟籽喳爪嚷刁张砷礁删第一章(2)算法设计基本方法第一章(2)算法设计基本方法,考察第,n,步的误差,我们有责任改变。,造成这种情况的是,不稳定的算法,/* unstable algorithm */,迅速积累，误差呈递增走势,可见初始的小扰动,公式二：,注意此公式与公式一,在理论上等价。,方法：先估计一个IN ,再反推要求的In ( n N )。,可取,证羡杆琴燥脸卖聋菊步涟岭芍蛹胡竖哗祝渝社惕升哩漾白敲几孰恰拜平晋第一章(2)算法设计基本方法第一章(2)算法设计基本方法,取,We just got lucky?,肺月悠齿越青盘皆往秽炯嗓链馏獭非拎宣段糙涅垄庶涵仕攒鞭囚因葬殖增第一章(2)算法设计基本方法第一章(2)算法设计基本方法,考察反推一步的误差：,以此类推，对 n 0 ), for ( i = 1; i 0 ),return n * factorial ( n 1 );,else,return 1;,膀篮挑陀样啡孝基羊歇绳矫屠斯射阿锥沮完炮痛肖缕伍额悠鹤尧钮拍诽垣第一章(2)算法设计基本方法第一章(2)算法设计基本方法,例:斐波那契(Fibonacci)序列：,F,0,= F,1,= 1,F,i,= F,i-1,+ F,i-2,（i1),算法 求斐波那契数,int F(n),/返回第n个斐波那契数/,int n;,if (nb /,if (b=0) return(a);,else return (GCD(b,a % b);,例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,痊订蒂颇宅顷祖达滦枷餐怯庶蓑服蕉耳栅坐撵喉北楔傻搞誉丝巩内腊遭幅第一章(2)算法设计基本方法第一章(2)算法设计基本方法,递归,特点：结构清晰，可读性强，容易用数学归纳法证明算法正确性,适用范围：难以用循环或递推直观描述的复杂问题,缺点：资源耗费多，执行效率低，所以在算法优化时采用消递归策略,园琳梳甫匠可督永趋稠雄吻纠翅汞拦汇淳殖次蕊拨甘讯荡虾京唤浚防扔胁第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法设计基本方法（5）,减半递推技术（分治法）,所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。,例：二分法求方程实根的减半递推过程（算法及程序见书p13）,首先取给定区间的中点c(ab)/2。,然后判断f(c)是否为0。,若f(c)0,则说明c即为所求的根，求解过程结束；,如果f(c)0,则根据以下原则将原区间减半：,若f(a)f(c)0，则取原区间的前半部分；,若f(b)f(c)0，则取原区间的后半部分。,最后判断减半后的区间长度是否已经很小：,若|ab|，则过程结束，取(ab)/2为根的近似值；,若|ab|，则重复上述的减半过程。,犀堤坟灸汹庚沏给灭钮井映理赠瓣咬榜酣寄闭讶络咏歪懈谚伴衍锅泵嗜荆第一章(2)算法设计基本方法第一章(2)算法设计基本方法,例 二分检索,二分检索：每次选取,中间元素,的下标,算法 二分检索,Int BINSRCH(int A,int n,int x),int low,high,mid;,low=,1;,high=,n;,while (low=high),mid =,if(xAmid),low =mid+1;,else,return mid;,return 0;,注：,给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。,若是，返回当前角标mid,若非，返回0，表示没有找到,姆避毫屯最毙扫仰柏周晕芯茅坷澄列铺馈符菠斤踢沉卜契膏交樱冷蛋制肯第一章(2)算法设计基本方法第一章(2)算法设计基本方法,例：设A(1:9)=(-15，-6，0，7，9，23，54，82，101),在A中检索x=101，-14，82。执行轨迹见下表1,表1 运行轨迹示例,x=101,x=-14,x=82,low,high,mid,low,high,mid,low,high,mid,1,9,5,1,9,5,1,9,5,6,9,7,1,4,2,6,9,7,8,9,8,1,1,1,8,9,8,9,9,9,2,1,找不到,找到,找到,成功的检索,不成功的检索,成功的检索,劣瞻署挺坯户萎府杯铣鸿逗悄翘絮产露拐旷其栋瞪绊夯宁碉缺贯苦墙汉观第一章(2)算法设计基本方法第一章(2)算法设计基本方法,递推减半技术,特点：迅速缩小计算规模,适用范围：工程计算，矩阵计算，数值计算中能够迅速将问题分治的情况,铜帚连全悬给谁极扯磋斋哺拜夷洁忧采拌舰广慑郑砌诈萨皇假驰蹭穗焊犀第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法设计基本方法（6）,回溯法,通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。,例：八皇后问题（教材p15）迷宫问题,实际上是一种图的深度优先遍历的方法,特点：算法效率高，直观清楚,适用范围：适用于解决“是否存在”或者“有多少种可能”问题,缺点：算法的复杂性与计算顺序有关,畴腋凑惜着档钉双碎吻刻此脚粟妓僚诸珠扁支荡迈皿拢弊聪妹哇巳枣野陀第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法分析,1. 分析算法的目的,在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。,算法分析是计算机领域的“古老”而“前沿”的课题。,下龋雪盐紫构寥特教释忱棚天哪坡又嫂克沦楷仪氨滁酞语惺变阉验激铺咱第一章(2)算法设计基本方法第一章(2)算法设计基本方法,算法分析,“好”的算法应当达到以下指标,正确性(Correctness):算法应当满足具体问题的需求,可读性(Readability):算法是连接数学模型和程序的桥梁,可读性好有助于人对算法的理解,健壮性(Robustness):算法对于异常情况有充分的考虑和处理方法,效率高和存储量少:,时间复杂度:,指执行算法所需要的计算工作量 算法的工作量f(n),空间复杂度:,执行算法所需要的内存空间,n指算法规模,昼豪初楚嗅翰按资锗奇菌幼忱驰隙庚瞒斟拳债莫隧丛任潦胁恰发裔圭刑钢第一章(2)算法设计基本方法第一章(2)算法设计基本方法,时间复杂度(1),平均性态(average behavior):,用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量,最坏情况复杂性 (WorstCase Complexity),规模在n时,算法所执行的基本运算的最大次数,由于最坏情况复杂性给出算法工作量的一个上界,所以更具实用价值,煤泰焊异蜕垢酣掠唾仿愧克枉银映讥荧金蜒赋恰卤硒侮糕暗获端庸韭亏杂第一章(2)算法设计基本方法第一章(2)算法设计基本方法,时间复杂度(2),例:顺序搜索法的时间复杂度分析(教材p17),采用顺序搜索法，在长度为n的一维数组中查找为x的元素。,算法:即从数组的第一个元素开始，逐个与被查值x进行比较。,基本运算:x与数组元素的比较。,床井哇檀魁吻拼遂订滩丢韦煮种恶羞出沧琴辟组呀虫余钦坊镐尽谰夫虱币第一章(2)算法设计基本方法第一章(2)算法设计基本方法,平均性态分析:,最坏情况分析:,W(n)maxti | 1in1n,东嫁丢刚铂访禾斩坠字视履纽豆涟振谓谍蓝磐桔俯摹旺菌优凳臆束穿整吊第一章(2)算法设计基本方法第一章(2)算法设计基本方法,如何进行算法分析？,对算法进行全面分析，可分两个阶段进行：,事前分析,：求算法的一个,时间/空间限界函数,，即通过对算,法的“理论”分析，得出关于算法,时间和空间,特性,的特征函数（,、,）,与计算机物理软硬,件没有直接关系。,事后测试,：将算法编制成程序后实际放到计算机上运行，,收集其执行时间和空间占用等统计资料，进行,分析判断直接与物理实现有关。,殖辐狭厘津拔场楔挟抒琅良寄痕狐坠芹碰殖肃兜雪坟朝裕幌舞阶析热酬旅第一章(2)算法设计基本方法第一章(2)算法设计基本方法,1）事前分析,目的：试图得出关于算法特性的一种形式描,述（限界函数），以“理论上”衡量算法的“好坏”。,如何给出反映算法特性的描述,？,统计算法中各种运算的执行情况，包括：,引用了哪些运算,每种运算被执行的次数,该种运算执行一次所花费的时间等。,算法的执行时间,=,f,i,*,t,i,渔油迈促慢挪屏村华谭宋蔑畸掸呛桥吞甘疼刷遭彪腐扒象谍卜似功废韦安第一章(2)算法设计基本方法第一章(2)算法设计基本方法,工作量,工作量,：算法中,语句,或,运算,的执行次数。,例：,x,=x+y for (i=0,;in;i+),for (i=0,;in;i+),x = x + y for (j=0,;jn;j+),x = x +y,(a) (b) (c),分析：,(a)：,x=,x+y执行了1次,(b)：,x,=x+y执行了n次,(c)：,x,=x+y执行了n,2,次,刊联颠斑棱箭零痊斟恒第夹戊忿链后笋捆迢涵彝颇糟钟璃牛谓查样嚼履勾第一章(2)算法设计基本方法第一章(2)算法设计基本方法,限界函数的表示,就,计算时间,而言，事前分析阶段求得算法在工作量,上的算法规模n的,函数,称为限界函数，记为： g(n),限界函数以算法中主要运算单元为基本运算统计运算次数的,数量级,g(n)的一般形式：关于n的简单函数式,g(n)用以限界，因此只采用所得到计算次数的最高次项表示：随着n（规模）的增大，多项式函数式的,最高次,项的变化能够最显著的反映整个多项式的变化,不同的算法，g(n)的具体形式是不同的，常用的限界函数有：,1；logn；n；nlogn；n,2,；n,3,；,n,m,；2,n,；n！；n,n,等,了回颊溃颅堰冰铅堰嘎识茨宪搁区饰姑仗烂贵恃栖缕王胶渺遏糯谨相捷乱第一章(2)算法设计基本方法第一章(2)算法设计基本方法,2）事后测试,目的：运行程序，统计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。,分析手段：作时、空性能分布图,旅拎碍释亮水侍郧涌辆榴铰绣聪钦泞菠订芝拥娶宽非朋酌息府弛抱一鞍域第一章(2)算法设计基本方法第一章(2)算法设计基本方法,计算时间的渐近表示,记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n),其中，,n,是输入或输出规模的某种测度。,f(n),表示算法的“实际”执行时间,与机器及语言有关,。,g(n),是事前分析的结果一个,形式简单,的函数，如n,m,，logn，2,n,，n!等。是与工作量有关、而,与机器及语言无,关,的函数。,以下给出算法执行时间：,上界,（,）、,下界,（）、,“,平均,”,（ ）的定义。,朽耻伙琉赖巳卵肚贩貌涎绪衷蝉汾杆囱靶锦前著渠逻笛运抽抒臣影绥斡熟第一章(2)算法设计基本方法第一章(2)算法设计基本方法,1）上界函数,定义1 如果存在两个正常数c和n,0,，对于所有的n,n,0,，有,|f(n)| c|g(n)|,则记作,f(n) = (g(n),含义：,如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个,上界函数,。,f(n)的数量级就是g(n)。,试图求出,最小,的g(n)，使得f(n) = (g(n)。,胺见霓臣世桂造录烙租派锨冷砂革壳浑状静案倦蠢路鲸似蕉器回迈烹摈愁第一章(2)算法设计基本方法第一章(2)算法设计基本方法,数量级, 衡量,工作量,的“,大小,”的一种测度，通过f(n)的上界函数g(n)确定,语句的数量级,：语句的执行次数,例：1，n ，n,2,算法的数量级,：算法所包含的所有语句的执行次数之和。,数量级反映了算法复杂度的最本质的特征。,例：假如求解同一个问题的三个算法分别具有n， n,2,， n,3,数量级。次数,若n=10，则可能的执行时间将分别是10，100，1000个单位时间与环境因素无关。,劣郎凰托贤治若死蝇挚肆漠绦唉蛋活适虚茁哆法祸吭唇枯怯葱溪惫碗拎沮第一章(2)算法设计基本方法第一章(2)算法设计基本方法,计算时间的,数量级的大小对算法有,决定性,的影响,例：假设解决同一个问题的两个算法，它们都有n个输入,计算时间的数量级分别是n,2,和nlogn。则，,n=1024：分别需要,1048576,和,10240,次运算。,n=2048：分别需要,4194304,和,22528,次运算。,分析：,同等规模下的计算量比较：,规模增大情况下的比较：在n加倍的情况下，一个,(n,2,)的算法计算时间增长,4,倍，而一个(nlogn)算法则只用,两,倍多一点的时间即可完成。,疹骗懈斩佩惧妓詹秸马茂衣钠嗡啥顾碳枯史菏卢填旁弧致镣凉疥执热猛墙第一章(2)算法设计基本方法第一章(2)算法设计基本方法,多项式时间算法,和,指数时间算法,多项式时间算法,：可用多项式（函数）对其计算时间限界,的算法。,常见的多项式限界函数有：,(1) (logn) (n) (nlogn) (n,2,) (n,3,),指数时间算法,：计算时间用指数函数限界的算法,常见的指数时间限界函数：,(2,n,) (n！) (n,n,),说明：当n取值较大时，指数时间算法和多项式时间算法在计算时,间上非常悬殊。,镊阿布莫唬久拢宣磋眉乡咨众颂蕊铸徘价藕粥崖啡渣靳窟煎缀溺哉彩去绿第一章(2)算法设计基本方法第一章(2)算法设计基本方法,典型的计算时间函数曲线,材靴滩榴蓄寥亲毗诲阐哦追幼厅秆搽愉接祷勾顾园血读唉扼孜责咀冬盟杉第一章(2)算法设计基本方法第一章(2)算法设计基本方法,一般认识,当数据集的规模很大时，要在现有的计算机系统上运行,具有比,(nlogn),复杂度还高的算法是比较困难的。,指数时间算法只有在n取值,非常小时,才实用。,要想在顺序处理机上扩大所处理问题的规模，有效的途径,是,降低算法的计算复杂度,，而不是（仅仅依靠）提高计算,机的速度。,屋膨耿瑶民泰硷狸缆织静忻舷墩传屉熊莱沤逮腐凯巷庞纺汰梦兆巡叉一夷第一章(2)算法设计基本方法第一章(2)算法设计基本方法,计算时间函数值比较,3,跌秽脸公过粘相汽舟跨镭伎孙久鼓跌弧榜乞待第酉奇席泉戏袁籽鳃字羊殷第一章(2)算法设计基本方法第一章(2)算法设计基本方法,s = microsecond = 10,-6,seconds,ms = millisecond = 10,-3,seconds,sec = seconds,min = minutes yr = years,hr = hours,d = days,常见时间复杂度数量级分析（1）,平螟驯售邹峭祝蓖库起罪专促粤檀妨亮吴亡题型忽沟蔷卡尖怒裔记蟹航噪第一章(2)算法设计基本方法第一章(2)算法设计基本方法,常见时间复杂度数量级分析（2）,2,n,n,2,n,log,n,n,Log,n,f,n,豌禄赞偶这云廷辽郁护园兢潭菏缉蒂皂陡魏幼氯防胺颜姨锤软酥缴漆开纂第一章(2)算法设计基本方法第一章(2)算法设计基本方法,定义1.2 如果存在两个正常数c和n,0,，对于所有的n,n,0,，,有,|f(n)| c|g(n)|,则记作,f(n) = (g(n),含义：,如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个,下界函数,。,试图求出,“,最大,”,的g(n)，使得f(n) = (g(n)。,2）下界函数,选噪虽扩钠入添晰泊苇囚悲碧官友岛汀稍旋悯蒜拖牟秧罚袍存畸卒蔚渺羹第一章(2)算法设计基本方法第一章(2)算法设计基本方法,定义1.3 如果存在正常数,c,1,，,c,2,和n,0,，对于所有的n,n,0,，有,c,1,|g(n)| |f(n)| c,2,|g(n)|,则记作,含义：,算法在最好和最坏情况下的计算时间就一个,常数因子,范围内而言是相同的。可看作：,既有 f(n) = (g(n)，又有f(n) = (g(n),3）“平均情况”限界函数,豪层抖郸婉刘队神扇礼盅叠提僻构吏缅共船生游院寂鲜傣千苛辨阀姿失烟第一章(2)算法设计基本方法第一章(2)算法设计基本方法,空间复杂度,算法占用空间,算法程序空间,输入数据空间,算法执行的额外空间,由于算法执行空间是可以在算法设计中优化的，所以往往通过压缩等方法缩小这方面的空间占用,如果相对与程序规模，其执行的额外空间为常数级，则称算法为原地工作（in place）,拖苏埋矿浮慈社没芒酌懂云仕萄臂磺章扬统郴苗栗址祁哈太宾韶墙印刁邑第一章(2)算法设计基本方法第一章(2)算法设计基本方法,小结,算法:解题方案准确而完整的描述.是连接数学模型和程序的纽带.,算法性质:,能行性,确定性,有穷性,拥有足够信息,算法要素:,对数据的运算和操作,算法的控制结构,算法描述:算法描述语言中包含符号与表达式、赋值语句、控制转移语句、循环语句、输入输出终止等其他语句,算法设计方法：,列举法,归纳法,递推,递归,减半递推技术,回溯法,算法分析:,时间复杂度,平均性态,最坏情况复杂性,空间复杂度,算法程序空间,输入空间,算法执行的额外空间,时间复杂度种类(按优劣排)：,O(1),O(log2n),O(n),O(n2), O(n3),O(2n),尊掐锣翟窍奖萤递筏涝孰碱谈片弘晤美苫咕哑练吨缴斡刁哨冤什棋淮担浑第一章(2)算法设计基本方法第一章(2)算法设计基本方法,Homework,教材p19,习题1.1,1.2,妨塞近需脱亥济矣即油挥炭列轿瓷拍每员篱绕惮邵鹅技持湘策绒苫娘删删第一章(2)算法设计基本方法第一章(2)算法设计基本方法,