文档介绍：数据结构与算法
第1章绪论
基本内容
1
相关练习
2
基本内容
基本概念与术语
数据→数据元素→数据项
数据:对客观事物的符号表示
数据元素:数据的基本单位,在计算机程序中作为一个整体处理。
数据项:数据的不可分割的最小单位。
数据对象
性质相同的数据元素的集合。分有限集和无限集。
基本内容
数据结构
相互之间存在一种或多种特定关系的数据元素的集合。
由数据元素之间关系的不同,数据结构分为四类:
(1)集合:数据元素之间的关系是松散的
(2)线性结构:数据元素之间的关系是一对一的关系
(3)树形结构:数据元素之间的关系是一对一的关系
(4)图状结构:数据元素之间的关系是一对一的关系
基本内容
逻辑结构
从操作对象抽象出的数学模型。
物理结构,也称存储结构
数据结构在计算机中的表示(又称映像)。包括数据元素的表示和关系的表示。
数据元素之间不同的关系,得到
顺序映像
非顺序映像
顺序存储
链式存储
两种结构是密切相关的两个方面,任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的存储结构。
基本内容
数据类型
是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型
是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。
一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。
抽象数据类型的表示与实现是通过类C语言实现的。
基本内容
算法与算法效率
算法的定义
是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每条指令表示一个或多个操作。
算法的特性
(1)有穷性(2)确定性(3)可行性(4)输入(5)输出
算法设计的要求
(1)正确性(2)可读性(3)健壮性(4)效率与低存储量需求
基本内容
算法效率的度量
两种方法: (1)事后统计的方法(2)事前分析估算的方法
通常做法是:从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该操作重复执行的次数作为算法的时间量度。
时间复杂度
算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作:T(n)=O(f(n)),它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。
基本内容
时间复杂度的分类及计算
分类:(1)常量阶:O(1) (2)线性阶:O(n) (3)平方阶:O(n2)
(4)对数阶:O(logn) (5)指数阶:O(2n)
计算:(1)一般情况取一种运算,有时需要取算法中的几种运算。
(2)在难于精确计算原操作的执行次数时,只求出关于n的增
长率。
(3)求最坏情况下的时间复杂度。
空间复杂度
除了用来存储算法本身所需要的存储空间外,其它所需要的辅助空间,称为算法的空间复杂度。记作:S(n)=O(f(n))。
原地工作:额外空间相对于问题的规模而言是常量。
相关练习
一、选择题:
1、算法的时间复杂度取决于( )。
B .待处理数据的初态 C .A和B
2、下面关于算法说法错误的是( )。
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(4)同一个算法,实现语言的级别越高,执行效率就越低
A.(1) B.(1),(2) C.(1),(4) D.(3)
C
A