算法与程序设计简介.ppt

《算法与程序设计简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法与程序设计概述1常用算法与程序设计主要内容1.1算法与算法描述算法定义算法描述1.2算法复杂性分析时间复杂度空间复杂度1.3程序设计简介算法与程序结构化程序设计2常用算法与程序设计1.1算法与算法描述1.1.1算法算法是程序设计的基础，是计算机科学的核心。算法是指解决某一问题的运算序列。或者说算法是问题求解过程的运算描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。3常用算法与程序设计3.算法是满足下列特性的指令序列：(1)确定性组成算法的每条指令是清晰的，无歧义的。(2)可行性算法中的运算是能够实现的基本运算，每一种运算可在有限

2、的时间内完成。(3)有穷性算法中每一条指令的执行次数有限，执行每条指令的时间有限。(4)输入一个算法有零个或多个输入。(5)输出一个算法至少产生一个量作为输出。4常用算法与程序设计4.选择算法的标准通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性。其次是算法所需要的存储空间少和执行时间短等。在实际工程中我们遇到许多高难度计算问题，有的问题在巨型计算机上用普通算法来求解可能要数个月的时间，而且很难找到精确解。但用一个好的算法，即使在普通的个人电脑上，可能只需数秒钟就可以求得解答。5常用算法与程序设计1.1.2算法描述1.描述算

3、法的方式算法是问题的程序化解决方案。一个问题可以设计不同的算法来求解，同一个算法可以采用不同的形式来表述。描述算法可以有多种方式，如自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。当一个算法使用计算机程序设计语言描述时，就是程序。本书采用C语言与自然自然语言相结合来描述算法。6常用算法与程序设计2.算法描述举例【例1.1】求两个整数a,b(a>b)的最大公约数的欧几里德算法:(1)a除以b得余数r;若r=0,则b为所求的最大公约数。(2)若r≠0,以b为a,r为b,继续(1)。注意到任两整数总存在最大公约数,上述辗转相除过程中余数逐

4、步变小,相除过程总会结束。欧几里德算法又称为“辗转相除”法，具体描述如下：7常用算法与程序设计输入正整数a,b;if(ab*/r=a%b;while(r!=0){a=b;b=r;/*实施"辗转相除"*/r=a%b;}printf(最大公约数b);8常用算法与程序设计算法复杂性的高低体现运行该算法所需计算机资源的多少。算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。计算机资源，最重要的是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源

5、的量称为空间复杂度。算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。1.2算法复杂性分析9常用算法与程序设计在分析算法时，隐藏细节的数学表示法成为大写O记法一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。1.2.1时间复杂度10常用算法与程序设计1.时间复杂度定义定义：对于一个数量级为的算法，如果存在两个

6、正常数c和m，对所有的n≥m，有则记作，称该算法具有用的运行时间，是指当n足够大时，该算法的实际运行时间不会超过的某个常数倍时间。11常用算法与程序设计2.例如程序段：for(k=1;k<=n;k++){x=x+y;y=x+y;s=x+y;}每个赋值语句执行频数为n，该算法的数量级为3n；其计算时间即时间复杂度为O(n)。12常用算法与程序设计3.例如程序段：for(t=1,k=1;k<=n;k++){t=t*2;for(j=1;j<=t;j++)s=s+j;}内循环赋值语句执行频数算法的时间复杂度为O()。13常用算法与程序设计4.算法时间关系：常见多

7、项式时间算法:常见指数时间算法:一般地，当n取值比较大时，在计算机上实现指数时间算法是不可能的，就是比时间复杂度高的多项式时间算法运行也很困难。14常用算法与程序设计5.两个定理定理1.1时间复杂度符号O有以下运算规则：O(f)+O(g)=O(max(f,g))(1.1)O(f)O(g)=O(fg)(1.2)定理1.2如果是n的m次多项式，则(1.3)15常用算法与程序设计【例1.3】估算下列程序段代表算法的时间复杂度。(1)t=1;m=0;for(k=1;k<=n;k++){t=t*2;for(j=t;j<=n;j++)m++;}时间复杂度为O(nlo

8、gn).16常用算法与程序设计(2)m=0;for(k=1;k<=n;k++)f