算法与算法分析PPT课件.ppt

《算法与算法分析PPT课件.ppt》由会员分享，可在线阅读，更多相关《算法与算法分析PPT课件.ppt（56页珍藏版）》请在三一文库上搜索。

1、第一章第一章 绪论绪论 1.1 1.1 引言引言 1.1.2 2 算法算法及算法分析（算法评价）及算法分析（算法评价）1什么是算法？算法是对解决问题的方法的一种精确描述。并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。因此，算法研究在某种意义上就是可行性研究。2算法的性质算法可以理解为动作序列的有限集合 仅有一个初始动作 每个动作的后继动作是确定的 算法的终止表示问题得到解答或问题没有解答 31 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成。2 2确定性确定性

2、 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有一在任何条件下，算法都只有一条执行路径。条执行路径。53 3可行性可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4 4有输入有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。6 5 5有输出有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。7算法设计的原则设

3、计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求81 1正确性正确性 首先，首先，算法应当满足满足以特定的“规格规格说明说明”方式给出的需求需求。其次，其次，对算法是否“正确正确”的的理解可以有以下四个层次四个层次：a a程序中不含语法错误；b b程序对于几组输入数据能够得出满足要求的结果；9 c c程序对于精心选择的、典型、苛刻且程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足带有刁难性的几组输入数据能够得出满足要求的结果；要求的结果；通常以第 c c 层意义的正确性作为衡量一个算法是否合格的标准。d

4、 d程序对于一切合法的输入数据都能得出满足要求的结果；102.可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行，因此算法应该易易于于人的理解理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。113健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出处理出错的方法错的方法不应是中断程序的执行，而应是返回返回一个表示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。124高效率与低存储量需求高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程

5、中所需的最大存储空间，两者都与问题的规模有关。13&第一章第一章 绪论绪论 1.1 1.1 引言引言 1.1.2 2 算法及算法及算法分析算法分析（算法评价）（算法评价）14算法分析与算法复杂度算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的复杂度分时间复杂度和空间复杂度。计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为 P类、NP类 和 NP-完全类。15算法的效率对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）1.设计一种容易理解、编码和调试的算法2.设计一种能

6、有效利用计算机资源的算法16算法的效率(cont)目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？17怎样比较两种算法解决问题的效率呢？实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法渐近算法分析(asymptotic algorithm analysis)，简称算法分析(algorithm analysis)可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法19“规模”与“基本操作”判断算法性能的一个基本考虑是处理一定“规模”(si

7、ze)的输入时该算法所需执行的“基本操作”(basic operation)数“规模”一般是指输入量的数目比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量20“规模”与“基本操作”（续）一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作：赋值运算简单算术运算简单布尔运算简单IO操作函数返回n个整数累加不是基本操作因为其代价依赖于n的值(即大小)21运行时间和增长率由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值算法的增长率(gro

8、wth rate)是指当输入规模增长时，算法代价的增长速率22最佳、最差和平均情况不是相同规模的所有输入的运行时间都相同顺序搜索法（Sequential search）从一个n元一维数组中找出一个给定的值K:从第一个元素开始，依次检索每一个元素，直到找到K为止最佳情况:最差情况:平均情况:23请用通俗的例子谈谈对增长率和平均情况 两个概念的理解请邮件告诉我（）24GrowthRateGraph255.1.1 时间复杂性（续）时间复杂性（续）更快的计算机，还是更快的算法?26时间复杂度对解题速度的影响O(n)解解 题题 速速 度度n=10n=30n=60n0.01 ms0.03 ms0.06 m

9、sn20.1 ms0.9 ms3.6 msn50.1 s24.3 s13.0 min2n1.0 ms17.9 min366.0 世纪世纪3n0.059 s6.5 年年1.31013 世纪世纪27u 阿达尔定律设 f 为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p 处理机的数目，Sp 为并行计算机系统最大的加速能力（单位：倍），则设 f=1%，p ，则Sp=100。串行计算与并行计算28算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的时间复杂度规模基本操作增长率平均情况效率请把下列的术语融入到上句中，请把下列的术语融入到

10、上句中，对算法分析的任务进行更加清晰的说明对算法分析的任务进行更加清晰的说明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-Ohnotation).Example:IfT(n)=3n2thenT(n)isinO(n2).希望最“紧”（即最小）的上限

11、虽然T(n)=3n2可以说它在O(n3)中,我们更喜欢用O(n2).31上限的例子例1:考虑找出整数数组中某个元素的顺序检索法(averagecost).如果访问并检查数组中的一个元素需要时间cs(cs为常数)，那么在平均情况下T(n)=csn/2。当n1时，csn/21，c1n2+c2n=c1n2+c2n2=(c1+c2)n2.因此取c=c1+c2andn0=1，有T(n)n0 时有T(n)=cg(n)，则称T(n)在集合(g(n)中意义:对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即nn0),该算法的完成至少需要cf(n)步.下限.34Big-OmegaExample例1

12、假定T(n)=c1n2+c2n.(c1，c20)则有 c1n2+c2n=c1n2foralln1.因此，取c=c1，n0=1，有T(n)=cn2.所以,根据定义,T(n)在(n2)中也可以说T(n)在(n)中我们希望找到一个最“紧”的可能限制.（最大下限）35ThetaNotation上限和下限描述了算法运行时间的范围当上、下限相等时，可以用表示法定义:如果非负函数T(n)既在O(h(n)中，又在(h(n)中，则称算法T(n)是(h(n)。这时也说T(n)与h(n)同阶36ACommonMisunderstanding“算法最佳情况是输入规模为1时，因为这时运行最快”。错误！大O指的是当n趋

13、近于时的增长率最佳情况指的是在规模为n的所有输入中哪个输入运行最快。37ACommonMisunderstanding混淆了最差情况和上限上限指的是增长率最差情况指的是给定规模的所有可能输入中最差的输入，消耗（运行）的时间最大38SimplifyingRules1.Iff(n)isinO(g(n)andg(n)isinO(h(n),thenf(n)isinO(h(n).2.Iff(n)isinO(kg(n)foranyconstantk0,thenf(n)isinO(g(n).3.Iff1(n)isinO(g1(n)andf2(n)isinO(g2(n),then(f1+f2)(n)isinO

14、max(g1(n),g2(n).4.Iff1(n)isinO(g1(n)andf2(n)isinO(g2(n)thenf1(n)f2(n)isinO(g1(n)g2(n).39程序运行时间的计算(1)Example1:a=b;Thisassignmenttakesconstanttime,soitis(1).Example2:sum=0;for(i=1;i=n;i+)sum+=n;时间代价为时间代价为(1)时间代价为时间代价为40程序运行时间的计算(2)Example3:sum=0;for(i=1;i=n;i+)for(j=1;j=i;j+)sum+;for(k=0;kn;k+)Ak=k;时

15、间代价为常量时间代价为常量c1时间代价为时间代价为c2n时间代价为时间代价为41程序运行时间的计算(3)Example4: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)Example5: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+;第一段程序的时间代价为第

16、一段程序的时间代价为(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语句最差情

17、况时间代价是then和else部分中时间代价较大的那一个对于平均情况代价也是如此假设n的取值与执行哪一条指令的概率无关switch语句最差情况时间代价是所有分支中开销最大的一个子程序调用加上执行子程序的时间44问题的分析问题代价的上限：已知最优算法的代价上限问题代价的下限：所有可能算法的代价下限（包括尚未设计出来的算法）45多参数问题ComputetherankorderingforallCpixelvaluesinapictureofPpixels.for(i=0;iC;i+)/Initialize count counti=0;for(i=0;iP;i+)/Look at all pixe

18、ls countvalue(i)+;/Increment countsort(count);/Sort pixel countsIfweusePasthemeasure,thentimeis(PlogP).Moreaccurateis(P+ClogC).46空间代价与分析时间代价类似与分析时间代价类似渐近分析中增长率的概念对于空间代价同样适渐近分析中增长率的概念对于空间代价同样适用用时间代价是相对于处理某个数据结构的算法而时间代价是相对于处理某个数据结构的算法而言的言的空间代价是相对于该数据结构本身而言的空间代价是相对于该数据结构本身而言的47空间/时间权衡原则(space/timetrade

19、offprinciple)以时间换空间以时间换空间信息压缩存储信息压缩存储以空间换时间以空间换时间查找表查找表基于磁盘的空间基于磁盘的空间/时间权衡原则时间权衡原则在磁盘上的存储代价越小，程序运行得越快在磁盘上的存储代价越小，程序运行得越快48小结算法分析的动机、基本符号和基本技术增长率的概念增长率的上限和下限的概念能够区分一种算法的代价和一个问题的代价49第一部分小结数据结构和算法效率代价和效益数据结构的定义；ADT算法分析动机：增长率基本符号：O、50什么情况下，可以直接用表示算法的复杂度？即什么情况下，算法的下限和上限相等。请邮件告诉我（）51习题讲解写出下列程序段平均情况下时间代价的表

20、示式。假设所有变量类型都为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;A

21、j!=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.The primary purpose of most computer programs is a)to perform a mathematical calculation.b)to store and retrieve information.c)to sort a collection of records.d)all of the abov

22、e.e)none of the above.2.An algorithm must be or do all of the following EXCEPT:a)correct b)composed of concrete steps c)ambiguous d)composed of a finite number of steps e)terminate553.Asymptotic analysis refers to:a)The cost of an algorithm in its best,worst,or average case.b)The growth in cost of an algorithm as the input size grows towards infinity.c)The size of a data structure.d)The cost of an algorithm for small input sizes4.Pick the growth rate that corresponds to the most efficient algorithm as n gets large:a)5nb)20 log nc)2n2d)2n56