第1章-算法-zhang.ppt

1、授课内容,数据结构与算法基础 算法的基本概念 数据结构基础知识 ( 线性表, 栈和队列, 树与二叉树, 查找与排序 ) 数据库及其应用基础 数据库的基本知识 ( 基本概念, 数据模型, 关系代数 ) Access的使用 SQL语言 VBA程序设计 软件工程基础 软件工程基本知识 结构化分析方法与结构化设计方法 软件测试与程序调试,第1章 算法,1.1 算法的基本概念 1.2 算法复杂度及算法的描述方式,1.1 算法的基本概念,算法是指解题方案的准确而完整的描述。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内，运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。,1.1.

2、1 算法的基本特征 可行性： 算法描述的每个步骤必须能够实现，且能达到预期的目的； 确定性： 算法中的每一个步骤，必须经过明确的定义，对于相同的输入只能得出相同的输出； 有穷性： 算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止； 输入： 具有零个或多个输入。它们是算法开始前的初始量； 输出： 至少产生一个输出，是与输入有某种关系的量，是算法的执行结果。,1.1.2 算法的基本要素,(1) 算法中对数据对象的运算和操作 算术运算：加、减、乘、除 逻辑运算：“与”、“或”、“非” 关系运算：“大于”、“小于”、“等于”、“不等于” 数据传输：赋值、输入、输出等操作,算法的控制结

3、构 是算法的基本框架，不仅决定算法中各操作的执行顺序，也直接反映算法的设计是否符合结构化原则。 一个算法一般使用顺序、选择、循环三种基本控制 结构组合而成。,顺序结构举例,已知三个数a、b、c，设计一算法，求它们的和。 算法分析：第一步： 输入三个数a，b，c；第二步： 计算和S abc；第三步： 输出S的值，结束。,顺序结构是由若干个依次执行的操作步骤组成。是任何算法都离不开的基本主体结构。,条件结构举例,设计算法，求给定的方程ax2bxc0的根。 第一步: 输入二次项、一次项系数和常数项a、b、c。 第二步: 计算判别式的值pb24ac。 第三步: 判断：如果p0，则x1，x2； 否则，x

4、1，x2。 第四步: 输出方程的两个根x1、x2，结束。,条件结构是以条件的判断为起始点， 根据条件是否成立来决定执行哪一个处理步骤。,循环结构举例,循环结构指从某处开始有规律地反复执行某一处理步骤（称为循环体）。循环体的执行次数由一个控制循环条件决定，满足条件反复做，不满足则停止。,设计算法，求n个学生某门课程的平均成绩。 第一步: 输入学生总数n; 置i为1, 成绩总合sum为 0; 第二步: 输入第i个学生的分数 score； 第三步: sum sum + score；i i+1; 第四步: 当 i小于等于n 时，返至第二步； 第五步: average sum / n, 输出averag

5、e，结束。,1.2.1 算法的描述方式 (1) 程序设计语言算法 可直接在计算机上运行，使给定问题在有限时间内求解。 (2) 伪语言算法 不能直接在计算机上运行。伪语言介于程序设计语言和自然语言之间，它忽略程序设计语言中一些严格的语法规则和细节描述。突出算法设计的主要思想，而不是语法细节。 (3) 非形式算法 采用自然语言，同时还可使用程序设计语言或伪程序设计语言（如，流程控制语句while、for、if等）描述。,1.2 算法的描述方式及算法复杂度,除采用语言描述外，实际上还有一种图形 描述方法，如流程图、N-S图等。 不论算法采用什么方法描述，它最终都要 转换为程序才能在计算机上运行。 算

6、法程序 （程序要受到运行环境的限制， 需考虑许多与方法和分析无关的细节问题）,1.2.2 算法复杂度 (P.2) (1) 算法的时间复杂度 算法所求解问题规模n的函数。记为T(n) 一个算法的时间复杂度T(n)是指执行算法所需要的计算工作量。 算法的工作量一般用算法执行的基本运算次数度量，即问题规模。 (2) 算法的空间复杂度 执行这个算法所需要的内存空间。,一条语句在算法中被重复执行的次数，称 为该语句的频度。 T(n)= 每一条语句的频度之和 当问题规模n趋向无穷大，（即n ） T(n)/f(n) a时，称时间复杂度T(n)的数量级 为O(f(n) 。 其中，a是不等于零的常数，f(n)

7、表示与问题 规模n 有关的频度最大的语句的频度 时间复杂度T(n)的数量级称为算法的渐进时间 复杂度。O(f(n),算法的渐进时间复杂度,通常使用算法的渐近时间复杂度评价一个算法的时间性能。即， T(n)= O(f(n) 常见的渐近时间复杂度包括（递增排列）： 常数阶o(1)、 对数阶 、 线性阶o(n)、 线性对数阶 、平方阶 、 立方阶 、k次方阶 、指数阶 时间复杂度为指数阶 的算法效率极低，当n值稍大时就无法应用。,例1： for( i=0; in; i+ ) /* 执行n+1次 */ for( j=0; jn; j+ ) /* 执行n(n+1)次 */ cij=0; /* 执行n2

8、次 */ for( k=0; kn; k+ ) /* 执行n2(n+1)次 */ cij=cij+aik*bkj; /* 执行n3次 */ ,f(n)=n3 时间复杂度为 O(n3), 记为: T(n)=O(n3),时间复杂度在具体分析时，可做如下处理： 若语句很少执行，且与规模n无关，则可 忽略不计； 若所有语句（即使有上千条语句）都与规 模n无关，时间复杂度的量级也只是O(1)， 其执行时间不过是一个较大的常数。 一般只考虑与程序规模n有关的频度最大 的语句。（如，循环语句的循环体，多重 循环的内循环等。）,例2： （1）a=b; 时间复杂度为O(1) （2）for(i=0;in;i+) a=b; 时间复杂度为O(n) （3）for(int i=0;in;i+) for(int j=0;jn;j+) a=b; 时间复杂度为O(n2),例3： 说明下列程序段的时间复杂度 (1) 交换a和b的内容 t=a; a=b; b=t;,三条语句的执行次数均为1， 与规模n无关， 故可知:时间复杂度为O(1)。,执行次数最多的语句是sum+=i，但它执行的次数不是n次，若