基本概念和术语
- 数据: 是对客观事物的符号表示, 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称
- 数据元素: 是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理(一个数据元素可由若干个数据项组成)
- 数据对象: 是性质相同的数据元素的集合, 是数据的一个子集
- 数据结构(逻辑结构): 是相互之间存在的一种或多种特定关系的数据元素的集合
- 线性结构
- 非线性结构: 集合, 树形结构, 图状结构或网状结构
- 存储结构(物理结构): 数据结构在计算机中的表示(又称映像)
数据元素在计算机中的映像称为元素或结点, 例如通常用一个字长的位串表示一个整数, 通常称这个位串为元素或节点. 当数据元素由若干数据项组成时,位串中对应于各个数据项的子位串称为数据域 * 顺序存储结构(顺序映像) * 链式存储结构(非顺序映像) 算法的设计取决于选定的数据(逻辑)结构, 而算法的实现依赖于采用的存储结构
数据类型: 和数据结构密切相关的一个概念, 最早出现在高级程序语言中, 用以刻画(程序)操作对象的特性
- 原子类型
- 结构类型
抽象数据类型(ADT): 是指一个数学模型以及定义在该模型上的一组操作
- 原子类型
- 固定聚合类型
- 可变聚合类型
后两种可统称为结构类型
多形数据类型: 指其值的成分不确定的数据类型
算法和算法分析
- 5 个重要特性:
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
- 算法的设计要求
- 正确性
- 可读性
- 健壮性
- 效率与低存储量需求
- 算法效率的度量
- 事后统计的方法
- 事前分析估算的方法
- 算法的存储空间需求
如果一个问题所占的输入数据空间是固定的、和算法无关的， 那我们在分析空间复杂度时，只需要关注算法额外使用的空间（也叫辅助空间）