《算法与算法分析.ppt》由会员分享，可在线阅读，更多相关《算法与算法分析.ppt（56页珍藏版）》请在三一办公上搜索。
1、1,2,什么是算法？,算法是对解决问题的方法的一种精确描述。并非所有问题都有算法，有些问题经研究可行，则可能有相应算法；而有些问题经研究不可行，则没有相应算法。因此，算法研究在某种意义上就是可行性研究。,3,算法的性质,算法可以理解为动作序列的有限集合 仅有一个初始动作 每个动作的后继动作是确定的 算法的终止表示问题得到解答或问题没有解答,4,算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：,1有穷性 2确定性 3可行性4有输入 5有输出,算法的性质,5,1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完
2、成。,2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,6,3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,7,5有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,8,算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2.可读性
3、,3健壮性,4高效率与低存储量需求,9,1正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,10,c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,11,2.可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,12,3健壮性
4、,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,13,4高效率与低存储量需求,通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。,14,15,算法分析与算法复杂度,算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的复杂度分时间复杂度和空间复杂度。计算机理论科学中，按照计算复杂性研究问题求解的难易性，可把问题分为 P类、NP类 和 NP-完
5、全类。,16,算法的效率,对于一个问题通常有多种解法（算法），应该选择哪一种呢？计算机程序设计的核心有两个目标（有时它们互相冲突）设计一种容易理解、编码和调试的算法设计一种能有效利用计算机资源的算法,17,算法的效率(cont),目标1涉及到软件工程原理目标2涉及到数据结构与算法分析本课程主要讲的是与目标2有关的问题怎样度量算法的代价、效率呢？,18,如何度量效率?,实验比较（运行程序）渐近算法分析Asymptotic Algorithm Analysis关键资源:影响运行时间的因素:对很多算法而言，运行时间依赖与输入的规模执行算法所需要的时间T写成输入规模n的函数，记为T(n),19,怎样比
6、较两种算法解决问题的效率呢？,实验比较用源程序分别实现这两种算法，然后输入适当的数据运行，测算两个程序各自的开销这是一种事后统计的方法渐近算法分析(asymptotic algorithm analysis)，简称算法分析(algorithm analysis)可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销这是一种事前分析估算的方法,20,“规模”与“基本操作”,判断算法性能的一个基本考虑是处理一定“规模”(size)的输入时该算法所需执行的“基本操作”(basic operation)数“规模”一般是指输入量的数目比如，在排序问题中，问题的规模可以用被排序元素的个数来衡量,2
7、1,“规模”与“基本操作”（续）,一个“基本操作”必须具有这样的性质：完成该操作所需时间与操作数的具体取值无关在大多数高级语言中，下列操作是基本操作：赋值运算简单算术运算简单布尔运算简单IO操作函数返回n个整数累加不是基本操作因为其代价依赖于n的值(即大小),22,运行时间和增长率,由于影响运行时间的最主要因素一般是输入的规模，所以经常把执行算法所需要的时间T写成输入规模n的函数，记为T(n)我们总是假设T(n)为非负值算法的增长率(growth rate)是指当输入规模增长时，算法代价的增长速率,23,最佳、最差和平均情况,不是相同规模的所有输入的运行时间都相同顺序搜索法（Sequentia
8、l search）从一个n元一维数组中找出一个给定的值K:从第一个元素开始，依次检索每一个元素，直到找到K为止最佳情况:最差情况:平均情况:,24,请用通俗的例子谈谈对增长率和平均情况 两个概念的理解请邮件告诉我（）,25,Growth Rate Graph,26,5.1.1 时间复杂性（续）,更快的计算机，还是更快的算法?,27,时间复杂度对解题速度的影响,28,阿达尔定律设 f 为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p 处理机的数目，Sp 为并行计算机系统最大的加速能力（单位：倍），则设 f=1%，p，则Sp=100。,串行计算与并行计算,29,算法分析的任务是对
9、设计出的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性算法的时间复杂度规模基本操作增长率平均情况效率,请把下列的术语融入到上句中，对算法分析的任务进行更加清晰的说明,30,渐近分析:大O,定义:对于非负函数T(n)，若存在两个正常数c和n0，使得当nn0时有T(n)cf(n)，则称T(n)在集合O(f(n)中。用法:这个算法最佳、平均、最差情况（下的增长率的上限）在O(n2)中.含意:对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即 nn0),该算法总能在cf(n)步以内完成.,31,上限:大O(cont),增长率的上限用符号O表示，称为大O表示法(bi
10、g-Oh notation).Example:If T(n)=3n2 then T(n)is in O(n2).希望最“紧”（即最小）的上限:虽然 T(n)=3n2 可以说它在O(n3)中,我们更喜欢用O(n2).,32,上限的例子,例1:考虑找出整数数组中某个元素的顺序检索法(average cost).如果访问并检查数组中的一个元素需要时间cs(cs为常数)，那么在平均情况下T(n)=csn/2。当n 1时，csn/2=csn，所以根据定义，T(n)在O(n)中，n0=1，c=cs,33,上限的例子,例2:某一算法平均情况下 T(n)=c1n2+c2n.c1、c2为正数。当n 1，c1n2
11、+c2n=c1n2+c2n2=(c1+c2)n2.因此取c=c1+c2 and n0=1，有T(n)=cn2.所以根据定义,T(n)在is in O(n2)中.例子3:T(n)=c.我们说它在O(1)中.,34,Big-Omega,定义:对于非负函数T(n)，若存在两个正常数c和and n0，使得当n n0 时有T(n)=cg(n)，则称T(n)在集合(g(n)中意义:对于问题的所有最佳、平均、最差情况输入，只要输入规模足够大(即 nn0),该算法的完成至少需要cf(n)步.下限.,35,Big-Omega Example,例1：假定T(n)=c1n2+c2n.(c1，c20)则有 c1n2+
12、c2n=c1n2 for all n 1.因此，取c=c1，n0=1，有T(n)=cn2.所以,根据定义,T(n)在(n2)中 也可以说T(n)在(n)中我们希望找到一个最“紧”的可能限制.（最大下限）,36,Theta Notation,上限和下限描述了算法运行时间的范围当上、下限相等时，可以用表示法定义:如果非负函数T(n)既在O(h(n)中，又在(h(n)中，则称算法T(n)是(h(n)。这时也说T(n)与h(n)同阶,37,A Common Misunderstanding,“算法最佳情况是输入规模为1时，因为这时运行最快”。错误！大O指的是当n趋近于时的增长率最佳情况指的是在规模为n
13、的所有输入中哪个输入运行最快。,38,A Common Misunderstanding,混淆了最差情况和上限上限指的是增长率最差情况指的是给定规模的所有可能输入中最差的输入，消耗（运行）的时间最大,39,Simplifying Rules,If f(n)is in O(g(n)and g(n)is in O(h(n),then f(n)is in O(h(n).If f(n)is in O(kg(n)for any constant k 0,then f(n)is in O(g(n).If f1(n)is in O(g1(n)and f2(n)is in O(g2(n),then(f1+f2
14、)(n)is in O(max(g1(n),g2(n).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).,40,程序运行时间的计算(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),时间代价为,41,程序运行时间的计算(2),Example 3:sum=0;for(i=1;i=n;i+)for(j=1;j=i;j+)
15、sum+;for(k=0;kn;k+)Ak=k;,时间代价为常量c1,时间代价为c2n,时间代价为,42,程序运行时间的计算(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),43,程序运行时间的计算(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+;第
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),44,其他控制语句,while循环、do-while循环分析方法与for循环类似if语句最差情况时间代价是
17、then和else部分中时间代价较大的那一个对于平均情况代价也是如此假设n的取值与执行哪一条指令的概率无关switch语句最差情况时间代价是所有分支中开销最大的一个子程序调用加上执行子程序的时间,45,问题的分析,问题代价的上限：已知最优算法的代价上限问题代价的下限：所有可能算法的代价下限（包括尚未设计出来的算法）,46,多参数问题,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+)/Lo
18、ok 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).,47,空间代价,与分析时间代价类似渐近分析中增长率的概念对于空间代价同样适用时间代价是相对于处理某个数据结构的算法而言的空间代价是相对于该数据结构本身而言的,48,空间/时间权衡原则(space/time tradeoff principle),以时间换空间信息压缩存储以空间换时间查找表
19、基于磁盘的空间/时间权衡原则在磁盘上的存储代价越小，程序运行得越快,49,小结,算法分析的动机、基本符号和基本技术增长率的概念增长率的上限和下限的概念能够区分一种算法的代价和一个问题的代价,50,第一部分小结,数据结构和算法效率代价和效益数据结构的定义；ADT算法分析动机：增长率基本符号：O、,51,什么情况下，可以直接用表示算法的复杂度？即什么情况下，算法的下限和上限相等。请邮件告诉我（）,52,习题讲解,写出下列程序段平均情况下时间代价的表示式。假设所有变量类型都为int：a=b+c;d=a+e;(b)sum=0;for(i=0;i3;i+)for(j=0;jn;j+)sum+;(c)su
20、m=0;for(i=0;in*n;i+)sum+;,时间代价为(1),时间代价为(n),时间代价为(n2),53,(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),54,(f)sum=0;if(EVEN(n)for(i=0;in;i+)sum+;else sum
21、=sum+n;,时间代价为(n),55,课堂练习,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 above.e)none of the above.2.An algorithm must be or do all of the following EXCEPT:a)correct b)compos
22、ed of concrete steps c)ambiguous d)composed of a finite number of steps e)terminate,56,3.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)2n,
