1 基本概念
1.1 什么是数据结构
1.1.1 算法效率
与解决问题的效率相关的几个因素：
- 数据结构的组织形式
例子：图书的摆放
实现方法：随便放、字母排列顺序放、按类别摆放
- 空间的使用
例子：printN
实现方法：for循环、递归
- 算法的巧妙程度
C语言计时：clock()函数，CLK_TCK为机器时钟每秒所走的打点数
例子：计算多项式值
实现方法：传统方法、秦九韶算法
1.1.2 数据结构定义
数据结构：数据对象在计算机中的组织方式，可以使用抽象数据类型（ADT）描述。
- 逻辑结构
- 物理存储结构
要点：
- 数据对象必定与一系列加在其上的操作相关联
- 完成操作的方法称为算法
抽象数据类型：
-
数据类型：
- 数据对象集
- 操作集
-
抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言无关
1.2 什么是算法
1.2.1 算法定义
算法：
- 一个有限指令集
- 接受一些输入
- 产生输出
- 一定在有限步骤之后终止
- 每条指令必须满足：
- 有充分的明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述应不依赖于任何计算机语言以及具体的实现手段
1.2.2 算法效率指标
空间复杂度S(n)：根据算法写成的程序在执行时占用的存储单元的长度。
时间复杂度T(n)：根据算法写成的程序在执行时耗费时间的长度。
1.2.3 算法复杂度的渐进表示法
表示f(n)是T(n)的一个上界；
表示f(n)是T(n)的一个下界。
常见的复杂度：
其中对于通常会考虑能否变为
。
- 对于 for 循环的复杂度，等于循环次数乘以循环体的复杂度。
- if-else 结构的复杂度取决于 if 的条件判断和两个分支部分的复杂度，总体复杂度取三者中最大的。
