1. 概述与复杂度分析
本文是整个「数据结构与算法」系列的总纲。后续所有章节（顺序表、链表、栈、队列、树、图、哈希表、排序、查找）都建立在本章概念之上。
数据结构三要素
数据结构 = 逻辑结构 + 存储结构 + 数据的运算。三者缺一不可：
| 要素 |
含义 |
例子 |
| 逻辑结构 |
数据元素之间的逻辑关系（与存储无关，是抽象出来的关系） |
线性结构、树形结构 |
| 存储结构 |
数据在计算机中的物理存储方式（如何把逻辑关系落地） |
顺序存储、链式存储 |
| 数据的运算 |
施加在数据上的操作，如插入、删除、查找 |
在顺序表中按下标插入元素 |
- 逻辑结构是「用什么关系组织数据」，存储结构是「怎么在内存里摆」，运算是「对这个结构能做什么」。
- 同一逻辑结构可以用不同存储结构实现，运算的实现效率随之不同。
四种逻辑结构
| 逻辑结构 |
特征 |
典型代表 |
| 集合结构 |
元素之间除了「同属于一个集合」外无其他关系 |
并查集、哈希集合 |
| 线性结构 |
元素之间一一对应，有唯一前驱和唯一后继（除了首尾） |
顺序表、链表、栈、队列 |
| 树形结构 |
一对多，一个根、多个分支，分层 |
二叉树、堆、B 树 |
| 图状结构 |
多对多，任意两点之间都可能有关系 |
有向图、无向图、网络 |
四种存储结构
| 存储结构 |
说明 |
优点 |
缺点 |
| 顺序存储 |
用一组连续的存储单元依次存放数据元素，逻辑相邻即物理相邻 |
随机存取、实现简单 |
插入删除需移动大量元素；需要大片连续空间 |
| 链式存储 |
用一组任意（不连续）的存储单元存放，借助指针表示逻辑关系 |
插入删除灵活、空间可动态分配 |
只能顺序存取；额外存储指针、空间开销大 |
| 索引存储 |
建立索引表，索引项指向数据元素 |
查找速度快，便于按关键字检索 |
索引表本身占用空间，增删要维护索引 |
| 散列存储 |
根据元素的关键字直接计算出存储地址 |
查找平均时间复杂度 O(1) |
存在冲突（碰撞），需要处理冲突的策略 |
时间复杂度
- 定义：算法执行时间随问题规模 n 增长的变化趋势，记为 T(n)。用大 O 表示法（算法的渐进时间复杂度）描述：
T(n) = O(f(n))，表示 T(n) 的增长不慢于 f(n)。
- 只保留最高阶项，忽略常数系数与低阶项：例如
T(n) = 3n² + 2n + 100 → O(n²)。
- 最坏 / 平均 / 最好 三种情况：通常以最坏时间复杂度作为算法性能的保证。
常见复杂度量级排序（从小到大）
| 量级 |
名称 |
规模 10 时约执行 |
规模 100 时约执行 |
| O(1) |
常数阶 |
1 |
1 |
| O(log₂n) |
对数阶 |
4 |
7 |
| O(n) |
线性阶 |
10 |
100 |
| O(n log₂n) |
线性对数阶 |
34 |
664 |
| O(n²) |
平方阶 |
100 |
10 000 |
| O(n³) |
立方阶 |
1 000 |
1 000 000 |
| O(2ⁿ) |
指数阶 |
1 024 |
巨大 |
| O(n!) |
阶乘阶 |
3 628 800 |
天文数字 |
排序关系：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
计算技巧
- 循环体执行次数 = 复杂度。
for(i=0;i<n;i++) 内层固定操作 → O(n)。
- 两层嵌套循环（各自到 n）→ O(n²)；三层 → O(n³)。
- 循环变量倍增/折半（
i = i * 2 或 i /= 2）→ O(log n)。
- 递归算法用主定理或画出递归树分析。
空间复杂度
- 定义：算法运行所需额外存储空间随 n 增长的量级，记为 S(n)。
- 只统计临时额外空间，不包含输入本身占用的空间。
- 常见情况：原地操作（只用到常数额外变量）→ O(1)；递归深度为 n → O(n)。
各数据结构适用场景总览
| 数据结构 |
特点 |
适用场景 |
| 顺序表 |
连续存储，支持 O(1) 随机存取；插入/删除需要移动元素，平均 O(n) |
频繁按下标访问、表长基本固定、很少插入删除 |
| 链表 |
离散存储，插入/删除 O(1)（已知结点）；查找需要遍历 O(n)；额外指针开销 |
频繁插入/删除、表长动态变化、不知确切长度 |
| 栈 |
后进先出（LIFO），只能在栈顶操作 |
函数调用、括号匹配、表达式求值、撤销操作、DFS |
| 队列 |
先进先出（FIFO），队尾入队、队头出队 |
任务调度、打印队列、广度优先搜索 BFS、缓冲 |
| 树 |
层次关系，一对多；二叉树、二叉搜索树、堆等变体 |
文件系统目录、表达式树、优先队列（堆）、查找树 |
| 图 |
多对多关系，顶点+边 |
社交网络、地图导航（最短路径）、网络拓扑、状态机 |
| 哈希表 |
关键字 → 地址，平均 O(1) 查找 |
快速检索/去重、缓存、字典映射（键值对） |
复杂度计算示例
C 示例：两层循环求和
#include <stdio.h>
// 计算 1*1 + 1*2 + ... + n*n 的累加
// 内层循环执行次数：n*(n+1)/2 次 -> 时间复杂度 O(n^2)
int sum(int n) {
int total = 0; // O(1) 额外空间，空间复杂度 O(1)
for (int i = 1; i <= n; i++) // 外层 n 次
for (int j = 1; j <= n; j++) // 内层 n 次
total += i * j;
return total;
}
int main(void) {
int n = 5;
printf("sum(%d) = %d\n", n, sum(n));
return 0;
}
Python 示例：折半（对数阶）
# 每次循环 i 翻倍，只需 log2(n) 次 -> 时间复杂度 O(log n)
def count_steps(n: int) -> int:
steps = 0
i = 1
while i < n:
i = i * 2
steps += 1
return steps
if __name__ == "__main__":
n = 1000
print(f"n={n} 时循环次数: {count_steps(n)}") # 约 10 次
系列导航
| 章节 |
主题 |
复杂度主线 |
| 本页 |
概述与复杂度分析 |
O(1) ~ O(n!) 量级 |
| 2 |
[[2.顺序表]] |
随机存取 O(1)，插入删除 O(n) |
| 3 |
[[3.单链表]] |
插入删除 O(1)（已知结点），查找 O(n) |
| 4 |
[[4.双链表]] |
可双向遍历，前插 O(1) |
| 5 |
[[5.循环链表]] |
从尾部到头 O(1)，遍历终止条件特殊 |
阅读建议：先掌握本页的复杂度分析方法，再按 2 → 5 的顺序学习线性表，重点对比「顺序存储 vs 链式存储」的取舍。
