运筹学第二讲ppt课件.ppt
《运筹学第二讲ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学第二讲ppt课件.ppt(30页珍藏版)》请在三一文库上搜索。
1、(第二讲),绍兴文理学院,计算机系计算机应用教研室,数据结构,想构成常用汉字的所有名言佳句,00:50,第1章 绪论(2)、第2章 线性表(1),一、教学目的:明确算法的概念,明确算法分析的作用与分析的重点;初步掌握算法分析的方法;明确线性表的概念和抽象数据类型的定义,掌握线性表的顺序表示、结构定义和基本操作;初步掌握平均时间复杂度的分析方法;算法设计训练。,二、教学重点:算法的概念,算法分析的作用与分析的重点;算法分析的方法;线性表的概念,线性表的顺序表示、结构定义和基本操作;平均时间复杂度的分析方法;算法设计训练。,三、教学难点:算法分析的方法;线性表的基本操作;平均时间复杂度的分析方法;
2、算法设计训练。 四、教学过程:,1.4 算法和算法分析,1.4.1 算法的定义及特性 算法(Algorithm)是对指定问题求得步骤的一种描述,是为了解决某类问题而规定的一个有限长的操作(指令)序列。 算法的五个重要特性: (1) 有穷性:算法必须是在执行有穷步之后结束,且每一步都可在有穷时间内完成。 (2) 确定性:算法中每一条指令必须有确切的含义,不会产生两义性。 (3) 可行性:描述的操作都可通过已经实现的基本运算执行有限次来完成 (4) 输入:有零个或多个输入。 (5) 输出:有一个或多个输出。,00:50,(1) 正确性。在合理的数据输入下,能够在有限运行时间内得到正确的结果。 (2
3、) 可读性。容易读懂和理解。 (3) 健壮性。当输入数据非法时,算法能适当地作出适应过处理。 (4) 高效性。高效性包括时间和空间两个方面。 时间高效是指算法设计合理,执行效率高,可以用时间复杂度来度量; 空间高效是指算法占用存储容量合理,可以用空间复杂度来度量。 时间复杂度和空间复杂度是衡量算法的两个主要指标。 评价算法的估算方法 (1) 事后统计方法利用计算机内部的计时功能。(不太采用) (2) 事前分析估算的方法。,1.4.2 评价算法优劣的基本标准,00:50,1.4.3 算法的时间复杂度,算法分析的目的是看算法实际是否可行,并在同一问题存在多个算法时,可进行时间性能上的比较,以便从中
4、挑选出较优算法。 1、算法的执行时间和语句的频度 一个算法的执行时间大致上等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。 语句的频度(Frequency Count):一条语句的重复执行次数。 算法的执行时间=原操作(基本操作)的执行次数(频度)原操作的执行时间 设每条语句一次执行的时间都是相同的,为单位时间。这样我们对时间的分析就可以独立于软硬件系统。,00:50,例1.4 求两个n阶矩阵乘积算法的执行时间,define n 自然数 MATRIXMLT(float ann,float bnn,float cnn) int i,j,k; fo
5、r(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,/n+1,/n(n+1),/n*n,/n*n*(n+1),/n*n*n,00:50,2、问题规模和算法的时间复杂度,算法求解问题的输入量称为问题的规模,一般用整数n表示。 对于例1.4的乘积算法,当n趋向无穷大时,显然有,一个算法的时间复杂度(Time Complexity)是该算法的执行时间,记作T(n),T(n)是该算法所求解问题规模n的函数。 当问题的规模趋向无穷大时,T(n)的数量级称为算法的渐近时间复杂度,记作 T(n)=(f(n) 它表示随问
6、题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,简称时间复杂度。我们就是要找这个f(n) 。 例1.5 交换x和y的值。,00:50,temp=x; x=y; y=temp;,T(n)=(1),例1.6 变量计数之一,(1) x=O;y=0; (2) for(k=1;k=n;k+) (3) x+; (4) for(i=1;i=n;i+) (5) for(j=1jj=n;j+) (6) y+;,T(n)=(n2),例1.7 变量计数之二 (1) x=1; (2) for(i=1;i=n;i+) (3) for(j=1;j=i;j+) (4) for(k=1;k=j;k+) (5) x
7、+;,00:50,(1) for(i=O;in;i+) (2) if(ai=e) return i+1; (3) return 0; T(n)=(n),例1.8 顺序查找,在数组ai中查找值等于e的元素,返回其所在位置。,补充例 几个时间复杂度的例, +x;s=0;,2,(1), for(i=1;i=n;+i) +x;s+=x;, for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,3n+1,(n),3n2 +2n+1,(n2),00:50, 常见的时间复杂度,按数量级递增排序:, 算法策略的重要性 补充例1: 100元买100支笔, 其中钢笔 3元/支, 圆珠笔
8、 2元/支, 铅笔 0.5元/支. 写算法输出各种组合方案,常数阶,对数阶,线性阶,线性对数阶,平方阶,立方阶, K次方阶,指数阶,00:50,解法1,算法的时间复杂度为 (N3),#define N 100 void scheme() int i,j,k,count,money; for(i=0;i=N;i+) for(j=0;j=N;j+) for(k=0;k=N;k+) count=i+j+k; money=3*i+2*j+0.5*k; if(count=N ,00:50,解法2,#define N 100 void scheme( ) int i,j; for(i=0;i=N/3;i+
9、) for(j=0;j=(N-3*i)/2;j+) if(3*i+2*j+0.5*(N-i-j)=N) printf(“%d,%d,%dn%”,i,j,N-i-j); 算法的时间复杂度为 (N2) 平均时间复杂度和最坏时间复杂度 (1) 平均时间复杂度 当算法中基本操作重复执行的次数随输入的数据不同而不同时,可考虑分析算法的平均时间复杂度,此时,各种出现的情况按,00:50,:最坏时间复杂度 当各种情况出现的概率难以确定时,可以分析最坏时间复杂度。这时是分析基本操作最多次数的情况。 1.4.4 算法的空间复杂度 算法的空间复杂度是指算法所需存储空间的量度,记作 S(n)=(f(n) (1) 若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第二 ppt 课件
链接地址:https://www.31doc.com/p-2709585.html