问题的规模 规模越大,消耗时间越多 书写程序的语言语言越高级,消耗时间越多 编译产生的机器代码质量 机器执行指令的速度 综上所述,为便于比较算法本身的优劣,应排除其它影响算法效率的因素。 从算法中选取一种对于所研究的问题来说是基本*作的原*作,以该基本*作重复执行的次数作为算法的时间量度。(原*作在所有该问题的算法中 都相同) 7(n)=O 上示表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度 sum(int num[4(4) for(i=0;i<4i++) 求4*4矩阵元素和 T(4)=0(f(4) for j=0; j<4: j++) r+=num[[j];/*原*作* ipass(int num[4[)) K inti,j for(i=0<4i++) 最好情况 T(4)=0(0) forj=0;j<4)j++) 最坏情况 if(num[Dll=i 4+j+1) T(4)=0(n*n) retum 1. 原*作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数 语句 频度 时间复杂度 {++X=0; 1
问题的规模 规模越大，消耗时间越多 书写程序的语言 语言越高级，消耗时间越多 编译产生的机器代码质量 机器执行指令的速度 综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。 从算法中选取一种对于所研究的问题来说是基本*作的原*作，以该基本*作重复执行的次数作为算法的时间量度。 （原*作在所有该问题的算法中 都相同） T(n)=O(f(n)) 上示表示随问题规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 求 4*4 矩阵元素和， T(4)=O(f(4)) f=n*n; sum(int num[4][4]) { int i,j,r=0; for(i=0;i<4;i++) for(j=0;j<4;j++) r+=num[i][j]; /*原*作*/ return r; } 最好情况： T（4）=O（0） 最坏情况： T（4）=O（n*n） ispass(int num[4][4]) { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1) return 0; return 1; } 原*作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。 语句 频度 时间复杂度 {++x;s=0;} 1 O(1)
for(i=1;i<=n;++) o(n) {++X;s+=X for=1小<=n;++j) for(k= 1; k o(log n) 0[2) 基本*作的执行次数不确定时的时间复杂度 平均时间复杂度 依基本*作执行次数概率计算平均 最坏情况下时间复杂度 在最坏情况下基本*作执行次数 、算法的存储空间需求 类似于算法的时间复杂度,空间复杂度可以作为算法所需存储空间的量度。 n)=n) 若额外空间相对于输入数据量来说是常数,则称此算法为原地工作 如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析 总结 渐近时间复杂度 空间复杂度 数据结构教程第五课线性表的类型定义
for(i=1;i<=n;++i) {++x;s+=x;} n O(n) for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;} n*n O(n*n) O(log n) 基本*作的执行次数不确定时的时间复杂度 平均时间复杂度 依基本*作执行次数概率计算平均 最坏情况下时间复杂度 在最坏情况下基本*作执行次数 二、算法的存储空间需求 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。 记作： S(n)=O(f(n)) 若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。 三、总结 渐近时间复杂度 空间复杂度 数据结构教程 第五课 线性表的类型定义
数学目的:掌握线性表的概念和类型定义 教学重点?线性表的类型定义 教学难点:线性表的类型定义 授课内容 复习:数据结构的种类 线性结构的特点: 在数据元素的非空有限集中 1)存在 个被称做”第一个”的数据元素 (2)存在唯一的一个被称做最后一个”的数据元素 3)除第一个之外,集合中的每个数据元素均只有一个前驱 (4)除最后一个之外,集合中每个数据元素均只有一个后继。 Q@@@@ 线性表的定义 线性表是最常用且最简单的一种数据结构 个线性表是n个数据元素的有限序列 数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息 1 3 67
教学目的： 掌握线性表的概念和类型定义 教学重点： 线性表的类型定义 教学难点： 线性表的类型定义 授课内容： 复习：数据结构的种类 线性结构的特点： 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素； （2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。 一、线性表的定义 线性表是最常用且最简单的一种数据结构。 一个线性表是 n 个数据元素的有限序列。 数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。 线性表例： 1、 1 2 3 4 5 6 7 2
学号 姓名 语文 数学 C语言 6201001 92 6201002 李四 6201003 王五 87 74 6201004 数据元素也可由若干个数据项组成(如上例3)。这时常把数据元素称为记录。含有大量记录的线性表又称文件 线性表中的数据元素类型多种多样,但同一线性表中的元素必定具有相同特性,即属同一数据对象,相邻数据元素之间存在着序偶关系。 a1 ai-1 ai+ an ai是彐+1的直接前驱元素,彐+1是a的直接后继元素 线性表中元素的个数n定义为线性表的长度,为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第个元素,把i称为数 据元素在线性中的位序 线性表的类型定义 1、抽象数据类型线性表的定义如下 ADT List 数据对象:D={ala〔 elem set ia=1,2,…,nn>=0} 数据关系:R1={<a1,a>|a-1,a(-D,i=2,…,n 基本*作: InitList(&L) DestroyList(&L) dlearList( &L) ListEmpty ( L ListLength( L)
3、 学号 姓名 语文 数学 C 语言 6201001 张三 85 54 92 6201002 李四 92 84 64 6201003 王五 87 74 73 6201004 ... 数据元素也可由若干个数据项组成（如上例 3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。 线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。 a1 ... ai-1 ai ai+1 ... an ai 是 ai+1 的直接前驱元素，ai+1 是 ai 的直接后继元素。 线性表中元素的个数 n 定义为线性表的长度，为 0 时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai 是第 i 个元素，把 i 称为数 据元素 ai 在线性中的位序。 二、线性表的类型定义 1、抽象数据类型线性表的定义如下： ADT List{ 数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 基本*作： InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L)
GetElem (Li, &e) LocateElem(L,e, compared) PriorElem (L,aur_e, &pre_e) xtElem(L,cur_e, &next_e ListTraverse(L,visito) union(List &La, List &Lb) JADT List 2、部分*作的类C实现: InitListi(&L】 [Lelem=(ElemType )mallodLIST_INIT_SIZE*sizeof(ElemType )); L listsize=LIST INIT SIZE, um OK: f//InitList etElem(l, i, &e) te=Lem[ M//GetElem ListInsert(List &L,int i, ElemType e) if(<1i>Llength+)retum ERROR for(p=&(Lelem[L length-1D: p>=q-P)*(p+1)=*p ng return ok
GetElem(L,i,&e) LocateElem(L,e,compare()) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit()) union(List &La,List &Lb) }ADT List 2、部分*作的类 C 实现： InitList(&L) {L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//InitList GetElem(L,i,&e) {*e=L.lem[i] }//GetElem ListInsert(List &L,int i,ElemType e) {if(i<1||i>L.length+) return ERROR; q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK;