第一章2算法设计基本方法优秀PPT.ppt

《第一章2算法设计基本方法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第一章2算法设计基本方法优秀PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计基本方法（算法设计基本方法（2）l归纳法：l通过分析少量特殊状况，找出关系，得到结论l例：搏彩问题这期彩票该买几呢？第一期3十一2二5十二1三 6十三1四8十四0五9十五2六8十六2七7十七3八5十八4九5十九4十3二十4依据曲线，买5比较好归纳法归纳法特点：适用面广，高效运用，常能解决很多实际问题适用范围：样本空间有确定规律，多用于预料领域，数据难以获得的工程计算科学计算等领域缺点：归纳出的数学模型须要证明，且代码实现不规范改进方法：常接受不同归纳方法共同求解一个问题软肋：不能求解样本空间过于零散的问题算法设计基本方法（算法设计基本方法（3）l递推l从已知的初始条件动身，逐次推出所要

2、求的各中间结果和最终结果l特点：接受递推关系式数学模型，理论正确性得到保证，由于递推关系式来源于归纳，所以本质上属于归纳法l适用范围：数值计算等工程应用l缺点：需考虑数值计算中稳定性问题，易产生蝴蝶效应l软肋：无递推关系式的问题不行解NYBJ递推递推据说，美军据说，美军 1910 年的一次部队的吩咐传递是这样的年的一次部队的吩咐传递是这样的:营长对值班军官营长对值班军官:明晚大约明晚大约 8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔 76年才年才能望见一次。吩咐全部士兵着野战服在操场上集合，我将向他们说明这一罕见的现象。假如能望见一

3、次。吩咐全部士兵着野战服在操场上集合，我将向他们说明这一罕见的现象。假如下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。值班军官对连长值班军官对连长:依据营长的吩咐，明晚依据营长的吩咐，明晚8点哈雷彗星将在操场上空出现。假如下雨的话，就让士点哈雷彗星将在操场上空出现。假如下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。连长对排长连长对排长:依据营长的吩咐，明晚依据营长的吩咐，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。假如操场点，非凡的哈雷彗星将身穿野战

4、服在礼堂中出现。假如操场上下雨，营长将下达另一个吩咐，这种吩咐每隔上下雨，营长将下达另一个吩咐，这种吩咐每隔76年才会出现一次。年才会出现一次。排长对班长排长对班长:明晚明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔点，营长将带着哈雷彗星在礼堂中出现，这是每隔 76年才有的事。假如下雨年才有的事。假如下雨的话，营长将吩咐彗星穿上野战服到操场上去。的话，营长将吩咐彗星穿上野战服到操场上去。班长对士兵班长对士兵:在明晚在明晚8点下雨的时候，著名的点下雨的时候，著名的76岁哈雷将军将在营长的陪伴下身着野战服，开着他岁哈雷将军将在营长的陪伴下身着野战服，开着他那那“彗星彗星”牌汽车，经过操场前往礼

5、堂。牌汽车，经过操场前往礼堂。例：例：计算计算 公式一：公式一：记为记为则初始误差则初始误差?!What happened?!留意此公式精留意此公式精确成立确成立考察第考察第n步的误差步的误差我们有责任改变。我们有责任改变。造成这种情况的是造成这种情况的是不稳定的算法不稳定的算法 /*unstable algorithm*/迅速积累，误差呈递增走势迅速积累，误差呈递增走势可见初始的小扰动可见初始的小扰动 公式二：公式二：留意此公式与公式一留意此公式与公式一在理论上等价。在理论上等价。方法：先估计一个方法：先估计一个IN,再反推要求的再反推要求的In(n N)。可取可取取取 We just go

6、t lucky?考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n 0)for(i=1;i 0)return n*factorial(n 1);else return 1;例:斐波那契(Fibonacci)序列：F0=F1=1 Fi=Fi-1+Fi-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;递归递归特点：结构清晰，可读性强，简洁用数学归纳法证明算法正确性适用范围：难

7、以用循环或递推直观描述的困难问题缺点：资源耗费多，执行效率低，所以在算法优化时接受消递归策略算法设计基本方法（算法设计基本方法（5）l减半递推技术（分治法）l所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。例：二分法求方程实根的减半递推过程（算法及程序见书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|

8、，则过程结束，取(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)，n1,推断x是否出现。若是，返回当前角标mid若非，返回0，表示没有找到例：设A(1:9)=(-15，-6，0，7，9，23，

9、54，82，101)在A中检索x=101，-14，82。执行轨迹见下表1表1 运行轨迹示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到找到成功的检索不成功的检索成功的检索递推减半技术递推减半技术特点：快速缩小计算规模适用范围：工程计算，矩阵计算，数值计算中能够快速将问题分治的状况算法设计基本方法（算法设计基本方法（6）l回溯法l通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步摸索，对于每一步的摸索，若摸索成功，就得到问题的解，若摸索失败，就逐步回退，换别的路途再进

10、行摸索。l例：八皇后问题（教材p15）迷宫问题l事实上是一种图的深度优先遍历的方法l特点：算法效率高，直观清晰l适用范围：适用于解决“是否存在”或者“有多少种可能”问题l缺点：算法的困难性与计算依次有关算法分析1.分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避开无益的人力和物力奢侈。算法分析是计算机领域的“古老”而“前沿”的课题。算法分析算法分析l“好”的算法应当达到以下指标l正确性(Correctness):算法应当满足具体问题的需求l可读性(Readability):算法是连接数学模型和程序的桥

11、梁,可读性好有助于人对算法的理解l健壮性(Robustness):算法对于异样状况有充分的考虑和处理方法l效率高和存储量少:l时间困难度:指执行算法所须要的计算工作量 算法的工作量f(n)l空间困难度:执行算法所须要的内存空间n指算法规模时间困难度时间困难度(1)l平均性态(average behavior):l用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量l最坏状况困难性(WorstCase Complexity)l规模在n时,算法所执行的基本运算的最大次数由于最坏状况困难性给出算法工作量的一个上界,所以更具好用价值时间困难度时间困难度(2)l例:依次搜寻法的时间困难度分析(教

12、材p17)l接受依次搜寻法，在长度为n的一维数组中查找为x的元素。l算法:即从数组的第一个元素起先，逐个与被查值x进行比较。l 基本运算:x与数组元素的比较。平均性态分析平均性态分析:最坏状况分析最坏状况分析:W(n)maxti|1in1n如何进行算法分析？对算法进行全面分析，可分两个阶段进行：事前分析：求算法的一个时间/空间限界函数，即通过对算 法的“理论”分析，得出关于算法时间和空间特性 的特征函数（、）与计算机物理软硬 件没有干脆关系。事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行 分析推断干脆与物理实现有关。1）事前分析目的：试图得出关于算法

13、特性的一种形式描 述（限界函数），以“理论上”衡量算法的“好坏”。如何给出反映算法特性的描述？统计算法中各种运算的执行状况，包括：引用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。算法的执行时间=fi*til工作量 工作量：算法中语句或运算的执行次数。例：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执行了n2次 l 限界函数的表示l 就计算时间而言，事前分析阶段求得算法在工作量l上的算法规模n的函数

14、称为限界函数，记为：g(n)l限界函数以算法中主要运算单元为基本运算统计运算次数的数量级l g(n)的一般形式：关于n的简洁函数式l g(n)用以限界，因此只接受所得到计算次数的最高次项表示：随着n（规模）的增大，多项式函数式的最高次项的变更能够最显著的反映整个多项式的变更l 不同的算法，g(n)的具体形式是不同的，常用的限界函数有：1；logn；n；nlogn；n2；n3；nm；2n；n！；nn等l 2）事后测试目的：运行程序，统计执行实际耗费的精确的时间与空间，与事前分析的结论进行比较，验证从前的分析结论包括正确性、执行性能等，比较、优化所设计的算法。分析手段：作时、空性能分布图计算时间的

15、渐近表示记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n)其中，n是输入或输出规模的某种测度。f(n)表示算法的“实际”执行时间与机器及语言有关。g(n)是事前分析的结果一个形式简洁的函数，如nm，logn，2n，n!等。是与工作量有关、而与机器及语言无 关的函数。以下给出算法执行时间：上界（）、下界（）、“平均”（）的定义。1）上界函数定义1 假如存在两个正常数c和n0，对于全部的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：假如算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界

16、函数。f(n)的数量级就是g(n)。试图求出最小的g(n)，使得f(n)=(g(n)。l数量级 l 衡量工作量的“大小”的一种测度，通过f(n)的上界函数g(n)确定l 语句的数量级：语句的执行次数l 例：1，n，n2l 算法的数量级：算法所包含的全部语句的执行次数之和。l 数量级反映了算法困难度的最本质的特征。l例：假如求解同一个问题的三个算法分别具有n，n2，n3数量级。次数l 若n=10，则可能的执行时间将分别是10，100，1000个单位时间与环境因素无关。计算时间的数量级的大小对算法有确定性的影响 例：假设解决同一个问题的两个算法，它们都有n个输入,计算时间的数量级分别是n2和nlo

17、gn。则，n=1024：分别须要1048576和10240次运算。n=2048：分别须要4194304和22528次运算。分析：同等规模下的计算量比较：规模增大状况下的比较：在n加倍的状况下，一个(n2)的算法计算时间增长4倍，而一个(nlogn)算法则只用两倍多一点的时间即可完成。多项式时间算法和指数时间算法多项式时间算法：可用多项式（函数）对其计算时间限界 的算法。常见的多项式限界函数有：(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：(2n)(n！)(nn)说明：当n取值较大时，指数时间算法和多项式时间算法在计算时

18、 间上特别悬殊。典型的计算时间函数曲线l一般相识l当数据集的规模很大时，要在现有的计算机系统上运行l 具有比(nlogn)困难度还高的算法是比较困难的。l指数时间算法只有在n取值特别小时才好用。l要想在依次处理机上扩大所处理问题的规模，有效的途径l 是降低算法的计算困难度，而不是（仅仅依靠）提高计算l 机的速度。计算时间函数值比较3 s=microsecond=10-6 secondsms=millisecond=10-3 secondssec=secondsmin=minutes yr=yearshr=hoursd=days常见时间困难度数量级分析（1）常见时间困难度数量级分析（常见时间困难

19、度数量级分析（2）2nn2n log nnLog nfn定义1.2 假如存在两个正常数c和n0，对于全部的nn0，有|f(n)|c|g(n)|则记作f(n)=(g(n)含义：假如算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。试图求出“最大”的g(n)，使得f(n)=(g(n)。2）下界函数定义1.3 假如存在正常数c1，c2和n0，对于全部的nn0，有 c1|g(n)|f(n)|c2|g(n)|则记作含义：算法在最好和最坏状况下的计算时间就一个常数因子范围内而言是相同的。可看作：既有 f(n)=(g(n

20、)，又有f(n)=(g(n)3）“平均状况”限界函数空间困难度空间困难度l算法占用空间l算法程序空间l输入数据空间l算法执行的额外空间由于算法执行空间是可以在算法设计中优化的，所以往往通过压缩等方法缩小这方面的空间占用假如相对与程序规模，其执行的额外空间为常数级，则称算法为原地工作（in place）小结小结l算法:解题方案精确而完整的描述.是连接数学模型和程序的纽带.l算法性质:l能行性l确定性l有穷性l拥有足够信息l算法要素:l对数据的运算和操作l算法的限制结构l算法描述:算法描述语言中包含符号与表达式、赋值语句、限制转移语句、循环语句、输入输出终止等其他语句l算法设计方法：l列举法l归纳法l递推l递归l减半递推技术l回溯法算法分析:时间困难度平均性态最坏状况困难性空间困难度算法程序空间输入空间算法执行的额外空间时间困难度种类(按优劣排)：O(1),O(log2n),O(n),O(n2),O(n3),O(2n)Homeworkl教材p19 l习题1.1,1.2