（嵌入式八股）第8章 数据结构(一)

8.1 时间复杂度

时间复杂度是衡量算法效率的重要概念，它描述了算法的运行时间随着输入规模 nnn 增长的变化趋势。

1. 常数阶 O(1)

定义：如果算法的运行时间不随输入规模 nnn 变化，而是一个固定的常数，则它的时间复杂度是 O(1)。

示例：

特点：

运行时间固定

不受输入规模影响

极其高效

2. 对数阶 O(log⁡n)

定义：如果算法的运行时间随着输入规模的增加而按对数增长（通常以 2 为底），则时间复杂度为 O(log⁡n)。

典型示例：

二分查找（Binary Search）

折半问题

示例代码：

分析：

每次查找范围减半

设查找次数为 x，则满足n / 2^x = 1，解得 x=log_⁡2n

时间复杂度：O(log⁡n)

3. 线性阶 O(n)

定义：如果算法的运行时间与输入规模成正比，则时间复杂度为 O(n)。

示例：

特点：

遍历 n个元素，执行 n 次操作

时间复杂度：O(n)

4. 平方阶 O(n2)

定义：如果算法的运行时间与输入规模的平方成正比，则时间复杂度为 O(n²)。

典型示例：

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

示例代码（冒泡排序）：

分析：

外层循环执行 n−1次

内层循环执行 n−i−1 次

总执行次数约为 n(n−1)/2，即 O(n²)

5. 立方阶 O(n3)

定义：如果算法的运行时间随着输入规模的增加呈立方增长，则时间复杂度为 O(n³)。

示例代码（三重嵌套循环）：

分析：

三层嵌套循环，每层执行 n次

总执行次数为 n³

时间复杂度：O(n³)

6. 指数阶 O(2n)

定义：如果算法的运行时间随着输入规模呈指数增长，则时间复杂度为 O(2ⁿ)。

典型示例：

斐波那契数列的递归解法

示例代码：

分析：

递归树的大小大约是 2ⁿ

计算 F(n)需要计算 F(n−1)和 F(n−2)

由于存在大量重复计算，因此时间复杂度为 O(2ⁿ)

7. 时间复杂度的比较

按照增长速度，从小到大排列：

O(1)<O(log⁡n)<O(n)<O(n²)<O(n³)<O(2ⁿ)

O(1)：最快，常数级别，不受输入大小影响

O(log n)：对数增长，例如二分查找

O(n)：线性增长，例如简单遍历

O(n²)：平方增长，例如冒泡排序

O(n³)：立方增长，例如三重循环

O(2ⁿ)：指数增长，例如斐波那契递归，非常低效

总结

• 选择算法时，应优先选择时间复杂度较低的算法，以提高效率。
• 线性或对数时间复杂度的算法通常较为高效，适用于大规模数据处理。
• 指数级别的算法（如递归求解斐波那契数列）通常需要优化，例如 动态规划 来降低时间复杂度。

8.2 空间复杂度

空间复杂度（Space Complexity）衡量的是算法在运行过程中占用的额外存储空间，它描述了输入规模 nnn 增长时，算法所需的额外空间如何变化。空间复杂度的计算主要关注：

1. 变量的数量
2. 数据结构的使用
3. 递归调用的栈空间

1. 常数阶 O(1)

定义：如果算法在运行过程中只使用了固定数量的额外空间（与输入规模无关），则其空间复杂度为 O(1)。

示例：

分析：该算法仅使用了一个整数变量 count

无论输入规模 n如何变化，占用的空间始终是一个常数

空间复杂度：O(1)

2. 对数阶 O(log⁡n)

定义：如果算法的额外空间需求随着输入规模的对数增长，则空间复杂度为 O(log⁡n)。

典型示例：二分查找（Binary Search）递归的对数深度调用

示例代码（二分查找递归实现）：

分析：

递归调用的深度最多为 O(log⁡n)

空间复杂度：O(log⁡n)（递归调用栈消耗的空间）

3. 线性阶 O(n)

定义：如果算法的额外空间需求随着输入规模 n成比例增长，则空间复杂度为 O(n)。

典型示例：

递归深度为 n（如普通递归计算斐波那契数列）

使用一个大小为 n 的数组存储数据

示例代码（递归调用）：

分析：

递归调用了 n次，每次都会创建一个新的栈帧

空间复杂度：O(n)

4. 平方阶 O(n²)

定义：如果算法的额外空间需求随着输入规模 n 的平方增长，则空间复杂度为 O(n²)。

典型示例：二维数组存储 n×n 的数据（如邻接矩阵存储图）

示例代码：

分析：

申请了 n² 大小的二维数组

空间复杂度：O(n²)

5. 立方阶 O(n³)

定义：如果算法的额外空间需求随着输入规模 n 的立方增长，则空间复杂度为 O(n³)。

典型示例：三维数组（如 n×n×n 立方体）

示例代码：

分析：

申请了 n³ 大小的三维数组

空间复杂度：O(n³)

6. 指数阶 O(2ⁿ)

定义：如果算法的额外空间需求随着输入规模指数增长，则空间复杂度为 O(2ⁿ)。

典型示例：递归求解斐波那契数列的暴力递归法

示例代码：

分析：

递归树的大小约为 2ⁿ

空间复杂度：O(2ⁿ)（如果不做优化）

空间复杂度比较

按照增长速度从小到大排列：

O(1)<O(log⁡n)<O(n)<O(n²)<O(n³)<O(2ⁿ)

优化空间复杂度的策略

1. 使用迭代代替递归（避免 O(n)递归调用栈）
2. 使用原地算法（避免额外数组，如快排的 in-place 方式）
3. 使用数据结构优化存储（如 邻接表 替代 邻接矩阵）

总结

• O(1)：常数空间，最优
• O(log n)：对数空间，常见于递归二分
• O(n)：线性空间，常见于递归、数组存储
• O(n²)：平方空间，常见于二维数组（如邻接矩阵）
• O(n3)：立方空间，常见于三维数组
• O(2ⁿ)：指数空间，递归爆炸性增长（如暴力递归斐波那契）

时间复杂度通常是优化重点，空间复杂度在合理范围内即可！

8.3 图（Graph）的实现

1. 图的实现方式

在计算机科学中，图（Graph） 用于表示多对多关系，例如社交网络、网络拓扑、路线规划等。图的实现主要有两种方式：

1. 邻接矩阵（Adjacency Matrix） - 使用二维数组存储边的关系。
2. 邻接表（Adjacency List） - 使用链表或动态数组存储每个顶点的相邻节点。

2. 邻接矩阵实现图

2.1 邻接矩阵的存储方式

定义：邻接矩阵使用 二维数组 存储图的顶点之间的连接关系。

规则：如果 adj[i][j] = 1，表示 顶点 i 到 顶点 j 之间有一条边。如果 adj[i][j] = 0，表示 顶点 i 和 顶点 j 之间没有直接连接。

适用场景：适用于 稠密图（边较多），即边的数量接近于顶点数量的平方。

2.2 邻接矩阵的特点

✅ 适用于稠密图（边较多）

✅ 查找是否有边 O(1)（直接访问数组）

❌ 存储空间高（需要 O(n²)的存储空间）

例如，addEdge(0, 1) 创建了一条 0 到 1 的边（无向图）。

display() 以 矩阵形式 打印存储结构。

3. 邻接表实现图

3.1 邻接表的存储方式

• 定义：邻接表使用 动态数组（vector）或链表 存储每个顶点的相邻节点，比邻接矩阵更节省空间。
• 适用场景：适用于 稀疏图（边较少），即 边的数量远小于顶点数量的平方。

3.2 邻接表的特点

✅ 适用于稀疏图（边较少）

✅ 存储空间较低（只存储实际存在的边）

❌ 查找某一条边是否存在较慢（需要遍历链表）

每个顶点存储它的邻接顶点。

display() 遍历 所有节点，并打印邻接表。

8.4 图的遍历：深度优先搜索（DFS） & 广度优先搜索（BFS）

在图的操作中，遍历（Traversal） 是最重要的基础算法之一。遍历可以用于：

• 查找路径（如最短路径问题）
• 检测连通性（检查图是否是连通的）
• 解决网络问题（如社交网络关系、迷宫寻路）

1.深度优先搜索

DFS 的工作原理

DFS 类似于树的前序遍历，使用递归或栈实现。

其基本步骤如下：

1. 选择起始顶点，标记为已访问。
2. 访问当前顶点的所有未访问的相邻顶点，递归继续遍历。
3. 回溯到上一个未完全遍历的顶点，继续访问其他邻接点。

DFS 代码递归示例：

DFS 采用 递归 方式：

1. 先访问 0，然后从 0 出发访问 1（最左边的路径）。
2. 继续访问 1 的 3，然后回溯访问 4。
3. 1 处理完毕，回溯到 0，然后访问 2。
4. 2 的 5 和 6 依次被访问。

DFS 的特点是 先往深走，走到尽头再回溯。

2. 广度优先搜索

BFS 的工作原理

BFS 类似于树的层次遍历，使用队列（Queue） 实现。

其基本步骤如下：

1. 选择起始顶点，标记为已访问，并加入队列。
2. 取出队列的队头元素，访问其所有未访问的相邻顶点，并加入队列。
3. 重复步骤 2，直到队列为空。

BFS 代码示例：

BFS 使用 队列，逐层遍历：

1. 先访问 0，然后访问 0 的邻居 1 和 2（按层遍历）。
2. 再访问 1 的 3 和 4，然后 2 的 5 和 6。
3. 依次处理 3、4、5、6，整个搜索完成。

BFS 的特点是 按层遍历，先访问同层的所有节点，再访问下一层。

3. DFS vs BFS（对比分析）

4. 选择 DFS 还是 BFS？

DFS 适用于：

• 需要搜索路径（如迷宫、连通分量）。
• 图的深度较大，不关心最短路径。

BFS 适用于：

• 需要查找最短路径（如地图导航、最短社交网络关系）。
• 需要遍历所有顶点（如搜索所有可能的答案）。

5. 总结

• DFS 使用 递归或栈，适合 路径搜索、连通性检测。
• BFS 使用 队列，适合 最短路径、广度层次遍历。
• 邻接表适用于存储稀疏图，邻接矩阵适用于存储稠密图。
• 在稠密图中，邻接矩阵存储方式更高效；在稀疏图中，邻接表存储更节省空间。

8.5 逆波兰表达式（RPN）

思路

1. 使用 栈（Stack） 来存储操作数。
2. 遍历逆波兰表达式（后缀表达式）：遇到 数字 时，入栈。遇到 运算符 时，从栈中弹出 两个操作数 进行计算，然后将结果压回栈。
3. 最终栈中只剩一个元素，即计算结果。

示例

1. 读取 3 → 入栈 [3]
2. 读取 4 → 入栈 [3, 4]
3. 读取 2 → 入栈 [3, 4, 2]
4. 读取 * → 计算 4 * 2 = 8，入栈 [3, 8]
5. 读取 1 → 入栈 [3, 8, 1]
6. 读取 5 → 入栈 [3, 8, 1, 5]
7. 读取 - → 计算 1 - 5 = -4，入栈 [3, 8, -4]
8. 读取 / → 计算 8 / -4 = -2，入栈 [3, -2