组合数学第1章 1

1、编写函数计算： 1-2+3-4+5-6+7+n(n很大）,例 子,数据结构,1,for(i=1;i=n;i+) s=s+flag*i； flag=-flag; ,while(j 0?i+;i-; j+; ,if (0= =n%2) return -n/2; else return -n/2+n;,F1F2F3,数据结构,2,有乘法 执行效率低,乘法变为加法 执行效率提高,没有循环运算 算法简洁 效率大幅提高 n很大更明显,算法1算法2算法3,数据结构,3,数据的类型,算法,数据类型和算法之间的关联,程序设计时考虑的因素,数据结构,4,学习常用的算法；,训练复杂程序设计,课 程 目 的,抽象逻辑

2、结构 选择存储结构 设计算法,算法的时间分析和空间分析技术,5,Objective,描述课程要求 说明课程目的 学习什么是数据结构 学会用抽象数据类型表示数据结构 学会时间复杂度和空间复杂度分析的技巧,数据结构课程的重要性,前驱课程,程序设计能力 提高,专业基础课,考研,第一章 概论,内容,数据结构讨论的范畴 数据结构的基本概念和术语 抽象数据类型的表示与实现 算法与算法分析,数据结构讨论的范畴,数据结构和程序设计的关系 Niklaus Wirth： Algorithms + Data Structures = Programs 数据结构：问题的数学描述 逻辑结构和物理结构 算法：处理问题的策

3、略（对数据运算的描述) 程序：为计算机处理问题编制的一组指令集,解决问题的步骤,任务,解,求解,输入,输出,抽象：过程抽象数据抽象,数据结构：逻辑结构物理结构,算法：解决问题的步骤,程序：计算机实现算法,数据的结构类型,有什么类型的数据结构？,数值,非数值,考生录取信息系统,考生信息表,姓名索引表,专业索引表,成绩索引表,考生录取信息系统,计算机处理的对象：表 元素间的关系：线性关系 施加于对象上的操作 查询、插入、删除等 算法：如何进行各种查询 模型：各种表格,棋盘格局,棋盘格局,计算机处理的对象：树型结构 元素间的关系： 层次关系，一对多的关系 施加于对象上的操作 查询、插入、删除等 算法

4、：博弈的规则和策略 模型：棋盘、棋子如何表示,快速送达疫苗,已知有临近的五个村子发生了疫情，我们要用汽车快速地将疫苗送达到5个村子。目标是寻找一条耗时最少的路线。,耗时矩阵,穷举法,贪心算法,问题被抽象成了图结构,快速送达疫苗,计算机处理的对象：图 元素间的关系： 图形或网状关系，多对多的关系 施加于对象上的操作 查询、插入、删除等 算法：如何求距离、最短路径等 模型：图或者网络,数据结构,集合结构：,线性结构：,数据结构,树形结构：,图形结构：,基本概念和术语,数据(Data)：信息的载体 描述客观事物的数、字符等 计算机程序识别和处理的符号的集合。 数据类型 数值型数据： 整数、实数、字符

5、串 非数值型数据： 文字、表、图像、图形、声音、视频等,基本概念和术语,数据元素(Data Element)： 数据的基本单位，完整地描述一个对象 棋盘中的一个格局（状态），一个考生记录，一个顶点等； 数据项(Data Item)： 组成数据元素的有特定意义的最小单位 考生信息中的学号、姓名。 数据元素是数据项的集合。 数据对象(Data Object)： 具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = 0, 1, 2, 学生数据对象,基本概念和术语,数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 带结构的数据元素的集合。,基本概念和术语,元素集合：D=a1, a

6、2, a3, a4, a5, a6 关系集合： R=, R1= , R2=, R3= , (D,R1) (D,R2) (D,R3),基本概念和术语,形式定义：数据结构是一个二元组 Data_Structures （D，R） D(Data)是数据元素的集合 R(Relation)是D上关系的集合。,基本概念和术语,数据结构：带结构的数据元素的集合。 数据的逻辑结构： 集合结构：同属于一个集合，别无其它关系 线性结构：一对一的关系 树形结构：一对多的关系， 图结构或网状结构：多对多的关系,基本概念和术语,逻辑结构（定义中的关系）： 数据元素之间的逻辑关系 存储结构(物理结构)： 数据结构在计算机中

7、的表示 逻辑结构在存储器中的映像,逻辑结构中的关系的表示,顺序存储（顺序映像） 借助元素的存储位置表示数据元素之间的关系 链式存储（非顺序映像） 借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。,抽象数据类型（ADT）,抽象数据类型: ADT（Abstract Data Type） 一个数学模型及定义在该模型上的一组操作,抽象数据类型,查找 登录 删除 修改,符 号 表,抽象数据类型表示方法,三元组（D，R，P） D：数据对象，具有相同特性的数据元素的集合 R：D上的关系的集合 P：对D的基本操作集 定义格式 ADT 抽象数据类型名 数据对象：数据对象定义 可用伪代码描

8、述 数据关系：数据关系定义 可用伪代码描述 基本操作：基本操作定义 ADT 抽象数据类型名,伪代码是一种用于描述算法的语言，介于高级程序设计语言和自然语言之间。,抽象数据类型例子,元素集合：D=a1, a2, a3, a4, a5, a6 R2=, P1=加法、减法 P2=乘法、除法 (D,R2) (D,R2,P1) (D,R2,P2),基本操作的定义格式,基本操作名（参数表） 初始条件： 操作结果： Add(int a, b) 初始条件：已知a和b 操作结果：返回a与b的和,抽象数据类型（ADT）,ADT的描述方法： 类C语言：伪代码和C语言组合 伪代码：描述算法的语言，介于高级程序设计语言

9、和自然语言之间。 交换赋值用：A B,算法与算法分析,算法： 对特定问题求解步骤的一种描述 指令的有限序列 每一条指令表示一个或多个操作 算法特性： 有穷性：执行有限步，每步有限的时间 确定性：相同输入有相同输出，无二义性 可行性：所有操作可以通过已经实现的基本运算执行有限次来实现的 输入：具有零个或多个输入 输出：具有一个或多个输出,算法设计的原则,算法设计的目标： 正确性：满足预先规定的功能和性能要求 可读性：清晰简洁、层次分明、 易读易懂，注释； 健壮性：当输入不合法的数据时，算法应能进行适当处理，不至于引起严重后果； 高效性：有效使用存储空间和有较高的时间效率。 与问题的规模有关： 时

10、间复杂度 空间复杂度,算法效率的衡量方法及其准则,衡量算法效率的方法主要有两大类： 事后统计： 利用计算机的时钟进行算法执行时间的统计 在算法中的插装时间函数time ( )测定算法完成某一功能所花费时间。 缺陷： 必须把算法转变成为程序执行， 依赖于硬件和软件环境，掩盖算法本身的优劣；,算法效率的衡量方法及其准则,衡量算法效率的方法主要有两大类： 事前分析估算： 需要考虑用程序运行的时间主要取决的因素 算法选用的策略； 问题的规模； 使用语言：级别越高，效率越低； 编译程序所产生的机器代码的质量； 机器执行指令的速度；,后三条与算法设计无关,算法效率的衡量方法及其准则,一个特定算法的“运行工

11、作量”的大小，只依赖于问题的规模（通常用整数量 n 来表示），或者说：它是问题规模的函数。,时间复杂度,随着问题规模 n 的增长，算法执行时间的增长率T(n)和函数f(n)的增长率相同，则可记作为： T(n)=O(f(n) 称T(n)为算法的（渐近）时间复杂度,算法 程序的控制结构（顺序，分支，循环） 原操作（必须的操作）构成,估计算法的时间复杂度,算法的执行时间 原操作(i)的执行次数原操作(i)的执行时间 执行时间 和 原操作执行次数之和成正比 估算： 从算法中选取一种对于算法最基本的原操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 语句频率：重复执行的次数,或者说算法

12、中基本操作重复执行的次数是问题规模n的某个函数f(n),估计算法的时间复杂度,+x; s=0;,时间复杂度,for(j=1;j=n;+j) +x;s+=x;,语句的频度为1时间复杂度O(1) 常量阶,语句的频度为n时间复杂度为O(n)线性阶,时间复杂度,for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,语句频度为nn，时间复杂度为O(n2)。 平方阶,时间复杂度,for(j=1;j=n;+j) for(k=1;k=j;+k) +x;s+=x; 语句频度：,为近似于n2，时间复杂度为O(n2)。,时间复杂度只考虑量级就可以了。,时间复杂度,s=0; for(j=1

13、;j=n;j*=2) for(k=1;k=n;+k) s+; 语句频度为：,时间复杂度为：O(nlog2n),时间复杂度,例：矩阵加法：n n for( i = 0; i n; i+) for( j = 0; j n; j+) cij = aij + bij; ,语句的频度：重复执行的次数：n*n; T( n ) = O ( n 2) 即：矩阵加法的运算量和问题的规模n的平方是同一个量级；,常见的时间复杂度,c log2n n nlog2n n2 n3 2n 3n n!,算法的空间复杂度,算法的空间复杂度： 算法在执行时所占用的存储空间 算法的空间复杂度表示： S(n)=O(g(n) 表示随着

14、问题规模 n 的增大，算法运行所需存储量的增长率与函数g(n)的增长率相同。,算法的空间复杂度,算法的存储量 程序本身所占的存储空间； 输入数据所占的空间 （变量） 辅助变量所占空间 （系统堆栈） 固定部分vs.可变部分,空间复杂度度量,固定部分程序指令代码的空间，常数、简单变量 可变部分 与实例特性有关的成分变量所占空间 引用变量所占空间 递归栈所用空间 通过malloc等命令动态使用的空间,算法的空间复杂度,输入数据所占空间只取决于问题本身和算法无关 只需分析辅助变量所占的额外空间即可。 所需额外空间相对于输入数据量来说只是一个常数 算法为“原地工作”记 O(1)； 算法所需的存储量与特定的输入有关 需要分析时间复杂度,作业,第一章 一 、二题,选做题,我们要做一个城市公交车站点查询系统。为简单起见，假设各