运筹学第二讲ppt课件.ppt

（第二讲）,绍兴文理学院,计算机系计算机应用教研室,数据结构,想构成常用汉字的所有名言佳句,00:50,第1章 绪论(2)、第2章 线性表（1）,一、教学目的：明确算法的概念，明确算法分析的作用与分析的重点；初步掌握算法分析的方法；明确线性表的概念和抽象数据类型的定义，掌握线性表的顺序表示、结构定义和基本操作；初步掌握平均时间复杂度的分析方法；算法设计训练。,二、教学重点：算法的概念，算法分析的作用与分析的重点；算法分析的方法；线性表的概念，线性表的顺序表示、结构定义和基本操作；平均时间复杂度的分析方法；算法设计训练。,三、教学难点：算法分析的方法；线性表的基本操作；平均时间复杂度的分析方法；算法设计训练。 四、教学过程：,§1.4 算法和算法分析,§1.4.1 算法的定义及特性 算法(Algorithm)是对指定问题求得步骤的一种描述，是为了解决某类问题而规定的一个有限长的操作(指令)序列。 算法的五个重要特性： (1) 有穷性：算法必须是在执行有穷步之后结束，且每一步都可在有穷时间内完成。 (2) 确定性：算法中每一条指令必须有确切的含义，不会产生两义性。 (3) 可行性：描述的操作都可通过已经实现的基本运算执行有限次来完成 (4) 输入：有零个或多个输入。 (5) 输出：有一个或多个输出。,00:50,(1) 正确性。在合理的数据输入下，能够在有限运行时间内得到正确的结果。 (2) 可读性。容易读懂和理解。 (3) 健壮性。当输入数据非法时，算法能适当地作出适应过处理。 (4) 高效性。高效性包括时间和空间两个方面。 时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量； 空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。 时间复杂度和空间复杂度是衡量算法的两个主要指标。 评价算法的估算方法 (1) 事后统计方法利用计算机内部的计时功能。(不太采用) (2) 事前分析估算的方法。,§1.4.2 评价算法优劣的基本标准,00:50,§1.4.3 算法的时间复杂度,算法分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间性能上的比较，以便从中挑选出较优算法。 1、算法的执行时间和语句的频度 一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。 语句的频度(Frequency Count)：一条语句的重复执行次数。 算法的执行时间=原操作(基本操作)的执行次数(频度)×原操作的执行时间 设每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。,00:50,例1.4 求两个n阶矩阵乘积算法的执行时间,define n 自然数 MATRIXMLT(float ann,float bnn,float cnn) int i,j,k; for(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) 它表示随问题规模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+;,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元/支, 圆珠笔 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+) 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) 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 (2) 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 (3) 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。 一个算法空间的效率当然是越高越好，但往往与时间的效率是一对辨证的矛盾。,等概率出现对待。如有关排序算法的分析。,00:50,§2.1 线性表的类型定义,§2.1.1线性表的定义和特点 1、定义 线性表(liner_list)是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。 2、线性表结构例 例1：数学中的数列（11，13，15，17，19，21） 例2：英文字母表（A, B, C, D, E Z）。 例3：某单位的电话号码簿。,00:50,3、说明和特点,(1) 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的； (2) 在表中 ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱，ai+1是ai的直接后继； (3) 在线性表中，存在唯一一个被称作第一个元素和最后一个元素，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继。 (4) ai是线性表的第i 个元素，称i为数据元素 ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号； §2.1.2 线性表的抽象数据类型定义 ADT List 数据对象：Dai|aiElemSet,i=1,2,.,n, n0 数据关系：R|ai-1 ,aiD,i=2,.,n,00:50,基本操作：(简讲),InitList( &L )(初始化操作) 操作结果： 构造一个空的线性表L。 DestroyList( &L ) (销毁操作) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L。 ClearList( &L ) (置空操作) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 ListLength(L) (求表长操作) 初始条件：线性表 L 已存在。 操作结果：返回L中元素个数。 GetElem( L, i, &e ) (求线性表中某个数据元素操作) 初始条件：线性表 L 已存在。且 1iListLength(L)。 操作结果：用e 返回L中第i 个元素的值。,00:50,LocateElem( L,e,compare( ) (定位操作),初始条件：线性表 L 已存在，e为给定值，compare( )是元素判定函数。 操作结果：返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。 ListInsert( &L,i,e) (插入元素操作) 初始条件：线性表 L 已存在。且 1iListLength(L)+1。 操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。 ListDelete( &L,i,&e) (删除元素操作) 初始条件：线性表 L 已存在。且 1iListLength(L)。 操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。 ADT List,00:50,§2.2 线性表的顺序表示和实现,§2.2.1 线性表的顺序存储表示,1、概念 线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。 2、存储位置公式 若线性表的每个元素占用l个存储单元 则有 loc(ai+1)=loc(ai)+l,loc(ai)=loc(a1)+(i-1)×l,空闲,00:50, 线性表的这种机内表示称做线性表的顺序存储结构或顺序映像，这样存储的线性表叫顺序表。,特点是：元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。, 顺序存储结构是一种随机存取的存储结构。 高级语言中通常用数组值来描述顺序存储结构。 3、顺序表的存储结构 #define MAXSIZE 100 / 顺序表可能达到的最大长度 typedef struct ElemType *elem; / 存储空间基址 int length; / 当前长度 SqList;,00:50,1、初始化- 算法2.1 顺序表的初始化 Status InitList_Sq(SqList ,§2.2.2 顺序表中基本操作的实现,2、查找-算法2.2 顺序表的查找 int LocateELem_Sq(SqList L,ElemType e) for(i=O;iL.length;i+) if(L.elermi=e) return i+1; return 0; ,算法时间复杂度：(1),算法时间复杂度：(L.length),00:50,算法 2.2 顺序表的 建立和查找 S2_1, 查找算法分析,(1) 分析对象：关键字和给定值进行过比较的记录个数的平均值。 (2) 平均查找长度(Average Search Length)：和给定值进行比较的关键字个数的期望值称为查找表算法在查找成功时平均查找长度。可表示为：,Ci为找到该记录时，曾和给定值比较过的关键字的个数。 对顺序表而言，Ci = i 则 ASL = P1 + 2P2 + +(n-1)Pn-1+nPn 在等概率查找的情况下，,其中: n 为表长，Pi 为查找表中第i个记录的概率，且,顺序表查找的平均查找长度为：,所以：T(n)=(n),00:50,3、插入,(1) 分析：插入后使原表长为 n的表:(a1,ai-1,ai,an) 成为表长为 n+1 表: (a1,ai-1,e,ai, an),在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。,00:50,(2) 算法描述,Status ListInsert_Sq(SqList ,算法 2.3 顺序表中插入一个元素 S2_2,00:50,L.length-1,0,87,56,42,66, 演示,例如：ListInsert_Sq(L, 5, 66),00:50,00:50,假设在第i个元素之前插入的概率为pi，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：,(3) 算法分析,假设在线性表中任何一个位置上进行插入的概率都是相等的，即：,则：,算法时间复杂度为: O(n ),4、删除,删除线性表中第 i 个元素； (1) 分析：删除后使原表长为n的线性表： (a1，a2，.，ai-1，ai，ai+1，.，an) 成为表长为 n-1 的线性表： (a1，a2，.，ai-1，ai+1，.，an),ai+1,an,表的长度减少,00:50,(2) 算法描述,Status ListDelete_Sq(SqList ,算法 2.4 顺序表中删除一个元素 S2_3,00:50,假设删除第 i 个元素的概率为 pi, 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,假定在线性表中任何一个位置上进行删除的概率都是相等的，即：,则：,(3) 算法分析,算法时间复杂度为: O(n ),00:50,五、作业：,1、书面作业：p16 6、p41 1中 (1)、(2)、(3)、(9)、(10) 2、上机编程：(数据结构编程练习)中 p43 2中 (10)(8811)、8809、8810,？,00:50,