【第一章】绪论

绪论部分纯纯八股文，考研大纲没有，了解即可，不用过多记忆，重点掌握复杂度的分析。

1.1 数据结构的基本概念¶

1.1.1 基本概念和术语¶

数据
- 定义：信息的载体，符号的集合。是计算机程序加工的原料。
数据元素
- 定义：数据的基本单位，通常是一个整体。
- 数据项：构成数据元素不可分割的最小单位。
- 例子：一个学生是一个数据元素，由学号、姓名等数据项构成。
数据对象
- 定义：相同性质数据元素的集合，是数据的一个子集。
- 例子：整数数据对象是集合 $N=\{0, \pm 1, \pm 2, \dots\}$。
数据类型
- 定义：值的集合+处理值操作的总称。
- 类型：
  1. 原子类型：值不可再分的数据类型。
  2. 结构类型：值可以再分成若干份的数据类型。
  3. 抽象数据类型（ADT）：一个数学模型和定义在数学模型上的一组操作。定义了数据的取值范围及其结构形式，以及对数据操作的集合。
数据结构
- 定义：相互存在一种或多种关系的数据元素的集合。
- 结构：数据元素之间的相互关系称之为结构（Structure）。
- 数据结构包括：
  - 逻辑结构
  - 存储结构
  - 数据的运算

一个算法的设计取决于所选的逻辑结构，而实现取决于存储结构。

因为不同的存储方式下可以写出不同的代码，而他们的思想却是相似的。比如要存储一个班级的学生可以采用线性表，同样的线性表逻辑结构，可以有不同的存储结构：链表、数组。

1.1.2 数据结构三要素¶

数据的逻辑结构
- 定义：数据元素之间的逻辑关系，从逻辑关系上描述数据。
- 线性结构
  - 线性表
- 非线性结构
  - 集合
  - 树
  - 图
数据的存储结构
- 定义：数据结构在计算机中的表示（映像），也成物理结构。包括数据元素的关系和关系的表示。
- 数据的存储结构：由计算机语言实现的逻辑结构，依赖于计算机语言（例如：不同语言的数组实现方式不同）。
- 分类：
  - 顺序存储
    - 特点：逻辑相邻，物理位置也相邻。
    - 优点：可以实现随机存取。
    - 缺点：可能产生外部碎片。
  - 链式存储
    - 特点：没有碎片现象。
    - 优点：没有碎片现象。
    - 缺点：存储指针浪费额外空间。
  - 索引存储
    - 特点：存储信息的同时建立索引表。
    - 索引项：索引表中的每一项。一般形式为（关键字，地址）。
    - 优点：检索速度快。
    - 缺点：增加和删除数据需要维护索引表，花费时间。
  - 散列存储（哈希 Hash 存储）
    - 特点：根据元素关键字直接计算出存储地址。
    - 优点：检索、增加和删除操作都很快。
    - 缺点：散列函数不好可能出现元素存储单元的冲突，解决冲突则增加时间和空间开销。
数据的运算
- 定义：包括运算的定义和实现。
- 运算的定义：针对逻辑结构。指出运算的功能。
- 运算的实现：针对存储结构，指出运算的具体操作步骤。

1.2 算法和算法的评价¶

1.2.1 算法的基本概念¶

定义：算法（Algorithm）是对特定问题求解步骤对一种描述，它是指令的优先序列，每条指令表示一个或多个操作。算法的五个重要特性：

有穷性。
- 一个算法必须在执行有穷个步骤后结束，每一步都可以在有穷时间内完成。
确定性。
- 每条指令有确定含义，相同输入只能得到相同的输出。
可行性。
- 算法中描述的操作都可以通过已经实现的基本运算执行有限次来完成。
输入。
- 一个算法有零个或多个输入。
输出。
- 一个算法有一个或多个输出。

一个好的算法的目标🎯： - 正确性。 - 正确解决问题。 - 可读性。 - 良好可读性，帮助人类理解。 - 健壮性。 - 对非法数据做出反应，不会产生莫名其妙的输出。 - 高效率与低存储量需求。 - 效率：算法的执行时间。 - 存储量需求：算法执行过程中需要的最大存储空间。

1.2.2 算法效率的度量¶

算法基础概念题中一定会有的，对时间复杂度的分析。

时间复杂度
语句的频度：
- 语句在算法中被重复执行的次数。
频度之和：
- $T(n)$
- $n$：算法问题规模。
时间复杂度
- 定义：算法中基本运算的执行次数的数量级。
- 目的：主要分析 $T(n)$ 的数量级。
- 记为：$O(f(n))$
- $O$：表示数量级。
- 严格的数学定义：
  - 若 $T(n)$ 和 $f(n)$ 是定义在正整数集合上的两个函数，则存在正常数 $C$ 和 $n_{0}$ ，使得当 $n\geq n_{0}$ 时，都满足 $0\leq T(n)\leq Cf(n)$。
- 分类：
  - 最坏时间复杂度。
    - 一般总是考虑最坏情况。
  - 最好时间复杂度。
    - 最好情况下算法时间复杂度。
  - 平均时间复杂度。
    - 算法的期望运行时间。

这里引入常数 $C$ 的意义：明确定义了常数 $C$ 不改变数量级。

时间复杂度的运算规则： - 加法规则： - $T(n)=$ - $T_{1}(n)+T_{2}(n)=$ - $O(f(n))+O(g(n))=$ - $O(max(f(n),g(n)))$ - 乘法规则： - $T(n)=$ - $T_{1}(n)\times T_{2}(n)=$ - $O(f(n))\times O(g(n))=$ - $O(f(n)\times g(n))$

对于加法规则的一个例子：

// a: O(1)
a {
    b {}    // b: O(n^2)
    c {}    // c: O(n)
}

最终复杂度为 $O(1\times O(max(n^{2}, n)))=O(n^{2})$

对于乘法规则的例子：

a { // a: O(1)
    b {    // b: O(n^2)
        c { }    // c: O(n)
    }
}

最终复杂度为 $O(n^{2}\cdot n\cdot 1)=O(n^{3})$

常见渐进时间复杂度：

\[ O(1)<O(\log_{2}n)<O(n)<O(n\log_{2}n)<O(n^{2})<O(n^{3})<O(2^n)<O(n!)<O(n^n) \]

空间复杂度

符号：$S(n)$ 定义：算法所需的存储空间。记为：

$$ S(n)=O(g(n)) $$ 例如：使用了与数据规模 $n$ 相同的辅助数组，则空间复杂度为 $O(n)$。 算法原地工作：指需要的辅助空间为常量，即 $O(1)$。