数据结构 数据结构 教学辅助课件 教学辅助课件 四川省省级精品课程 四川省省级精品课程 西南财经大学 西南财经大学

Presentation on theme: "数据结构 数据结构 教学辅助课件 教学辅助课件 四川省省级精品课程 四川省省级精品课程 西南财经大学 西南财经大学"— Presentation transcript:

1 数据结构 数据结构 教学辅助课件 教学辅助课件 四川省省级精品课程 四川省省级精品课程 西南财经大学 西南财经大学
经济信息工程学院 “数据结构”精品课程组 负 责 人：周启海 教授 博导 主讲教师：杨祥茂 副教授 黄 涛 副教授 李谨坤 副教授 2019/10/14

2 主讲教师简介 黄涛 副教授、博士 经济信息工程学院 院长助理 教学主页：http://htxy.cai.swufe.edu.cn
黄涛 副教授、博士 经济信息工程学院 院长助理 教学主页： Tel: ; 主要研究方向： 算法与程序设计；财经计算；支付经济学；金融智能； 金融信息管理；

3 主讲教师简介 主要科研与教学工作 近3年共发表论文34篇(本) ，其中： 合作出版专著1本； 参编教材3本；
在B1级以上核心刊物发表论文14篇 发表英文论文6篇(其中EI收录全文检索论文3篇；ISTP 收录全文检索6篇)； 主研科研项目3项(2项已顺利结项)； 荣获得西南财经大学优秀教学成果奖一等奖两项，四川省级三等奖一项 学校”精彩一课”比赛优秀奖

4 主要科研成果 1. 专著：（数量：1本） 2、编著、教材：（数量：3本） 3. 论文及译文：（数量：30篇）
[1]《同构化二维点集凸壳算法与应用研究》 .电子科技大学出版社， 合著 2、编著、教材：（数量：3本） [2]《电子商务导论》.西南财经大学出版社 , 参编 [3]《汇编语言程序设计》. 北京工业大学出版社 , 参编 [4]《全国计算机等级考试专项训练 》.中国铁道出版社, 参编 3. 论文及译文：（数量：30篇） [5]基于链表的择换排序新算法. 计算机科学，2008第10期 [6]基于双域双向水平倾角最小化圈绕的凸壳新算法. 计算机科学，2008第2期 [7]中国电子商务及其网上支付主要瓶颈初析. 计算机科学，2008第8期 [8]双域单向水平倾角最小化圈绕凸壳新算法 . 计算机科学，2007第11期 [9]基于最大基线倾角智能逼近的凸壳新算法 . 计算机科学，2007第9期 [10]一种基于数字加密与信息隐藏的电子签名技术改进方案 . 计算机科学，2007第10期 [11]同构化信息温度与热点发现初探 . 计算机科学，2007第11期 [12]基于双群双域四向水平倾角最小化圈绕的凸壳并行新算法 . 计算机科学,2008第2期 [13]基于四群四域四向动态基线倾角最大化圈绕的凸壳并行新算法. 计算机科学,2008第3期 [14]基于动态基线倾角与基线距离最大化的凸壳并行新算法 . 计算机科学,2008第4 [15]基于当前基线垂直落差最大化的凸壳递归新算法 . 计算机科学,2008第7期 [19]An improved scheme for e-singature techniques based on digital encryption and information hiding（EI检索号： ，ISTP检索号：BHZ19）USA: IEEE Computer Society, May, (EI,ISTP双检索第一作者)

5 主要教学成果 主持“20～21世纪高校程序设计课程教学改革与教育创新的研究与实践”获2005年西南财经大学优秀教学成果奖 一等奖。
主持“20～21世纪高校程序设计课程教学改革与教育创新的研究与实践”获2005年西南财经大学优秀教学成果奖 一等奖。　　　　 主持“21世纪高校数据结构课程教学改革及教育创新的研究与实践” 获2006年西南财经大学优秀教学成果奖 一等奖　　　　 “论程序设计课程教学中的同构化创新思想教育”　获2008年第十一次四川省高等教育学科优秀科研成果奖　三等奖 学校”精彩一课”教学比赛优秀奖

6 《数据结构》课程学习要求 Who? Why? What? 现实世界数据存储 程序员的工具 建模

7 目 录 第一章 绪论 第六章 树形结构 第二章 线性表 第七章 图 第三章 栈与队列 第八章 查找 第四章 串 第九章 排序 第五章 数组与广义表 第十章 文件

8 课程内容： 课时安排： 教 材： 计算机软件的基础知识———数据结构 数据结构——51学时 上 机——9～15学时
上 机——9～15学时 教 材： 严蔚敏编著. 数据结构（C语言版）.清华大学出版社,1997年版. 数据结构习题集（C语言版） 数据结构与算法 python语言描述-裘宗燕

9 第一章：绪论

10 教学重点与难点 重点： 数据结构的基本概念及有关术语 算法及算法的分析方法 难点： 时间复杂度的估算

11 课前思考 你知道数据结构是一门讨论什么内容的学科吗？ 人工智能与数据结构的关系？

12 数据结构的创始人—克努特 1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著： The Art of Computer Programming 他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。

13 Algorithm + Data Structures = Programs ( 算 法 + 数 据 结 构 = 程 序 ）
数据结构课程讨论的内容 著名的瑞士科学家沃思教授 Algorithm + Data Structures = Programs ( 算 法 + 数 据 结 构 = 程 序 ） 数据结构: 算 法: 程 序: 问题的数学模型，它反映数据及其之间关系。（存储结构和逻辑结构） 处理问题的策略（是对数据运算的描述，是程序的逻辑抽象） 为计算机处理问题而编制的一组指令集

14 求解问题举例 问题求解的主要步骤： 1.确定求解问题的数学模型 (逻辑结构)； 2.确定存储结构； 3.设计算法； 4.编程并测试结果。

15 数据结构的关键 计算机求解问题: 问题→抽象出问题的模型→求模型的解 问题——数值问题、非数值问题 数值问题→数学方程 非数值问题→数据结构

16 二是设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
求解问题举例 程序设计的实质是在于解决两个主要问题： 一是根据实际问题选择一种好的数据结构； 二是设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

17 书目卡片 线性表 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目文件 按登陆号排序 索引表 按登陆号 按书名索引
1.1 什么是数据结构 程序=数据结构+算法 例1 书目自动检索系统 线性表 按登陆号排序 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名索引 按作者索引 按登陆号 索引表

18 树 例2 人机对奕问题 …….. …...

19 图 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED

20 试用计算机求任给矩阵Am×m的各元素之和,其中m≤10000。
(效率最低) (效率一般) 解法1: 数据存储，采用2维数组结构。 算法 Eg010101; {采用2维数组} 整型:i,j,m,s; {定义整型变量} 整型 数组 [1..100,1..100]:x; {定义2维整型数组} >>> {算法开始} 输出 “矩阵行数 m=?”; 输入 m; {输入(矩阵)行数} s←0; {累加器初始化} 对 \\ {各元素逐行顺序存放} 对 \\ 输出 “a(”,i, “,”,j,”)=?”; 输入 x[i,j]; {输入各元素} s←s+x[i,j] {累加求和} //; 行输出 “矩阵A各元素之和为”; s; !!! {算法结束} 解法2: 数据存储，采用1维数组结构。 算法 Eg010101; {采用2维数组} 整型:i,j,m,s; {定义整型变量} 整型 数组 [ ]:x; {定义1维整型数组} >>> {算法开始} 输出 “矩阵行数 m=?”; 输入 m; {输入(矩阵)行数} m←m*m; s← 0; {求元素个数；累加器初始化} 对 \\ {各元素单行顺序存放} 输出 “a(”,i,”)=?”; 输入 x[i]; {输入各元素} s←s+x[i] {累加求和} //; 行输出 “矩阵A各元素之和为”; s; !!! {算法结束} 解法3: 数据存储，采用平凡数据结构——简单变量。 算法 Eg010101; {采用2维数组} 整型:i,m,s,x; {定义整型变量} >>> {算法开始} 输出 “矩阵行数 m=?”; 输入 m; {输入(矩阵)行数} m←m*m; s← 0; {求元素个数；累加器初始化} 对 \\ {各元素单行顺序存放} 输出 “a(”,i,”)=?”; 输入 x; {输入各元素} s←s+x {累加求和} //; 行输出 “矩阵A各元素之和为”; s; !!! {算法结束} (效率最高)

21 根据数据元素间关系的基本特性，有四种基本数据结构：
1.2 基本概念和术语 数据（data)—所有能输入到计算机中去的描述客观事物的符号 数据元素（data element）—数据的基本单位，也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单位，也称域(field) 数据结构（data structure)—数据元素和数据元素关系的集合 数据之间的相互联系，称为逻辑结构。（在计算机中存储数据时，不仅要存储数据本身，还要存储其逻辑结构。） 一种数据结构在计算机中的存储方式，称为物理结构 根据数据元素间关系的基本特性，有四种基本数据结构： 集合 ——数据元素间除“同属于一个集合”外，无其它关系。 线性结构——一个对一个。（例如：线性表、栈、队列） 树状结构——一个对多个。（例如：树） 图状结构——多个对多个。（例如：图） 数据结构

22 数据的逻辑结构—只抽象反映数据元素的逻辑关系
数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构

23 顺序存储 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容
…….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 元素i(地址)定位: Loc(元素i)=Lo+（i-1)*m (其中:m为元素长度) 顺序存储

24 h h 链式存储 ∧ 存储地址 存储内容 指针（所指地址） 1345 元素1 1400 1346 元素4 ∧（无地址） ……. ……..
（存储地址） h 元素1 （存储内容） 1400 （存储地址） 元素2 （存储内容） 1536 （存储地址） 元素3 （存储内容） 1346 （存储地址） 元素4 （存储内容） ∧ （无地址） 存储地址 存储内容 指针（所指地址） 1345 元素1 1400 1346 元素4 ∧（无地址） ……. …….. 元素2 1536 元素3

25 数据结构课程的内容体系: 1. 数据的逻辑结构 本课程的内容 方面 过程 数据表示 数据处理 抽象 逻辑结构 基本运算 实现 存储结构 算法
评价 不同数据结构的比较和算法性能分析 简单地说, 本课程研究的内容包括以下三方面： 1. 数据的逻辑结构 2. 数据的存储结构/物理结构 3. 数据的运算

26 数据的运算：检索、排序、插入、删除、修改等
数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面：

27 数据与数据结构 逻辑结构可用二元组形式定义为: Data_Structures = (D, R) 其中: D 是数据元素的有限集合， R是 D上关系的有限集合。 也可用数据的逻辑结构图来形象表示之。

28 开始结点为k1,k2(无前驱的结点） 终端结点为k6,k7(无后继的结点） 【例1】设有数据结构为： B=（D，R），其中：
D={k1,k2,k3,….k9} R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>, <k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>} 画出其逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些是终端结点？ 开始结点为k1,k2(无前驱的结点） 终端结点为k6,k7(无后继的结点）

29 两种关系，一种是行关系，一种是列关系，试给出其逻辑结构的二元组表示形式。
【例2】矩阵 中9个元素之间存在 两种关系，一种是行关系，一种是列关系，试给出其逻辑结构的二元组表示形式。 ， 其逻辑结构的二元组表示形式为： B=（D，R），其中： D={a1,a2,……,a9} R={ROW,COL} //ROW:行关系，COL:列关系 ROW= {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>,<a7,a8>,<a8,a9>} COL= {<a1,a4>,<a4,a7>,<a2,a5>,<a5,a8>,<a3,a6>,<a6,a9>}

30 数据与数据结构 存储结构 ——是逻辑结构在计算机中的表示， （即是逻辑结构在存储器中的映象） “数据元素”的映象 ？ “关系”的映象 ？

31 存储结构 用二进制位(bit)的位串表示数据元素 ‘a’= ( )10 = ( )8 = ( )2 数据与数据结构——
“数据元素”的映象方法： 用二进制位(bit)的位串表示数据元素 (456)10 = (710)8 = ( )2 ‘a’= ( )10 = ( )8 = ( )2

32 x y 存储结构 1. 顺序映象 以相对的存储位置来表示数据元素之间的逻辑关系。 （逻辑位置关系与存储位置关系是一致的） 数据与数据结构—
“数据关系”的映象方法： 1. 顺序映象 以相对的存储位置来表示数据元素之间的逻辑关系。 （逻辑位置关系与存储位置关系是一致的） 如：表示x, y的方法： x y 顺序存储结构 注意 所有元素存放在一片连续的存贮单元中 整个存储结构中只含数据元素值本身的信息

33 需要用一个和 x附加在一起的指针来指示 y 的存储位置。
存储结构 数据与数据结构—— 2. 链式（非线性）映象 (表示x, y的方法) 以附加信息(指针)表示后继关系。 需要用一个和 x附加在一起的指针来指示 y 的存储位置。 y x 链式存储结构 注意 所有元素存放在可以不连续的存贮单元中 逻辑上相邻的元素其存储位置不一定相邻

34 存储结构 数据与数据结构—— 顺序存储 最常用 的两种 链式存储 数据的存储结构 索引存储 散列存储

35 1.3 数据类型 在用高级程序语言编写的程序中，每个数据都应有一个所属的、确定的数据类型。 其实数据类型反映三个方面的内容：存储结构，取值范围和允许进行的操作。

36 1.3 抽象数据类型 抽象数据类型 1. 数据类型(Data Type)：一组值的集合以及定义于这个值集上的一组操作的总称。
1.3 抽象数据类型 抽象数据类型 1. 数据类型(Data Type)：一组值的集合以及定义于这个值集上的一组操作的总称。 例如：C中的整型变量 2. 抽象(Abstract):抽出问题本质的特征而忽略非本质的细节。 例如： 地图、驾驶汽车 3. 抽象数据类型(Abstract Data Type，ADT):一个数据结构以及定义在该结构上的一组操作的总称。

37 1.3 抽象数据类型 数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称 例 C语言中，提供
1.3 抽象数据类型 数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称 例 C语言中，提供 ①int, char, float, double等基本数据类型; ②数组型、结构（即记录）型、共用型、枚举型等构造数据类 型，还有指针型、空(void)类型等。 ③用户也可用typedef 自己定义数据类型。 typedef struct { int num; char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p;

38 1.3 抽象数据类型 ADT的定义形式 ADT 抽象数据类型名{ Data Objects ：数据元素的定义 Data relations：
1.3 抽象数据类型 ADT的定义形式 ADT 抽象数据类型名{ Data Objects ：数据元素的定义 Data relations： 数据元素之间逻辑关系的定义 Operation： 操作1 前置条件：执行此操作前数据所必须的状态 输 入：执行此操作所需要的输入 功 能：该操作将完成的功能 输 出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 …… 操作n }ADT 抽象数据类型名

39 1.4 算法及算法分析 算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性— 算法的描述—采用C语言
1.4 算法及算法分析 算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性— 算法的描述—采用C语言 算法的评价—衡量算法优劣的标准 正确性(correctness) 可读性(readability) 健壮性(robustness) 效率与低存储量

40 1.4 算法及算法分析 基于程序运行时间的评判方法 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量
1.4 算法及算法分析 基于程序运行时间的评判方法 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量 1.事后统计评价——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本 身的优劣 2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适

41 1.4 算法及算法分析 基于算法复杂程度的评判方法
1.4 算法及算法分析 基于算法复杂程度的评判方法 时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n))；其中：f(n)是关于基本操作执行次数的函数 空间复杂度：s(n)=O(f(n))一个算法在运行过程中临时占用的存储空间大小的量度。其中：f(n)是关于存储空间占用量的函数。 例： For(i=0;i<=n;i++) 循环体 ——单重循环控制的操作次数为： 因：i=0; //初始化：1次 i<=n; //循环条件判定：n+1次 i++; //循环变量值修正：n次 n //返回循环判定处操作： n次 故：单重循环i控制次数函数 f(n) = 3n+2次 据此，当n→∞时，单重循环i控制次数的阶数 T(n)=O( 3n+2)=O(n)

42 1.4 算法及算法分析 例： For(i=0;i<n;i++)
1.4 算法及算法分析 例： For(i=0;i<n;i++) For(j=0;j<n;j++) 循环体——双重循环控制的操作次数为： 因：外层循环i次数 = 3n+2 内层循环j次数 = 3n+2 故：双重循环i,j次数=外层循环i次数+n*内层循环j次数 =3n+2+n*(3n+2) =3n2+5n+2。 据此，当n→∞时，双重循环i,j控制次数的阶数 T(n)=O(3n2+5n+2)=O(n2) 例：n×n矩阵相乘 for(i=1; i<=n; i++) //次数：3n+2 for(j=1;j<=n;j++) //次数：n*(3n+2) { c[i][j]=0; //次数：n*n=n2 for(k=1;k<=n;k++) //次数：n*n*(3n+2) c[i][j]=c[i][j]+a[i][k]*b[k][j]; //(重心操作)次数：n*n*n } 据此，当n→∞时，n×n矩阵相乘次数的阶数 T(n)=O(4n3+6n2+5n+2) =O(n3)

43 1.4 算法及算法分析 例：欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数 欧几里德算法 m r n

44 1.4 算法及算法分析 算法的描述方法——自然语言 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想
1.4 算法及算法分析 算法的描述方法——自然语言 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段

45 1.4 算法及算法分析 例：欧几里德算法 自然语言 ① 输入m 和n； ② 求m除以n的余数r；
1.4 算法及算法分析 例：欧几里德算法 ① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束；否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。 自然语言

46 1.4 算法及算法分析 算法的描述方法——流程图 优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次

47 1.4 算法及算法分析 N 开始 输入m和n r=m % n r=0 m=n；n=r 输出n 结束 Y 例：欧几里德算法 流 程 图

48 1.4 算法及算法分析 算法的描述方法——程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证
1.4 算法及算法分析 算法的描述方法——程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数

49 1.4 算法及算法分析 例：欧几里德算法 程序设计语言 int CommonFactor(int m, int n) {
1.4 算法及算法分析 例：欧几里德算法 int CommonFactor(int m, int n) { int r=m % n; while (r!=0) m=n; n=r; r=m % n; } return n; 程序设计语言 main( ) { int min=CommonFactor(63, 54)； cout<<min; }

50 1.4 算法及算法分析 算法的描述方法——伪代码 伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解 使用方法：7 ± 2

51 1.4 算法及算法分析 例：欧几里德算法 1. r = m % n; 2. 循环直到 r 等于0 伪 代 码 2.1 m = n;
1.4 算法及算法分析 例：欧几里德算法 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ; 伪 代 码 上述伪代码再具体一些，用C的函数来描述。请同学们自行完成！

52 1.4 算法及算法分析 算法分析 度量算法效率的方法： 事后统计：将算法实现，测算其时间和空间开销。
1.4 算法及算法分析 算法分析 度量算法效率的方法： 事后统计：将算法实现，测算其时间和空间开销。 缺点：⑴ 编写程序实现算法将花费较多的时间和精力； ⑵ 所得实验结果依赖于计算机的软硬件等环境因素。 事前分析：对算法所消耗资源的一种估算方法。

53 1.4 算法及算法分析 算法分析 算法分析（Algorithm Analysis）：对算法所需要的计算机资源——时间和空间进行估算。
1.4 算法及算法分析 算法分析 算法分析（Algorithm Analysis）：对算法所需要的计算机资源——时间和空间进行估算。 时间复杂性（Time Complexity） 也称为：渐进时间复杂度，T(n)=O(f(n)) 空间复杂性（Space Complexity） S(n)=O(f(n))

54 1.4 算法及算法分析 算法分析 算法的时间复杂度分析 算法的执行时间＝每条语句执行时间之和 单位时间 每条语句执行次数之和
1.4 算法及算法分析 算法分析 算法的时间复杂度分析 算法的执行时间＝每条语句执行时间之和 单位时间 每条语句执行次数之和 执行次数×执行一次的时间 基本语句的执行次数 指令系统、编译的代码质量

55 1.4 算法及算法分析 算法分析 问题规模：输入量的多少。 基本语句：是执行次数与整个算法的执行次数成正比的操作指令。
1.4 算法及算法分析 算法分析 问题规模：输入量的多少。 基本语句：是执行次数与整个算法的执行次数成正比的操作指令。 频度:是指该语句重复执行的次数。 例如： （a）{x++；s=0；} （b）for(i=1;i<=n;++i) {x++；s+=x；} （c）for(j=1;j<=n;++j) for(k=1;k<=n;++k) {x++；s+=x；}

56 1.4 算法及算法分析 算法分析——大O符号 定义 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n)) n0 问题规模n 执行次数 n0之前的情况无关紧要 T(n) c×f(n) 当问题规模充分大时在渐近意义下的阶

57 1.4 算法及算法分析 说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。 算法分析——大O符号
1.4 算法及算法分析 算法分析——大O符号 定理：若A(n)=amnm+am-1nm-1++a1n+a0是一个m次多项式，则A(n)=O(nm)。 说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。

58 1.4 算法及算法分析 例 1： temp = i; i = j; j = temp;
1.4 算法及算法分析 例 1： temp = i; i = j; j = temp;  如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1)。

59 1.4 算法及算法分析 例 2： x=0;y=0; for (k=1;k<=n;k++) x++;
1.4 算法及算法分析 例 2： x=0;y=0; for (k=1;k<=n;k++) x++; for (i=1;i<=n;i++) for (j=1;j<=n;j++) y++; //n*n  一般情况下，对循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加1、终值判断、控制转移等成分。

60 1.4 算法及算法分析 例 3： x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++)
1.4 算法及算法分析 例 3： x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++;

61 1.4 算法及算法分析 很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。 例4：在数组A[n]中查找值为k的元素。 i = n-1; while ( (i>=0) && A[i]!=k) ) i--; return i;

62 1.4 算法及算法分析 常见的时间复杂度，按数量级递增排序： 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶
1.4 算法及算法分析 常见的时间复杂度，按数量级递增排序： 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶 Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3) ＜…＜Ο(2n)＜Ο(n!)

63 1.4 算法及算法分析 最好情况、最坏情况、平均情况 例：在一维整型数组A[n]中顺序查找与给定值k相等的元素
1.4 算法及算法分析 最好情况、最坏情况、平均情况 例：在一维整型数组A[n]中顺序查找与给定值k相等的元素 （假设该数组中有且仅有一个元素值为k）。 int Find(int A[ ], int n) { for (i=0; i<n; i++) if (A[i]= =k) break; return i; } 基本语句的执行次数是否只和问题规模有关？

64 1.4 算法及算法分析 最好情况、最坏情况、平均情况
1.4 算法及算法分析 最好情况、最坏情况、平均情况 结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。 最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布

65 算法设计比较 【问题描述】给定一整数序列A1， A2，... An （可能有负数），求A1～An的一个子序列Ai～Aj，使得Ai到Aj的和最大。例如：整数序列 -2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21（从A2到A9）；整数序列4，-3，5，-2，1，2，6，-2的最大子序列的和为11（从A1到A7）。 提示：可以用四种实现方法

66 本章小结——知识结构图 绪 论 数据结构 算 法 基 本 概 念 逻 辑 结 构 存 储 ⑴数据 ⑵数据元素 ⑶数据对象 ⑷ADT
绪 论 数据结构 算 法 基 本 概 念 逻 辑 结 构 存 储 ⑴数据 ⑵数据元素 ⑶数据对象 ⑷ADT ⑴逻辑结构 ⑵数据结构 的分类 ⑴存储结构 ⑵常用存储 方法 算 法 分 析 ⑴算法 ⑵算法特性 ⑶评价算法 ⑷描述算法 ⑴问题规模 ⑵基本语句 ⑶时间复杂度 ⑷大O记号 关 系

67 本 章 小 结 　　1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2. 了解抽象数据类型的定义、表示和实现方法。 3. 熟悉用C语言描写算法的书写规范。 4. 理解算法5个性质的确切含义和对算法正确性的理解。 　5. 掌握计算语句频度和估算算法时间复杂度的方法

68 作 业 1.概念理解：习题集 P8 1.8, 1.9 2.算法设计：习题集 P , 1.17