简介
什么是数据结构
- 数据 是对客观事物的符号表示
- 数据元素 是数据的 基本单位
- 数据对象 是性质相同的数据元素集合
数据结构 是相互之间存在一种或者多种特定关系的数据元素的集合
基本的四种结构：
- 集合 结构中的数据之间除了 同属于一个集合的关系外，别无其它关系
- 线性结构 结构中的数据元素之间存在一个对一个的关系
- 树形结构 结构中的数据元素之间存在一个对对个的关系
- 图状结构或网状结构 结构中的数据存在多个对多个的关系
数据类型 用以刻画操作对象的特性
抽象数据类型 (abstract data type ADT) 指数据模型以及定义在该模型上的一组操作
什么是算法
算法 是对特定问题求解步骤的一种描述 特性
- 有穷性 一个算法必须总是在执行有穷步之后结束 且每一步都可在有穷时间内完成
- 确定性 每一条指令必须有确切的含义
- 可行性 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
- 输入 一个算法有零或多个的输入
- 输出 算法有一个或多个输出
算法的要求： 正确性 可读性 健壮性 效率与低存储需求
时间复杂度 随着问题规模n的增大 算法执行时间的增长率和 f(n)增长率相等 渐近时间复杂度
空间复杂度 需要存储空间来寄存本身的指令，也需要对一些数据进行操作的工作单元和存储实现计所需信息的辅助空间