# 数据结构-第一章-数据结构的基本概念
# 数据结构的基本概念
# 基本概念和术语
- 数据
- 数据元素
- 数据类型等
# 数据结构三要素
# 逻辑结构
- 线性结构
- 线性表
- 栈
- 队列
- 非线性结构
- 树
- 图
- 集合
# 存储结构
- 顺序存储
- 链式存储
- 索引存储
- 散列存储
# 运算
# 算法与算法评价
# 1. 算法
对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
# 算法五大性质
- 有穷性
- 可行性
- 确定性
- 输入
- 输出
# 2. 程序
程序是某种程序设计语言对算法的具体实现。
# 3. 算法的评价
# “好”算法的定义
- 正确性
- 可读性
- 健壮性
- 效率与存储量
# 时间复杂度
语句频度
该条语句可能重复执行的次数
T(n)
所有语句的频度之和，其中n为问题的规模
时间复杂度
T(n)=O(f(n)),其中O表示T(n)与f(n)在n->正无穷时为同阶无穷大(既相等)
- 加法规则
T(n)=T1(n)+T2(n)=o(f(n))+o(g(n))=o(max(f(n),g(n)))
- 乘法规则
T(n)=T1(n)*T2n(n)=O(f(n))*o(g(n))=o(f(n)*g(n))
- 通常采用基本运算频度来分析时间复杂度
- 时间复杂度常用排序
- o(1)<o(log2n)<o(n)<o(nlog2n)<o(n^2)<o(n^3)<o(2^n)<o(n!)<o(n^n)
# 空间复杂度
算法消耗的存储空间，记S(n)=o(g(n)) 除本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储为实现算方法所需要的一些信息的辅助空间。
- 算法原地工作时指算法所需辅助空间为常量，o(1)