运筹学（第二讲）.pptVIP

（第二讲） 绍兴文理学院 计算机系计算机应用教研室 TKS * 想构成常用汉字的所有名言佳句 * AAA BBBB 第1章 绪论(2)、第2章 线性表（1） 一、教学目的：明确算法的概念，明确算法分析的作用与分析的重点；初步掌握算法分析的方法；明确线性表的概念和抽象数据类型的定义，掌握线性表的顺序表示、结构定义和基本操作；初步掌握平均时间复杂度的分析方法；算法设计训练。 二、教学重点：算法的概念，算法分析的作用与分析的重点；算法分析的方法；线性表的概念，线性表的顺序表示、结构定义和基本操作；平均时间复杂度的分析方法；算法设计训练。 三、教学难点：算法分析的方法；线性表的基本操作；平均时间复杂度的分析方法；算法设计训练。 四、教学过程： AAA BBBB §1.4 算法和算法分析 §1.4.1 算法的定义及特性 算法(Algorithm)是对指定问题求得步骤的一种描述，是为了解决某类问题而规定的一个有限长的操作(指令)序列。 算法的五个重要特性： (1) 有穷性：算法必须是在执行有穷步之后结束，且每一步都可在有穷时间内完成。 (2) 确定性：算法中每一条指令必须有确切的含义，不会产生两义性。 (3) 可行性：描述的操作都可通过已经实现的基本运算执行有限次来完成 (4) 输入：有零个或多个输入。 (5) 输出：有一个或多个输出。 TKS * * AAA BBBB (1) 正确性。在合理的数据输入下，能够在有限运行时间内得到正确的结果。 (2) 可读性。容易读懂和理解。 (3) 健壮性。当输入数据非法时，算法能适当地作出适应过处理。 (4) 高效性。高效性包括时间和空间两个方面。 时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量； 空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。 时间复杂度和空间复杂度是衡量算法的两个主要指标。 ▲ 评价算法的估算方法 (1) 事后统计方法—利用计算机内部的计时功能。(不太采用) ?(2) 事前分析估算的方法。 §1.4.2 评价算法优劣的基本标准 TKS * * AAA BBBB §1.4.3 算法的时间复杂度 算法分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间性能上的比较，以便从中挑选出较优算法。 1、算法的执行时间和语句的频度 一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。 语句的频度(Frequency Count)：一条语句的重复执行次数。 △ 算法的执行时间=∑原操作(基本操作)的执行次数(频度)×原操作的执行时间 △ 设每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。 TKS * * AAA BBBB 例1.4 求两个n阶矩阵乘积算法的执行时间 ＃define n 自然数 MATRIXMLT(float a[n][n],float b[n][n],float c[n][n]) {int i,j,k; for(i=1;i=n;i++) for(j=1;j=n;j++) { c[i][j]=0; for(k=1;k=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； } } //n+1 //n(n+1) //n*n //n*n*(n+1) //n*n*n T(n)是矩阵阶数n的函数。  TKS * * AAA BBBB 2、问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模，一般用整数n表示。 对于例1.4的乘积算法，当n趋向无穷大时，显然有 lim ￥ ? n lim ￥ ? n 一个算法的时间复杂度(Time Complexity)是该算法的执行时间，记作T(n)，T(n)是该算法所求解问题规模n的函数。 当问题的规模趋向无穷大时，T(n)的数量级称为算法的渐近时间复杂度，记作 T(n)=〇(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。我们就是要找这个f(n) 。 例1.5 交换x和y的值。 TKS * * temp=x; x=y; y=temp; T(n)=〇(1) AAA BBBB 例1.6 变量计数之一 (1) x=O；y=0； (2) for(k=1；k=n；k++) (3)