1. 绪论
1.1 概述
- 算法 +数据结构= 程序
- 程序：计算机指令的组合
- 算法：程序的逻辑抽象
- 数据结构：数据及其关系的反映，从逻辑结构和存储(物理)结构。
- 数据结构解决具体问题：
- 数据的逻辑结构（数学模型）
- 数据的存储结构
- 数据操作与运算
1.2 数据与数据结构
1.2.1 术语
- 数据（Data）：数据是信息的载体，是对客观事物的符号表示。
- 数据元素（Data Element）：是数据的基本单位，是一个个体。相当于表的一行。
- 数据项（Data Item）：是数据元素的组成部分。相当于表的列。
- 数据对象（Data Object）：性质相同的数据元素的集合。相当于表。
- 数据结构（Data Structure）：特定关系的数据元素的集合。
1.2.2 逻辑结构
- 逻辑结构：数据元素之间的逻辑关系，与数据存储无关，独立与计算机之外。
- 数据元素按照特性：
- 集合：元素之间没有关系，比较松散
- 线性结构：元素之间存在==一对一==关系。除了开始和终端结点，其他结点由有一个前驱和一个后继。
- 树形结构：元素之间存在==一对多==关系。
- 图形结构：元素之间存在==多对多==关系。
- 数据的逻辑结构需要2部分：数据元素（data）、数据元素的关系（relationship）
1.2.3 存储结构：
- 存储结构：数据的存储结构，也称为物理结构，是数据的逻辑结构在计算机的实现。
- 数据元素的值存储表示和逻辑关系。
存储结构的4种方式：
- 顺序存储：在一片连续的存储空间中进行存储，元素的逻辑位置和物理位置保持一致。例如：数组
链式存储：可以存储在任意的物理物质上，需要额外的部分存放逻辑关系的指针。例如：链表
- 索引存储：存储数据的同时，额外的存储一个索引表。在查询时可以提高效率。
- 散列存储：一般情况物理上可以是连续的存储空间，需要通过
散列函数hash来确定存储位置。在查询时可以提高效率。
1.2.4 数据操作：
- 初始化：创建、销毁：
- 数据操作：插入/添加、删除、修改
- 数据使用：查找、遍历
1.3 算法
- 算法：对特定问题求解步骤的一种描述。是指令的有限序列。
1.3.1 算法特性
- 有穷性：有限
- 确定性：需求确定、指令确定
- 有效性：指令都是由意义
- 输入：
- 输出：
1.3.2 算法目标
- 正确性：基本要求，需求和实现对应。
- 可读性：使程序员能够读懂，编写代码时可以辅助注释。
- 健壮性：临界值的处理、无效数据的校验等。
- 高效性：使用较少的资源（资源分2种：时间资源、空间资源）。一个好的算法要做到执行时所需时间尽量短，所需的最大存储空间尽量少。
1.3.3 算法分析：概述
- 算法的复杂度是衡量算法优劣的重要依据。
- 算法的复杂度分类：时间复杂度、空间复杂度。
- 时间复杂度：执行时间的长短。
- 空间复杂度：执行时空间需求量，也就是计算机资源的使用量。
1.3.4 算法分析：时间复杂度（大O）
- 主要考虑因素：
- 算法本身
- 问题规模
- 程序语言选择
- 编译程序（JDK优劣）
- 硬件速度
- 运行软件
- 时间复杂度通过
大O表示法进行表示的
- 大O表示法，用于估算一个算法的执行时间。
- 算法执行时间：Σ(指令的执行次数 * 指令的执行时间)。
指令的执行时间是固定的，可以不考虑。只需要考虑指令的执行次数即可。- 大O表达法，通过统计
指令的执行次数，就可以估算出一个算法的优劣。 指令的执行次数：每行代码执行的次数，将所有的次数累加在一起即可。- 例如1.7：2n^3 + 3n^2+2n+1 总次数表达式 --> 只考虑最高次幂 --> O(n^3)
- 大O表达式只需要考虑最高次幂的项。
2.大O表达式常见的形式
- 常量阶：O(1) ，执行的次数与输入无关。
- 线性阶：O(n) ，执行的次数与输入成正比关系。例如：一层循环。
- 平方阶：O(n^2) ， 执行的次数与输入成平方关系。例如：二层循环
- 立方阶：O(n^3) ，执行的次数与输入成立方关系。例如：三层循环
- 对数阶：O(log2n) ， 执行的次数与输入成开方关系。例如：求对数 log28 = 3
- 线性对数阶：O(nlog2n)
- O (n) ：一层循环
- O(n^2)：二层循环（99乘法表）
intn=9; for(inti=0 ; i<n ; i++) { for(intj=0 ; j<n : j++) { // 次数 n*n } }
O(n^3)：三层循环
intn=9; for(inti=0 ; i<n ; i++) { //时针for(intj=0 ; j<n : j++) { //分针for(intm=0 ; m<n ; m++) { //秒针// 次数 n * n * n } } }
1.3.5 算法分析：最好、最坏、平均
- 实例：从数组中获得内容 a[1...n]
- 最好时间复杂度：获得最好的情况，例如：数组中的第一个数据。O(1)表示此情况。
- 最坏时间复杂度：获得最坏的情况，例如：数据中最后一位。O(n)表示此情况。
- 平均时间复杂度：
- 1+...+n和 ： (n+1) * n/2
- 平均，和/n ：(n+1) * n/2 / n ---> (n + 1) / 2 --> O(n)表示
- 结论：在一般情况下，取
最坏时间复杂度或等概率下的平均时间复杂度作为算法的时间复杂度。
1.4 回顾：西格玛Σ 求和
