《数据结构课件ppt第一章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件ppt第一章.ppt（51页珍藏版）》请在三一办公上搜索。
1、1.3 算法和算法的衡量,二、算法,三、算法设计的原则,四、算法效率的衡量方法和准则,五、算法的存储空间需求,一、算法描述的工具,一、算法描述的工具,1.算法、语言和程序的关系(1)算法：对特定问题求解步骤的一种描述，是指令的有限序列。(2)描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。自然语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构，而高级程序语言则较为准确但又比较严谨。(3)程序是算法在计算机中的实现（与所用计算机及所用语言有关）。,2.设计实现算法过程的步骤 找出与求解有关的数据元素之间的关系（建立结构关系）。确定在某一数据对象上所施加的运算。考虑数据元
2、素的存储表示。选择描述算法的语言。设计实现求解的算法，并用程序语言加以描述。,(1)预定义常量和类型。本书中用到以下常量符号，如True、False、MAXSIZE等，约定用如下宏定义预先定义：define TRUE 1 define FALSE 0 define MAXSIZE 100 define OK 1 define ERROR 0,3.类描述算法的语言选择,(2)本书中所有的算法都以如下的函数形式加以表示，其中的结构类型使用前面已有的定义。函数类型 函数名（形式参数及说明）内部数据说明；执行语句组；/*函数名*/函数的定义主要由函数名和函数体组成，函数体用花括号“”和“”括起来。函数
3、中用方括号括起来的部分如“形式参数”为可选项，函数名之后的圆括号不可省略。,(3)赋值语句。简单赋值;（1）变量名=表达式，它表示将表达式的值赋给左边的变量；（2）变量+，它表示变量加1后赋值给变量；（3）变量-，它表示变量减1后赋值给变量。串联赋值#;变量1=变量2=变量3=变量k=表达式；成组赋值#;（变量1，变量2，变量3，,变量k)=（表达式1，表达式2，表达式3，,表达式k）；,数组名1下标1下标2=数组名2下标1下标2；条件赋值;变量名=条件表达式？表达式1:表达式2；(4)条件选择语句。if（表达式）语句；if（表达式）语句1；else 语句2；,switch(）case 判断值
4、1:语句组 1；break;case 判断值2:语句组 2；break;.case 判断值n:语句组n;break;default:语句组；break;,(5)循环语句。for 语句 for(；）循环体语句；首先计算表达式1的值，然后求表达式2的值，若结果非零（即为真）则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为零（即不成立为假）时为止。,while 语句 while(）循环体语句；while循环首先计算条件表达式的值，若条件表达式的值非零（即条件成立），则执行循环体语句，然后再次计算条件表达式的值，重复执行，直到条件表达式的值为零（即为假）时退出循环，执行该循环之后的语
5、句。,do-while 语句 do 循环体语句 while(）该循环语句首先执行循环体语句,然后计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。,(6)输入、输出语句。输入语句：用函数scanf实现；特别当数据为单个字符时，用getchar函数实现；当数据为字符串时，用gets函数实现。输出语句：用printf函数实现；当要输出单个字符时，用putchar函数实现；当数据为字符串时，用puts函数实现。其中输入输出函数中的类型部分不做严格要求，淡化表述。,(7)其它一些语句。return 或return：用于函数结束
6、。break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。continue语句：可用在循环语句中结束本次循环过程，进入下一次循环过程。exit语句：表示出现异常情况时，控制退出函数。,(8)注释形式。/*字符串*/注释句的作用是增强算法的可阅读性，在算法描述中要求在函数首部加上对算法功能的必要注释描述。加注释说明时如果没有涉及到的参量一定是多余的，而涉及到的内容应当作为参量，这实际上是程序设计中的一个素质要求，希望多加注意。,(9)一些基本的函数，例如：max函数：用于求一个或几个表达式中的最大值；min函数：用于求一个或几个表达式中的最小值；abs函数：用于求表达式的绝对值
7、；eof函数：用于判定文件是否结束；eoln函数：用于判断文本行是否结束。,算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：,1有穷性 2确定性 3可行性4有输入 5有输出,二、算法,1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。,2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，含义明确，无二义性。使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,4有
8、输入 有零个或多个输入量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,5有输出 至少产生一个输出或一个有意义操作。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,三、算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2.可读性,3健壮性,4高效率与低存储量需求,1正确性,首先，算法应当确切地满足具体问题的需要，这是算法设计的基本目标。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,c程序对于精心选择的、典型
9、、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,2可读性,算法是为了方便人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。,3健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,4高效率与低存储量需求,通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。
10、,算法的分析,1.算法的分析是研究和比较各种算法的性能和优劣。2.算法的时间性能和空间性能是算法分析的两个主要方面，分别称为：3.其目的主要是考察算法的时间和空间效率，以求改进算法对不同算法进行比较。,1.时间复杂度T(n)2.空间复杂度S(n),四、算法效率的衡量方法和准则,算法效率是指算法执行时间，通常有两种衡量算法效率的方法:,事后统计法,缺点：1必须执行程序 2其它因素掩盖算法本质,和算法执行时间相关的因素：,1算法选用的策略,2问题的规模,3编写程序的语言,4编译程序产生的机器代码的质量,5计算机执行指令的速度,事前分析估算法,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（
11、通常用整数量n表示），或者说，它是问题规模的函数。,称T(n)为算法的(渐近)时间复杂度。,T(n)=O(f(n),假如，随着问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，记作：,T(n)=O(f(n)中，“O”的文字含义是T(n)的量级。定义：T(n)=O(f(n)当且仅当存在正常数c和n0，对所有的n（n=n0）满足 T(n)=c.f(n)换句话说，O(f(n)给出了函数 f(n)的上限。上述定义是当问题的规模趋向无穷大时，T(n)的数量级称为时间复杂度。,如何估算算法的时间复杂度？,算法=控制结构+原操作（固有数据类型的操作）,算法的执行时间=原操作(i)的执行次数原操作
12、(i)的执行时间,算法的执行时间和原操作的执行次数之和成正比,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法的时间度量，定义为算法的时间复杂度。,语句的频度：该语句重复执行的次数。,原操作的基本操作：重复执行次数和算法的执行时间成正比的原操作。把求解问题的关键操作，如加法、减法和比较的运算指定为基本操作。多数情况下是最深层循环内的语句。,时间复杂度分析法规,执行一条读写或赋值语句用o(1)时间。依次执行一系列语句所用时间采用求和准则。判断语句的耗时主要是执行语句所用的时间，检验条件还需o(1)。循环语句的运行时间为多次迭代中执行循环体
13、以及检验循环条件的耗时，常用乘法准则。,例一两个矩阵相乘,void mult(int a,int b,int/*基本语句2*/for/mult,基本操作：乘法操作,解：设基本语句的执行次数为f(n),有 f(n)=n2+n3因为程序段的时间复杂度 T(n)=f(n)=n2+n3=c*n3=O(n3),其中c为常数，所以该程序段的时间复杂度为O(n3)。由此可看出，选择f(n)表达式中增长最快的项作为T(n)的量级。,例二起泡排序,void bubble_sort(int-i)/bubble_sort,基本操作:赋值操作,时间复杂度:O(n2),change=FALSE;/change 为元素进
14、行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟起泡,这个算法的时间复杂度随待排序数据的不同而不同，当某次排序过程中没有任何两个数组元素交换位置，则表明数组元素已排序完毕，此时算法将因标记change=FALSE不满足循环条件而结束。但是在最坏情况下，每次排序过程中至少有两个数组元素交换位置，因此，应该按最坏情况计算该算法的时间复杂度。设基本语句的执行次数为f(n),最坏情况下有 f(n)=n-2+n(n-1)/2 取f(n)表达式中增长率最大的项n2。所以该程序段的时间复杂度为O(n2)。,数据结构中常用的时间复杂度频率计数有7个：O(1)常数型 O(
15、n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 按时间复杂度由小到大递增排列成下页图和表所示（当n充分大时）。不同数量级的时间复杂度的形状如图所示，表与图是同一问题的不同表示形式。一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法，而避免使用指数阶的算法。,数据结构中常用的时间复杂度频率计数,图 多种数量级的时间复杂度图示,五、算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。,S(n)=O(g(
16、n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间,3辅助变量所占空间,若输入数据所占空间只取决于问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。,若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,“数据结构”课程的学习特点,“数据结构”课程的教学目标是要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。人类解决问题思维方式可分为两大类：一类是推理
17、方式，凭借公理系统思维方法，从抽象公理体系出发，通过演绎、归纳、推理来求证结果，解决特定问题；另一类是算法方式，凭借算法构造思维方式，从具体操作规范入手，通过操作过程的构造和实施，解决特定问题。,1.熟悉各名词、术语的含义，掌握基本概念。,2.理解算法五个要素的确切含义。,本章学习要点,3.掌握计算语句频度和估算算法时间复杂度的方法。,课堂练习,1.下面关于算法的说法，正确的是（）算法最终必须由计算机程序实现为解决某问题的算法与为该问题编写的程序含义相同。算法的可行性是指指令不能有二义性。以上几个都是错误的。,答案：D,2.计算机中的算法是指解决某个问题的有限运算序列，它必须具备输入、输出、（
18、）等5个特性。可执行性、可移植性和可扩充性可执行性、有穷性和确定性确定性、有穷性和稳定性易读性、稳定性和确定性,答案：B,3.算法分析的目的是（）找出数据结构的合理性。研究算法中的输入和输出关系。分析算法的效率以求改进。分析算法的易懂性和文档性。算法分析的两个主要方面是（）空间复杂性和时间复杂性。正确性和简单性。可读性和文档性。数据复杂性和程序复杂性。,答案：C,A,程序段的时间复杂度为（）for(i=0;im;i+)for(j=0;jn;j+)Aij=i*j;,答案：O(m*n),课后练习,一、试说明下列计算过程是否是一个算法，并说明理由。1.开始；2.n1*/y=0;while(x=(y+1)*(y+1)y=y+1;三、名次解释1.抽象数据类型 2.算法的时间复杂度,
