第一章算法概述精选PPT.ppt
第一章算法概述2023/4/17计算机算法设计与分析1第1页，本讲稿共22页2023/4/17计算机算法设计与分析2什么是算法？n简单的说，算法是指解决某一问题的运算序列n或者说算法是问题求解过程的运算描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止与指出问题对此输入数据无解。第2页，本讲稿共22页2023/4/17计算机算法设计与分析3算法的五个特性n确定性：每条指令的意义都是清晰的，无歧义的；n能行性：每条运算指令是能够实现的基本运算且能在有限时间内完成；n有穷性：每条指令的执行次数和执行时间都是有限的；如：不允许有诸如“x/0”或“x与1或2相加”之类的运算。因为前者结果不能确定，而后者不能确定两种可能的运算应该执行哪一个。n输入：有零个或多个输入；n输出：至少产生一个量作为输出。如：如果算法中的循环步长为零，运算进入无限循环，这是不允许的。如：两个实数相加是可行的；但两个实数相除，例如求2/3的值，在没有指明位数时需由无穷个十进制位表示，并不可行。第3页，本讲稿共22页2023/4/17计算机算法设计与分析4算法与过程n对任何合法输入，算法将在有限时间内通过有穷步计算后终止。n过程可以是有穷的，也可以是无穷的，不一定会终止。第4页，本讲稿共22页2023/4/17计算机算法设计与分析5算法与程序n程序是某个算法或过程在计算机上的一个具体的实现。n程序是依赖于程序设计语言的，甚至依赖于计算机结构的。n算法是脱离具体的计算机结构和程序设计语言的。第5页，本讲稿共22页2023/4/17计算机算法设计与分析6算法的复杂性n算法的复杂性是指算法运行时所需要的计算机资源的量多少，所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是：n时间复杂性：需要时间的资源量。n空间复杂性：需要空间的资源量。n这里人们通常更为关注的是时间复杂性。第6页，本讲稿共22页2023/4/17计算机算法设计与分析7决定算法复杂性的因素n算法的复杂性取决于n(1)求解问题的规模；n(2)具体的输入数据；n(3)算法本身的设计。n若令N、I、和A分别表示问题的规模、具体的输入和算法本身，则C=F(N,I,A)或C=FA(N,I)=F(N,I)第7页，本讲稿共22页2023/4/17计算机算法设计与分析8时间复杂性的计算n通常用算法执行的总语句（运算）的数量级决定算法的时间复杂度。n就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。n因此，算法的数量级直接决定算法的时间复杂度。第8页，本讲稿共22页2023/4/17计算机算法设计与分析9算法的数量级n观察以下程序段：(1)x=x+1;n若把程序段看成相应算法的主体，则：(1)语句执行频数为1，算法数量级为1；(2)for(k=1;k=n;k+)x=x+y;y=x+y;s=x+y;(2)每个赋值语句执行频数为n，算法数量级为3n；(3)for(t=1,k=1;k=n;k+)t=t*2;for(j=1;j=t;j+)s=s+j;(3)内循环的赋值语句执行频数为2+22+2n=2(2n-1)；时间复杂度为O(1);时间复杂度为O(n);取c=2，2(2n-1)2*2n;时间复杂度为O(2n);第9页，本讲稿共22页2023/4/17计算机算法设计与分析10最坏、最好或平均的情况n令：D为规模为N的合法输入的集合；I*表示在最坏情况下的输入；I#表示在最好情况下的输入；P(I)输入I出现的概率。nW(N)=maxIDT(N,I)=T(N,I*)nB(N)=minIDT(N,I)=T(N,I#)nA(N)=IDP(I)T(N,I)n三者中最常用的是W(N)。第10页，本讲稿共22页2023/4/17计算机算法设计与分析11复杂性分析的简化n在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。n例如，当n比较大时，计算机对n2和n2+2n的响应速度几乎没有什么区别，可直接认为二者复杂度均为n2。n在分析算法时，隐藏细节的数学表示法称为大写O记法。第11页，本讲稿共22页2023/4/17计算机算法设计与分析12上界标记n设f(N)、g(N)都是定义在正整数集上的函数。n上界记号O：如果存在正的常数C和自然数N0，使得当NN0时有|f(N)|C|g(N)|，则f(N)有上界函数g(N)，记为f(N)=O(g(N)。即当n足够大时，算法的实际运行时间不会超过g(n)的某个常数倍时间。例如第12页，本讲稿共22页2023/4/17计算机算法设计与分析13常见时间复杂度函数关系n多项式算法时间：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)n约定logn表示以2为底的对数。指数时间算法时间：O(2n)O(n!)1时，其余结点可分为m(0)个互不相交的有限集T1，T2，Tm，其中每个集合本身又是一棵树，并且称为根的子树。n3、图、图一个图G是一个有序三元组，G=(V，E，)，其中：（1）V是非空顶点集合；（2）E是边集合，EV=；（3）是E到uv|u，vV的映射，称为关联函数。第17页，本讲稿共22页2023/4/17计算机算法设计与分析18伪代码n程序员常常被要求以一种常人能够读懂的方式描述算法。n这样的描述不是计算机程序，但比通常的描述更结构化。n它们还便于对数据结构和算法执行高级分析。n这样的描述称为伪代码。第18页，本讲稿共22页2023/4/17计算机算法设计与分析19例如：n从键盘输入整数n，按C语言的键盘输入函数应写为：scanf(“%d”,&n);可简写为：scanf(n)或输入整数n。n要输出整数量a(1),a(2),a(n)，按C语言的输出函数应写为：for(k=1;k=n;k+)printf(“%d”,ak);可简写为：printf(a1an)或输出a(1n)第19页，本讲稿共22页2023/4/17计算机算法设计与分析20伪代码实例n数组最大值问题：在存储n个整数的数组A中找出最大元素。n算法arrayMax的伪代码描述如下：arrayMax(A,n)输入：存储输入：存储n1个整数的数组个整数的数组A 输出：输出：A中的最大元素中的最大元素 currentMaxA0 for i 1 to n-1 do if currentMaxAi currentMax Ai return currentMax 伪代码比等价的实际软件代码段更简洁，更容易理解和阅读。第20页，本讲稿共22页2023/4/17计算机算法设计与分析21什么是伪代码？n伪代码是自然语言和高级程序设计语言的混合物，它描述数据结构或算法的一般实现的主要实现。n然而，由于伪代码依赖于自然语言，因为实际上伪代码语言没有精确的定义。n编写伪代码时，切忌是为读者而不是为计算机编写的。因此，应力图传达一些高级思想，而不是低级的实现细节。同时，对于重要步骤，不能一笔带过。n就像人类的许多交流形式，找到合适的平衡是一项重要的技能，大家可以通过实践逐步改进。第21页，本讲稿共22页2023/4/17计算机算法设计与分析22作业：n书上第一章习题1,2,3,5,6,8,9n求以下算法的时间复杂度(1)m=0;for(k=1;k=1;j-)m=m+j;(2)t=1;m=0;for(k=1;k=n;k+)t=t*k;for(j=1;j=k*t;j+)m=m+;第22页，本讲稿共22页
