算法设计基本方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计基本方法（1）,列举法(穷举法):,指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。,例：百鸡问题（教材p6）,特点：算法简单，可读性强，直观易于理解和设计,适用范围：解决“是否存在”或者“有多少种可能”问题,缺点：运算工作量巨大,改进方法：分析实际问题，缩小列举范围以减少运算量,软肋：不能用以解决列举量无限的问题,或列举量非常大的问题,算法设计基本方法（2）,归纳法：,通过分析少量特殊情况，找出关系，得到结论,例：搏彩问题,这期彩票该买几呢？,第一期,3,十一,2,二,5,十二,1,三,6,十三,1,四,8,十四,0,五,9,十五,2,六,8,十六,2,七,7,十七,3,八,5,十八,4,九,5,十九,4,十,3,二十,4,根据曲线，买5比较好,归纳法,特点：适用面广，高效使用，常能解决许多实际问题,适用范围：样本空间有一定规律，多用于预测领域，数据难以获得的工程计算科学计算等领域,缺点：归纳出的数学模型需要证明，且代码实现不规范,改进方法：常采用不同归纳方法共同求解一个问题,软肋：不能求解样本空间过于零散的问题,算法设计基本方法（3）,递推,从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果,特点：采用递推关系式数学模型，理论正确性得到保证，由于递推关系式来源于归纳，所以本质上属于归纳法,适用范围：数值计算等工程应用,缺点：需考虑数值计算中稳定性问题，易产生蝴蝶效应,软肋：无递推关系式的问题不可解,NY,BJ,递推,据说，美军 1910 年的一次部队的命令传递是这样的:,营长对值班军官:明晚大约 8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔 76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。,值班军官对连长:根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。,连长对排长:根据营长的命令，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。,排长对班长:明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔 76年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。,班长对士兵:在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。,例：,计算,公式一：,记为,则初始误差,?,?,?!,!,What happened?!,注意此公式,精确,成立,考察第,n,步的误差,我们有责任改变。,造成这种情况的是,不稳定的算法,/*unstable algorithm*/,迅速积累，误差呈递增走势,可见初始的小扰动,公式二：,注意此公式与公式一,在理论上,等价,。,方法：先估计一个,I,N,再反推要求的,I,n,(,n,N,),。,可取,取,We just got lucky?,考察反推一步的误差：,以此类推，对,n,0),for(i=1;i 0),return n*factorial(n,1);,else,return 1;,例:斐波那契(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;,递归,特点：结构清晰，可读性强，容易用数学归纳法证明算法正确性,适用范围：难以用循环或递推直观描述的复杂问题,缺点：资源耗费多，执行效率低，所以在算法优化时采用消递归策略,算法设计基本方法（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|，则重复上述的减半过程。,例 二分检索,二分检索：每次选取,中间元素,的下标,算法 二分检索,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)，n,1,判断x是否出现。,若是，返回当前角标,mid,若非，返回0，表示没有找到,例：设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,找不到,找到,找到,成功,的检索,不成功,的检索,成功,的检索,递推减半技术,特点：迅速缩小计算规模,适用范围：工程计算，矩阵计算，数值计算中能够迅速将问题分治的情况,算法设计基本方法（6）,回溯法,通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。,例：八皇后问题（教材p15）迷宫问题,实际上是一种图的深度优先遍历的方法,特点：算法效率高，直观清楚,适用范围：适用于解决“是否存在”或者“有多少种可能”问题,缺点：算法的复杂性与计算顺序有关,算法分析,1.分析算法的目的,在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。,算法分析是计算机领域的“古老”而“前沿”的课题。,算法分析,“好”的算法应当达到以下指标,正确性(Correctness):算法应当满足具体问题的需求,可读性(Readability):算法是连接数学模型和程序的桥梁,可读性好有助于人对算法的理解,健壮性(Robustness):算法对于异常情况有充分的考虑和处理方法,效率高和存储量少:,时间复杂度:,指执行算法所需要的计算工作量 算法的工作量f(n),空间复杂度:,执行算法所需要的内存空间,n指算法规模,时间复杂度(1),平均性态(average behavior):,用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量,最坏情况复杂性(WorstCase Complexity),规模在n时,算法所执行的基本运算的最大次数,由于最坏情况复杂性给出算法工作量的一个上界,所以更具实用价值,时间复杂度(2),例:顺序搜索法的时间复杂度分析(教材p17),采用顺序搜索法，在长度为n的一维数组中查找为x的元素。,算法:即从数组的第一个元素开始，逐个与被查值x进行比较。,基本运算:x与数组元素的比较。,平均性态分析:,最坏情况分析:,W(n)maxti|1in1n,如何进行算法分析？,对算法进行全面分析，可分两个阶段进行：,事前分析,：求算法的一个,时间/空间限界函数,，即通过对算,法的“理论”分析，得出关于算法,时间和空间,特性,的特征函数（,、,）,与计算机物理软硬,件没有直接关系。,事后测试,：将算法编制成程序后实际放到计算机上运行，,收集其执行时间和空间占用等统计资料，进行,分析判断直接与物理实现有关。,1）事前分析,目的：试图得出关于算法特性的一种形式描,述（限界函数），以“理论上”衡量算法的“好坏”。,如何给出反映算法特性的描述,？,统计算法中各种运算的执行情况，包括：,引用了哪些运算,每种运算被执行的次数,该种运算执行一次所花费的时间等。,算法的执行时间,=,f,i,*,t,i,工作量,工作量,：算法中,语句,或,运算,的执行次数。,例：,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,次,限界函数的表示,就,计算时间,而言，事前分析阶段求得算法在工作量,上的算法规模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）事后测试,目的：运行程序，统计执行实际耗费的准确的时间与空间，与事前分析的结论进行比较，验证先前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。,分析手段：作时、空性能分布图,计算时间的渐近表示,记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n),其中，,n,是输入或输出规模的某种测度。,f(n),表示算法的“实际”执行时间,与机器及语言有关,。,g(n),是事前分析的结果一个,形式简单,的函数，如n,m,，logn，2,n,，n!等。是与工作量有关、而,与机器及语言无,关,的函数。,以下给出算法执行时间：,上界,（,）、,下界,（,）、,“平均”,（）的定义。,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)。,数量级,衡量,工作量,的“,大小,”的一种测度，通过f(n)的上界函数g(n)确定,语句的数量级,：语句的执行次数,例：1，n，n,2,算法的数量级,：算法所包含的所有语句的执行次数之和。,数量级反映了算法复杂度的最本质的特征。,例：假如求解同一个问题的三个算法分别具有n，n,2,，n,3,数量级。次数,若n=10，则可能的执行时间将分别是10，100，1000个单位时间与环境因素无关。,计算时间的,数量级的大小对算法有,决定性,的影响,例：假设解决同一个问题的两个算法，它们都有n个输入,计算时间的数量级分别是n,2,和nlogn。则，,n=1024：分别需要,1048576,和,10240,次运算。,n=2048：分别需要,4194304,和,22528,次运算。,分析：,同等规模下的计算量比较：,规模增大情况下的比较：在n加倍的情况下，一个,(n,2,)的算法计算时间增长,4,倍，而一个,(nlogn)算法则只用,两,倍多一点的时间即可完成。,多项式时间算法,和,指数时间算法,多项式时间算法,：可用多项式（函数