预计2025.03.07，完成优化/完善该内容，敬请期待！！！

（以下为学习过程中的粗略知识点，还未经过优化/完善，后续会变成更有条理的形式！！！）

8.1 时间复杂度与空间复杂度

8.1.1 时间复杂度

如下列举了常用的几种时间复杂度，以及它们之间的大小关系：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。

1.倘若你能够确定循环的次数，即最后执行的次数是一个常数，和n无关，那么其就是常数阶，即O(1)

2.二分查找时间复杂度：最好的情况：一次就找到，那就是O(1);

最坏的情况：最后一次才找到。假设找了x次，有n个元素，则n/2/2/2/2.../2=1，那么/2这个运算进行了x次。所以n = 2^x，所以x = logn，即它的最坏情况下的时间复杂度为O(logn)。它的平均查找的时间算法复杂度实际上也是O(logn)，这个具体的算法我们在后面再讲。

因此，该二分查找的算法的复杂度为O(logn)

3.斐波那契数列：它的算法的时间复杂度是O(2^n)

8.1.2 空间复杂度

1.我们空间复杂度的判断标准是看变量的个数，或者是变量所用空间的个数。从上面的展示可以看出，这里的变量是常数个。因为就count一个。所以，它的算法的空间复杂度为O(1)。

2.它递归调用了n次。我们在C语言的函数部分介绍过，函数的每一次递归调用都会为新的函数重新开辟一个栈帧，上一级的函数由于并未结束，所以上一级的函数的栈帧并未被销毁。所以在调用下一级的函数的时候，就不得不在新的位置重新为其开辟栈帧。

所以，它的空间可以理解为开辟了n次。

粗暴理解就是：每个函数都要有参数值、返回值等一系列的寄存器变量来去维护它。要完成这个算法，这些变量需要开辟n次。

所以，该算法的空间复杂度为O(N)。

如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;

如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；

如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示； 等等。

在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。

8.2 线性结构与非线性结构

8.2.1 线性结构（线性表）

数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。线性结构是一个有序数据元素的集合。

线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。

顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。

队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。

常用的线性结构有 线性表，栈，队列，双队列，循环队列，一维数组，串

线性表第一个元素位表头，最后一个元素为表尾，另外，某个元素的前面一个元素，称为该元素的前驱；该元素的后面一个元素，成为该元素的后继

某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；

某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

8.2.2 非线性结构

非线性结构中各个数据元素不再保持在一个线性序列中，数据元素之间是一对多，或者是多对一的关系。根据关系的不同，可分为层次结构（树）和群结构（图）。

树存储结构适合存储具有“一对多”关系的数据。

图存储结构适合存储具有“多对多”关系的数据。

常见的非线性结构有二维数组，多维数组，广义表，树(二叉树等)，图。（其中多维数组是由多个一维数组组成的， 可用矩阵来表示，他们都是两个或多个下标值对应一个元素，是多对一的关系，因此是非线性结构。）

8.3 链表和数组的区别和作用

1. 数组和链表的定义

数组和链表是两种不同的数据存储方式

数组的定义

数组是一组具有相同数据类型的变量的集合，这些变量称之为集合的元素

每个元素都有一个编号，称之为下标，可以通过下标来区别并访问数组元素，数组元素的个数叫做数据的长度

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的特性是在中间任意位置插入和删除元素都非常快，不需要移动其它元素

对于单向链表而言，链表中的每一个元素都要保存一个指向下一个元素的指针

对于双向链表而言，链表中的每个元素既要保存指向下一个元素的指针，又要保存指向上一个元素的指针

对于双向循环链表而言，链表中的最后一个元素保存一个指向第一个元素的指针

8.4 逆波兰表达式

逆波兰表达式（Reverse Polish Notation，简称 RPN），也称为后缀表达式，是一种算术表达式的表示方法，它将操作数放在操作符之前。相较于传统的中缀表达式，逆波兰表达式不需要括号来改变运算顺序，因为它的运算顺序是由表达式的排列方式自然决定的。

### 逆波兰表达式的特点

1. **没有括号**：由于运算的优先级和顺序是通过操作符的位置确定的，不需要括号。

2. **从左到右计算**：表达式按照从左到右的顺序进行计算。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

### 示例

#### 中缀表达式到后缀表达式的转换

1. **中缀表达式**：`3 + 4 * 2 / ( 1 - 5 )`

2. **后缀表达式**：`3 4 2 * 1 5 - / +`

#### 计算步骤

1. **输入**：`3 4 2 * 1 5 - / +`

2. **计算过程**：

- 读取 `3`，将其压入堆栈。

- 读取 `4`，将其压入堆栈。

- 读取 `2`，将其压入堆栈。

- 读取 `*`，将顶部两个元素 `4` 和 `2` 弹出，计算 `4 * 2 = 8`，将结果 `8` 压入堆栈。

- 读取 `1`，将其压入堆栈。

- 读取 `5`，将其压入堆栈。

- 读取 `-`，将顶部两个元素 `1` 和 `5` 弹出，计算 `1 - 5 = -4`，将结果 `-4` 压入堆栈。

- 读取 `/`，将顶部两个元素 `8` 和 `-4` 弹出，计算 `8 / -4 = -2`，将结果 `-2` 压入堆栈。

- 读取 `+`，将顶部两个元素 `3` 和 `-2` 弹出，计算 `3 + (-2) = 1`，将结果 `1` 压入堆栈。

8.5 字符串

KMP主要应用在字符串匹配上。

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

求最长相等前后缀，找前面字符串的最长相同的前缀和后缀。

移动匹配

我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

8.6 树

8.6.1 树的基本术语

将会以此树，来对以下基本术语进行举例。

1、结点：数据元素+若干指向其子树的分支；这里的A、B、C等都可以看成是一个结点。所谓指向若干结点的分支，则可以理解为是该结点的指针域。

2、结点的度(degree) ：结点拥有的子树数；比如，在上图中，结点A的度数是3，结点B的度数是2。

注意，我们这里和离散数学里的度有所区别，因为离散数学中的数是从图中引过来的，所以它的度的概念就沿用了图中的度（当然你如果不知道这点，那你就不用关心，你就记得这里的就好啦）

3、树的度：树中所有结点的度的最大值；很好理解，就是把树中所有的结点的度数的最大值挑出来，然后它就是整棵树的度了。

4、叶子结点(leaf)：度为零的结点，或称为终端结点；比如，在上图中，K、L、F、G等都是叶子结点。

5、分支结点：度大于零的结点，或称为非终端结点；就是说，如果它不是叶子结点，那么它就是分支结点。

6、结点的层次(level)：假设根结点的层次为1, 若某结点在第i层，则其子树的根在第i+1层。例如，上图中的B是在第二层；M在第四层。

7、树的深度（或高度）Depth：树中叶子结点所在的最大层次。比如在上图中，树的高度就是4。

8、孩子结点(Child)：结点的子树的根；相应地该结点称为孩子的双亲结点（或者父亲结点）(Parent)。比如说，在上图中，我们可以认为，A是B的双亲（或者叫父亲结点）；