绪论

基本概念和术语

• 数据
数据（Data）是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

• 数据元素
由多个数据项组成的一个小单位，又称元素，结点

• 数据对象
具备相同性质的数据元素的集合

• 数据结构
有某一数据对象及该对象中的元素关系构成，记为
包括了数据元素集合和关系集合

• 逻辑结构
面向用户的，属于用户的视图，面向问题的，表示数据元素间的逻辑关系。

• 存储结构
是指数据如何在计算机中存放，面向计算机本身

• 运算
运用在数据结构上的运算，包括（查找，插入，删除，更新等）

求解问题的过程

数据结构的逻辑结构

• 集合结构：属于一个集合，但没有其他关系

• 线性结构：数据元素的有序序列

• 树形结构：每个节点只有一个父节点。除了根元素外，每个节点有且仅有一个前趋，后继数目不限，1对多。

• 图形结构：前驱和后继都不一定

数据的存储结构

• 顺序存储：所有元素按顺序储存，在计算机里依然连续存储

• 链式存储：所有元素依次序放在可以不连续的存储单元中（计算机中）

• 索引存储（间接寻址）：元素表中的每个元素也可以存储在存储器的不同区域中；元素地址则被收集在一张表中，该表的第i项指向元素表中的第i个元素，这张表是一个用来存储元素地址的表。

• 散列存储：构造散列函数，用函数的值来确定存储位置

That is to say,

📌
散列和索引的区别在于散列存储不需要存储地址（映射表），只需要一个函数。

数据的运算

• 搜索

• 创建

• 清除

• 删除

• 插入

• 更新：修改数据结构中的某个元素的值

• 访问：访问数据结构中的某个元素

• 遍历：按照某种次序访问数据结构中的每一元素，使每个元素恰好被访问一次

抽象数据类型ADT

• 由用户定义，用以表示应用问题的数据模型

• 由基本的数据类型组成，并包括一组相关的服务（或称操作）

• 抽象：抽取反映问题本质的东西，不涉及具体实现细节

• 支持了逻辑设计和物理实现的分离，支持封装和信息隐蔽

• ADT可以看作一个三元组

• 设计者的角度：
根据问题来定义抽象数据类型所包含的信息，给出其相关功能的实现，并提供公共界面的接口。

• 用户的角度：
使用公共界面的接口对抽象数据类型进行操作，不需要考虑其物理实现。对于外部用户来说，抽象数据类应该是一个黑盒子。

算法与算法设计

• 算法：一个有穷的指令集，为了解决某一个特定序列而规定的一个特定序列操作
• 描述方式：
• 自然语言
• 流程图
• 伪语言
• 类语言：如类PASCAL，类C语言
• 五个重要特性
• 输入：有0或者多个输入
• 输出：有一个或者多个输出
• 确定性：每个语句确切无歧义
• 有穷性：应该在执行有穷步骤后停止
• 有效性：每条运算应该足够基本
⚠️
1：一条语句遇到两次相同输入，应给出相同的结果。 3：算法中所有操作都必须可以通过已经实现的基本操作及基本运算，并在有限次内实现。 2：算法不能陷入无限循环。例如求pi 的精确解，由于是无穷位的数，所以可以称为计算方法，而不能是算法。
• 算法的效率
• 时间代价
• 空间代价
• 衡量方法
• 后期测试：收集数据，统计资料
• 事前估计：求出该算法的一个时间函数
算法的复杂性度量就是事前估计！包括空间复杂度和时间复杂度。
⚠️
为什么不用绝对时间来衡量时间复杂度
• 一个编程实现了的算法的绝对运行时间，不仅和算法本身相关，还和其他因素密切相关：机器性能、编程语言、编译器、编程技巧等
• 在分析一个算法的运行时间时，通常将该算法和其他算法在同一问题、甚至是不同的问题上进行比较，因而运行时间只能是相对的，而不是绝对的。
• 希望算法的描述不仅独立于机器，并且可以以任何语言来加以描述，包括自然语言。
• 希望使用度量算法运行时间的准则不依赖于软硬技术的进步。
• 不仅仅关注小规模输入下的，而且还关注在大规模输入下的情形。
• 算法的渐进分析
• 渐进的时间复杂度
• 一个算法的“运行时间”通常是随问题规模的增长而增长，它是问题规模（用正整数n表示）的函数。
• 统计算法中的关键操作，以关键操作重复执行的次数作为算法的时间度量。
• 算法中关键操作重复执行的次数是规模n的某个函数 ，称为算法的（渐近）时间复杂度。
• 要精确地计算通常较困难。
• 渐进时间复杂度——算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间度量记作：
• 随着问题规模n的增长，算法执行时间的增长率和的增长率相同。
⚠️
此时我们关注阶数最大的一项，因为这才matter。
例如：
• 若语句很少执行，且与规模无关，则可忽略不计。
• 若所有语句都与规模无关，即使有上千条语句，其执行时间也不过是一个较大的常数，时间复杂度也只是)。
• 一般可只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等。 通常用表示常数计算时间。常见的渐进时间复杂度有:
⚠️
O关注的是算法的一个上界，即算法的最坏情况，而不关注最优状态下的情况
 
• O的几条规则
• 加法规则：针对并行程序段
• 乘法规则：针对嵌套程序段
• 乘法规则中的常数无关项
其中， 表示常数计算时间。
• 最坏、最好和平均情况
1. 大表示法 即给出了时间复杂度的上界，即最坏情况。
2. 大表示法给出了时间复杂度的下界，即最好情况。
3. 大表示法 这里， 表示在平均情况下，算法的运行时间既不会低于 的某个常数倍，也不会高于 的某个常数倍。
• 空间复杂度的渐进分析
• 为算法的(渐近)空间复杂度
• 当实例特性n充分大时，需要的存储空间将如何随之变化。
• 这里所说得是为解决问题所需要的辅助存储空间