文档介绍：算法与数据结构
主讲教师: 葛日波
联系方式: teacher_******@dlut.
82172108
办公室: 教学楼1904
主要内容
第1章绪论
(1)数据的逻辑结构
(2)物理结构
(3)对数据的操作(算法设计)
(3)数据结构
相互之间存在一种或多种特定关系的数据元素的集合
不同的元素或不同的关系,构成不同种类的数据结构
含逻辑结构和物理结构
(1)数据
信息的载体,它能够被计算机识别、存储和加工处理
(2)数据元素
数据的基本单位,也称为结点、顶点、记录
(5)物理结构(存储结构)
逻辑结构的机内表示
同一种逻辑结构可以有多种物理结构
算法的设计取决于逻辑结构,实现取决于物理结构
(4)逻辑结构
数据元素之间的逻辑关系
通常是前后位置关系,又叫前后件关系
分线性结构和非线性结构
(1)集合表示
数据结构是一个二元组: B = (D,S)
D是数据元素的有限集,S是D上关系的有限集
关系用序偶<ai,aj>或无序对(ai,aj)表示
ai称为前驱或弧尾,aj称为后继或弧头
如: 教材P6-习题1
D = {a,b,c,d,e,f} R = {r}
(1)r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}
(2)r={<a,b>,<b,c>,<b,d>,<d,e>,<d,f>}
(3)r={<a,b>,<b,c>,<d,a>,<d,b>,<d,e>,<e,f>}
(2)图形表示
以结点为顶点,用弧(或边)连接
a
b
c
d
e
f
a
b
c
d
e
f
a
b
c
d
e
f
线性结构
非线性结构
(1)有穷性
(2)确定性
(3)可行性
(4)0个或多个输入
(5)1个或多个输出
算法是为了解决特定问题的有限的操作步骤的描述
(1)正确性(correctness)
(2)可读性(readability)
(3)健壮性(robustness)
(4)高效性(efficient)
(2)算法的时间复杂度一般用简单操作执行的次数来度量
(3)一个特定算法运行的工作量只依赖于问题的规模,它是问题规模的函数
(4)随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作: T(n)= O(f(n)),称T(n)为算法的(渐近)时间复杂度
(1)算法的时间复杂度是指运行算法所消耗的时间
(5)常见复杂度及关系
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
O(2n)<O(n!)<O(nn)