引言
计算机解决问题的步骤
1. 从具体的问题抽象出一个适当的数学模型
2. 设计一个求解该数学模型的算法
3. 用计算机语言编写实现该算法的程序, 调试和运行程序直至最终得到问题的解答
数据结构 (Data Structure)
数据结构是组织数据和存储数据的方式
数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式, 以及定义在该组数据上的一组操作.
数据的逻辑结构
数据及数据的组织方式被称为逻辑结构
数据结构和算法和程序的关系
程序 = 数据结构 + 算法
基本概念和术语
数据 (Data)
所有能被计算机存储处理的对象
数据元素 (Data Element)
数据为集合, 集合当中一个个的个体即为该集合的一个元素. 数据元素是数据的基本单位
数据项 (Data Item)
数据元素常常还由若干个数据项组成. 它是数据不可分割的最小标识单位.
数据的逻辑结构 (Logical Structure)
数据元素之间的结构关系
逻辑关系: 指数据元素之间的关联方式或邻接关系
集合
任意两个点之间都没有邻接关系, 组织形式松散
线性结构
结点按逻辑关系依次排列成一条链, 结点之间一个一个依次相邻接.
树形结构
具有分支, 层次特性, 上层的结点可以和下层多个结点相邻接, 但下层结点只能和上层的一个结点相邻接.
图结构
最复杂, 任意两个结点都可以相邻接
数据的存储结构 / 数据的物理结构 (Physical Structure)
数据的逻辑结构在计算机中的实现称为数据的存储结构(物理结构)
数据结构的存储 = 数据元素的存储 + 逻辑关系的存储
顺序结构
顺序存储方式: 借助数据元素的相对存储位置来表示数据的逻辑关系
方法: 将所有存储结点存储到一片连续的存储区
特点
1. 预先分配好长度, 需要预估存储数据需要的存储量
2. 插入和删除需要移动其它元素
3. 存取快捷, 是随机存取结构链式结构
链式存储方式: 借助数据元素地址的指针表示数据的逻辑关系
存放结点的存储单元分为两部分: 数据项 | 指针项
特点
1. 动态分配, 不需要预先确定内存分配
2. 插入和删除不需要移动其它元素
3. 非随机存取结构索引存储方式
索引存储方式: 借助索引表中的索引指示各存储结点的存储位置
散列存储方式
散列存储方式: 用散列函数指示各结点的存储位置
运算
指在某种逻辑结构上施加的操作, 即对逻辑结构的加工
加工型运算
其操作改变原逻辑结构的值. 如: 结点个数, 结点内容等.
引用型运算
其操作不改变原逻辑结构的值.
基本运算
1. 建立
2. 查找
3. 读取
4. 插入
5. 删除算法及描述
算法规定了求解给定类型问题所需的所有处理步骤和执行顺序, 使给定类型问题在有限时间内被求解
一个算法是对特定问题求解步骤的一种描述, 它是指令的有穷序列.
特性
1. 有穷性: 一个算法总是在执行有穷步后结束
2. 确定性: 算法的每一步都必须是明确定义的
3. 可行性: 算法中的每一步都是可以通过已经实现的操作来完成的
4. 输入: 一个算法有零个或者多个输入, 这些输入取自于特定的对象集合
5. 输出: 一个算法有一个或者多个输出, 它们是与输入有特定关系的量算法分析
算法的设计应满足
- 正确性: 对于合法的输入产生符合要求的输出
- 易读性: 算法应易读, 便于交流, 这也是保证算法正确性的前提 (如: 添加注释)
- 健壮性: 当输入非法数据时, 算法还能做出适当的反应而不会崩溃. 如: 输出错误信息; 算法中应该考虑适当的错误处理.
- 时空性: 指算法的时间复杂度和空间复杂度, 算法分析主要分析算法的时间复杂度和空间复杂度, 目的是提高算法的效率
时间复杂度
算法运行时需要的总步数, 通常是问题规模的函数
确定算法的计算量
合理地选择一种或几种操作作为标准操作
无特殊说明, 默认以赋值语句作为标准操作.
确定每个算法共执行多少次标准操作, 并将此次数规定为该算法的计算量
算法的最坏情况时间复杂度
以算法在所有输入下的计算量的最大值作为算法的计算量
算法的平均情况时间复杂度
以算法在所有输入下的计算量的加权平均值作为算法的计算量
渐近时间复杂度
T(n) = O(f(n))
f(n)为问题规模n的某个函数
大O表示法也称为渐进表示法
T(n)称为算法的渐进时间复杂度, 简称时间复杂度
常见的时间复杂度按数量级递增排列依次为
O(1) < O(log2(n)) < O(n) < O(nlog2(n)) < O(n^2) < O(n^c) < O(2^n)
常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 多项式阶 < 指数阶
通常认为:
常数阶O(1), 算法的时间复杂度与输入规模n无关
具有指数阶的算法是实际不可计算的
阶数低于平方阶的算法是高效率的
空间复杂度
S(n) = O(g(n))
g(n)为问题规模n的某个函数
算法执行时所占用的存储空间, 通常是问题规模的函数
是对一个算法在运行过程中临时占用存储空间大小的量度.
一个算法在执行期间所需要的存储空间量包括以下部分
1. 程序代码所占用的空间
2. 输入数据所占用的窠
3. 辅助变量所占用的空间我们在估算空间复杂度时, 一般只分析辅助变量所占用的空间