什么是数据结构
在学习具体的数据结构之前,先理清几个基本概念。这些概念在考试和面试中经常出现,也是理解后续所有章节的基础。
数据
数据是计算机能识别、存储和处理的符号集合。数字、字符、图片、音频——凡是能被计算机处理的东西,都是数据。
数据元素
数据元素是数据的基本单位,在程序中通常作为一个整体进行考虑和处理。一个数据元素可以由多个数据项组成。而数据项即是最小单位。
简单解释,数据结构是对数据元素的操作,数据元素由数据项组成,数据元素是一串内存,数据项是单个地址,而数据是对于所有单位都统称。
举个例子:一个学生记录是一个数据元素,它包含姓名、学号、成绩等多个数据项。
| 概念 | 类比 | 示例 |
|---|---|---|
| 数据 | 整个通讯录 | 全班同学的联系方式 |
| 数据元素 | 通讯录中的一条记录 | 张三的完整信息 |
| 数据项 | 记录中的一个字段 | 张三的电话号码 |
数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包含两个层面:
- 逻辑结构:数据元素之间的抽象关系(与存储无关),逻辑结构主要分为线性结构和非线性结构
- 物理结构(存储结构):数据在计算机内存中的实际存储方式,目前主要分为顺序存储结构和链式存储结构。
逻辑结构
逻辑结构描述数据元素之间的抽象关系,与计算机如何实现无关。主要分为四大类:
| 逻辑结构 | 关系 | 说明 | 典型例子 |
|---|---|---|---|
| 集合结构 | 元素同属一个集合,无其他关系 | 最松散的结构 | {1, 3, 5, 7} |
| 线性结构 | 一对一(1:1) | 元素排成一条线 | [[C_顺序表_SequentialList |
| 树形结构 | 一对多(1:N) | 层层分支 | 二叉树、B树、文件系统 |
| 图形结构 | 多对多(M:N) | 任意连接 | 社交网络、地图导航 |
graph TD subgraph 集合结构 S1((1)) --- S2((3)) --- S3((5)) --- S4((7)) end subgraph 线性结构 L1[1] --> L2[2] --> L3[3] --> L4[4] end subgraph 树形结构 T1[1] --> T2[2] T1 --> T3[3] T2 --> T4[4] T2 --> T5[5] T3 --> T6[6] end subgraph 图形结构 G1((A)) --- G2((B)) G1 --- G3((C)) G2 --- G3 G2 --- G4((D)) G3 --- G4 end
关键区分:逻辑结构关注的是”元素之间有什么关系”,不关心”元素存在哪里”。同一个线性结构,可以用数组存储,也可以用链表存储——这就是逻辑结构和物理结构的分离。线性结构中最基础的抽象是线性表,它的定义与两种实现见 线性表与顺序表。
物理结构(存储结构)
物理结构描述数据在计算机内存中的实际存储方式。主要分为两种:
顺序存储
把逻辑上相邻的元素,存储在物理位置也相邻的存储单元中。
内存地址: 1000 1004 1008 1012 1016
存储内容: [ 1 ][ 2 ][ 3 ][ 4 ][ 5 ]
←──── 连续的内存块 ────→
特点:
- 支持随机访问(按下标取值 O(1))
- 插入/删除需要移动大量元素 O(n)
- 需要预先分配连续空间
典型代表:数组
链式存储
不要求逻辑上相邻的元素在物理位置上也相邻,元素间的逻辑关系通过附加的指针来表示。
内存地址: 1000 2056 1532
存储内容: [ 1 | ●]→[ 2 | ●]→[ 3 | ●]→NULL
↑ ↑ ↑
不连续!靠指针链接
特点:
- 不支持随机访问(必须从头遍历 O(n))
- 插入/删除只需修改指针 O(1)
- 动态分配,不需要预先知道数据规模
典型代表:链表
对比
| 维度 | 顺序存储 | 链式存储 |
|---|---|---|
| 内存分配 | 预先分配连续空间 | 动态分配,按需申请 |
| 随机访问 | O(1) | O(n) |
| 插入/删除 | O(n)(需移动元素) | O(1)(已知位置时) |
| 空间利用 | 可能浪费(预分配过多) | 按需使用,但指针占额外空间 |
| 缓存友好 | 好(连续内存,局部性) | 差(节点分散,cache miss) |
还有一种散列存储:用哈希函数直接计算元素的存储地址,典型代表是哈希表。它既不是纯粹的顺序存储,也不是链式存储,而是通过数学映射直达目标位置。
数据的运算
无论哪种数据结构,基本运算都可以归纳为以下几类:
| 运算类型 | 说明 | 示例 |
|---|---|---|
| 查找(Search) | 在数据结构中找到指定元素 | 在数组中找值为 5 的元素 |
| 插入(Insert) | 在数据结构中添加新元素 | 在链表头插入新节点 |
| 删除(Delete) | 从数据结构中移除指定元素 | 删除二叉树的叶节点 |
| 修改(Update) | 更新指定元素的值 | 修改数组 arr[3] 的值 |
| 遍历(Traverse) | 访问数据结构中的每个元素 | 中序遍历二叉树 |
算法
算法是什么
在《数论》中的解释是为了实现一个计算或解决一个问题而给定的精确的指令的有限集合
在严蔚敏《数据结构》教材中是对特定问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作
社区普遍的技术定义是解决问题的明确指令,在有限时间内完成
无论如何定义,算法都应该具备 输入,输出,有穷,确定,可行的五大性质
算法的五个特性
| 特性 | 含义 |
|---|---|
| 有穷性 | 在有限步之后结束,且每一步都在有限时间内完成 |
| 确定性 | 每条指令无歧义,相同输入必得相同输出 |
| 可行性 | 每一步都能通过已实现的基本运算执行有限次完成 |
| 输入 | 有零个或多个输入 |
| 输出 | 至少有一个输出,否则算法没有意义 |
算法与程序
算法不等于程序:
- 算法是解决问题的思想与步骤,独立于编程语言和机器;
- 程序是算法在某种语言中的一种实现,还要受语言特性、编译器、运行环境约束;
- 一个算法可以有多种程序实现;一个程序也可以包含多个算法;
- 程序可以不满足”有穷性”(如操作系统长期运行、服务器常驻进程),而算法必须有穷——这是二者最本质的区别。
算法评价标准
| 标准 | 含义 |
|---|---|
| 正确性 | 对合法输入能给出符合规格的结果 |
| 可读性 | 结构清晰、命名合理,便于阅读、调试与维护 |
| 健壮性 | 对非法输入能作出合理反应,而不是崩溃或产生错误结果 |
| 高效性 | 时间复杂度和空间复杂度低,即运行快、占用少 |
前三条是”能不能用”,第四条是”用得好不好”。高效性的数学计算方法见本章后面的 语句频度、时间复杂度的数学计算 与 空间复杂度的数学计算。
抽象数据类型(ADT)
抽象数据类型(Abstract Data Type, ADT)由三部分组成:
| 组成部分 | 说明 | 例(线性表) |
|---|---|---|
| 数据对象 | 数据的集合 | 全体数据元素 |
| 数据关系 | 元素之间的关系 | 一对一的前驱/后继关系 |
| 基本操作 | 定义在数据对象上的操作 | 初始化、插入、删除、查找 |
ADT 的核心思想是封装与信息隐藏:
- 使用者只关心”能做什么”(操作及其语义),不关心”怎么实现”(数组还是链表);
- 使用与实现分离:同一套 ADT 接口可以有多种实现,只要接口语义不变,更换实现不影响调用者;
- 本章 数据抽象 一节从”对外 / 对内”的角度再次解释了这一思想;
- C 语言中常用”结构体 + 一组函数”模拟 ADT,见 线性表 的接口约定。
数据类型与数据对象
| 概念 | 定义 | 例 |
|---|---|---|
| 数据类型 | 值的集合 + 定义在该集合上的一组操作 | int:整数值 + 加减乘除等运算 |
| 原子类型 | 值不可再分的数据类型 | int、char、bool |
| 结构类型 | 其值可以再分解的数据类型 | 结构体、数组 |
| 抽象数据类型 | 只描述逻辑特性、与实现无关的数据类型 | 栈、队列、图 |
| 数据对象 | 具有相同性质的数据元素的集合 | 全体整数、某个班的全体学生 |
数据类型是语言层面的分类,数据对象是逻辑层面的一批元素;二者都强调”值 + 操作”的绑定关系。
逻辑结构与存储结构的关系
flowchart LR L["逻辑结构<br/>数据元素之间的关系"] -->|"可有多种实现"| S1["顺序存储"] L --> S2["链式存储"] L --> S3["索引存储"] L --> S4["散列存储"] S1 --> P["存储结构<br/>(物理结构)"] S2 --> P S3 --> P S4 --> P
三条结论(选择题高频):
- 逻辑结构独立于存储结构:线性表这个概念不依赖它是用数组还是链表实现;
- 一种逻辑结构可以有多种存储结构:线性表既可以用顺序表,也可以用链表;
- 存储结构依赖逻辑结构,不能独立存在:脱离”元素之间是什么关系”,就无从谈论”怎么存”。
常见数据结构一览
下面按逻辑结构给出一张全景表。本章只做一句话介绍,具体实现与算法见对应章节。本节与前面的算法、ADT、数据类型、逻辑与存储结构关系等概念小节,是 408 选择题、填空题与判断题的高频考区。
| 结构 | 逻辑结构 | 一句话介绍 | 详见 |
|---|---|---|---|
| 线性表 | 线性 | 个数据元素的有限序列,两种实现:顺序表与链表 | 线性表 |
| 数组 | 线性 | 连续存储,按下标随机访问 | 数组 |
| 字符串 | 线性 | 字符的有限序列,模式匹配是核心算法 | 字符串 |
| 链表 | 线性 | 结点存放数据与指针,已知位置插删只改指针 | 链表 |
| 栈 | 线性(受限) | 后进先出(LIFO),只在一端操作 | 栈 |
| 队列 | 线性(受限) | 先进先出(FIFO),两端分别进出 | 队列 |
| 稀疏矩阵 | 线性(二维) | 只存非零元,三元组或十字链表压缩 | 稀疏矩阵 |
| 树 | 树形 | 一对多的层次结构,BST / AVL / B 树各司其职 | 树 |
| 堆 | 树形 | 完全二叉树的数组实现,优先队列的底层 | 堆 |
| 图 | 图形 | 多对多关系,遍历、最短路、最小生成树 | 图 |
| 哈希表 | 集合 / 映射 | 哈希函数直接定位,平均 查找 | 哈希表 |
| 并查集 | 集合 | 合并与查询集合,近似常数时间 | 并查集 |
两个不在表内但考试常考的概念:
内存和地址
计算机运行程序时,所有数据都存在内存(RAM)里。可以把内存想象成一排带编号的小格子,每个格子能存一小块数据,格子的编号就是它的地址(类似宾馆的房间号)。
程序里写的变量名、数组名,对 CPU 来说都不存在——CPU 只认地址。所以理解”数据放在哪、怎么找到它”,是理解一切数据结构的第一步。
数据宽度
一个格子能存多少数据,取决于数据宽度。比如:
char占 1 字节int占 4 字节double占 8 字节
数据宽度也叫”元素大小”。后面学数组时你会看到:第 i 个元素的地址 = 起始地址 + i × 数据宽度,这个公式几乎贯穿整个教程。
字节
字节(Byte)是计算机存储的最小单位,1 字节 = 8 个二进制位(bit),能表示 0 ~ 255 的数字。
文件大小里的 KB、MB、GB 都基于字节:1 KB = 1024 字节,1 MB = 1024 KB。记住 就够了。
CPU
CPU 是计算机的”大脑”,负责执行指令。它工作时只跟寄存器(CPU 内部的小存储)打交道,而寄存器的数据要从内存读来。CPU 的速度非常快,快得内存跟不上——正是这个速度差距,引出了下面的”缓存”。
这一节不需要深究,只要记住一句话:CPU 读数据是有代价的,从不同地方读,速度差很多倍。
磁盘和存储
磁盘(硬盘/SSD)是”断电后数据还在”的地方。程序不运行时存在磁盘里,运行时要先加载到内存。
类比:内存是办公桌,磁盘是抽屉。拿东西桌面上最快,抽屉里要弯腰,慢得多(慢约十万倍)。所以数据结构的性能讨论,通常只关心内存,不关心磁盘。
缓存
因为 CPU 太快、内存太慢,计算机在中间加了一层速度更快的缓存(Cache),自动存最近用过的数据。CPU 每次读数据,会顺带把相邻的一小片数据一起搬进缓存(这叫”局部性”)。
这就是为什么:
- 数组(连续内存)从头到尾读一遍,非常快——因为一次能搬一大片进缓存;
- 链表(节点散落各处)跳着读,每次都”扑空”,慢得多。
同样的操作,数据摆得越连续,跑得越快。 这是整个教程反复出现的底层逻辑。
偏移
从某段内存的起点往前”数几格”,这个距离叫偏移(offset)。比如数组的第 3 个元素,距开头偏移是 3。
索引
索引(index)就是数组下标 i,从 0 开始。索引和偏移的关系:
一个 int 数组,arr[3] 的字节偏移是 字节。
地址
地址是内存格子的编号,也是变量真正的”身份证”。数组里每个元素的位置:
(基地址就是 arr[0] 的地址)这个公式是数组 O(1) 随机访问的全部秘密——只要一次乘法和加法,就能算出任意元素在哪。
指针
指针是一个”存的不是数据,而是别人地址”的变量。类比:一张纸条上写着”东西在第 12 号柜子里”。
需要知道的几点:
- 指针指向一个位置,也叫”引用”它;
- 指针可以为空(NULL),表示”不指向任何地方”,使用前要判断;
- 链表、树、图这些结构,本质都是靠指针把一个个分散的节点”串”起来。
数据抽象
数据结构可以拆成两层看:
- 对外:能干什么(提供的操作,比如”插入""查找”);
- 对内:怎么存(具体实现,比如数组还是链表)。
这两层可以分开。比如”栈”只规定”后进先出、只能从顶部操作”这个规则,底层用数组实现也行、用链表实现也行——使用者完全不用关心。这种”只看规则、不看实现”的思想就是抽象。
所以后面学”栈""队列""哈希表”时,先分清它是一套规则(抽象),还是具体的实现,学习会顺畅很多。
数学基础
对数
的意思是:“2 要自乘几次才等于 n”。例如 ,因为 。
为什么数据结构里到处都是 O(log n):因为很多算法每做一次操作就”砍掉一半”(二分查找、二叉树的查找都是)。砍一半很快到底——,也就是说处理 100 万个数据,最多只需要约 20 步,这就是 O(log n) 强大之处。
幂
这种”指数”记法。计算机里到处是 2 的幂:、内存容量 4GB/8GB/16GB(翻倍增长)、容器扩容”容量 ×2”。所以看到一个东西成倍翻,先想到幂。
几何级数
一串数每一项都是前一项的固定倍数(比如 1, 2, 4, 8, 16…),叫几何级数。它有个重要性质:
为什么学:vector 扩容是”每次容量翻倍”,把扩容的搬移代价加起来正好是几何级数,总和约 2n——所以”平均每次插入的代价是常数”,这就是均摊复杂度(后面容器章节会细讲)。
取模
取模 % 就是取余数:7 % 3 = 1。它把任意大的数字”圈”进一个固定范围,很像时钟:13 点就是 1 点(模 12)。
哪里会用到:环形队列用 (i + 1) % n 转圈;哈希表用 h(k) % M 把任意键映射进桶数组。“取模让数字循环起来”,记住这一句就够。
位运算
数据在计算机里是二进制(一串 0/1),直接对这串 0/1 做的运算叫位运算:
| 符号 | 含义 | 例子 |
|---|---|---|
& | 与(按位) | i & (-i) 取出最低位的 1 |
| | 或(按位) | 把某些位设为 1 |
<< | 左移(×2) | 1 << 3 = 8 |
>> | 右移(÷2) | 8 >> 1 = 4 |
这一节只需认识符号,知道”二进制、有位运算这回事”。真正用到的地方(树状数组的 lowbit)会单独讲解,到时候再回头看这里即可。
语句频度
分析复杂度的第一步不是套公式,而是回答一个更底层的问题:每一条语句到底执行了多少次。这个次数就是语句频度(frequency count),记作 。
为什么要数语句频度
算法运行时间 = 所有语句的执行次数 × 单条语句的执行时间。单条语句的耗时取决于硬件与编译器,难以精确测量;但执行次数只取决于算法逻辑与数据规模 ,完全由代码决定。于是做两步近似:
- 认为每条语句单次执行耗时是一个常数;
- 统计各语句的频度并累加,得到”总操作次数” ,再取数量级得到时间复杂度。
一句话:语句频度是时间复杂度的原材料。从代码到公式的转化训练见 表达方式之间的转化。
如何找语句频度
按下面的顺序逐条分析:
- 找循环:只有处在循环中的语句频度才会随 增长;
- 定层级:外层循环决定”执行多少轮”,内层循环决定”每轮多少次”;
- 求和:把内层频度对循环变量求和,逐层向外展开;
- 累计:把所有语句频度相加。
以逐行统计为例:
int sum(int a[], int n) {
int s = 0; /* 1 次 */
for (int i = 0; i < n; i++) { /* 判断执行 n+1 次 */
s += a[i]; /* n 次 */
}
return s; /* 1 次 */
}| 语句 | 频度 |
|---|---|
s = 0; | 1 |
i = 0; | 1 |
判断 i < n | |
i++ | |
s += a[i]; | |
return s; | 1 |
| 合计 |
累加得 ,取数量级为 。注意:循环判断比循环体多执行一次(最后一次判断失败退出),这是教材计数的常见细节;但取数量级后 不影响结果,所以后续分析往往只关注循环体。
频度求和:把循环翻译成求和式
单层循环的频度是对循环变量求和:
for (int i = 1; i <= n; i++)
x++; /* 频度 = Σ(i=1..n) 1 = n */双重循环先固定外层、再对内存求和:
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
x++; /* 频度 = Σ(i=1..n) i = n(n+1)/2 */x++ 的频度是 ,数量级 。不是所有双重循环都执行 次——内层上界依赖外层变量时必须用求和,这是语句频度方法最直接的价值。
若内层上界与 无关或随层数规律变化,则用乘法规则:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
x++; /* 频度 = n × n = n² */非线性递增:数执行次数
循环变量按倍数增长时,不要数”每轮多少次”,而要数”总共多少轮”:
int i = 1;
while (i < n) {
i = i * 2; /* 执行 k 次,2^k ≥ n,k = ⌈log₂ n⌉ */
}设循环体执行 次,停止条件是 ,解得 ,频度为 。同理:
| 循环步进 | 执行次数 | 复杂度 |
|---|---|---|
i++ | ||
i += 2 | ||
i *= 2 | ||
i *= 3 | ||
i = i * i |
时间复杂度的数学计算
大 O 的数学定义
大O也被称为朗道符号,详见于《数论》,用于描述事物膨胀的尺度或变化规模。
比如一个函数,输入值是1,输出值是1,但是当输入值为10的时候,输出值是100,输入100的时候,输出是10000,那么这个函数对数值的膨胀尺度是平方级别的,可以用O(n²)表示其规模。
又比如一家公司,他赚钱的规模随着人员的增长,年利率增长是n倍的,那么可以用O(n)表示其年利率相对于员工数目的变化规模
要记住的是一些基础的朗道符号计算:
O(n1)+O(n2)=O(n1+n2)
O(n1) * O(n2)=O(n1* n2)
函数f是O(n)的,c是常数,那么Cf是O(n)的
函数f1和f2是O(n)的,那么f1+f2是O(n)的,f1 x f2是O(n²)的
函数有多个项,以最高指数项取值,类如f1=x³+logₙ2+n是O(n³) ----具体推导见于《数论》
常见的参考函数有,1,logₙ,nlogₙ,n²,√n,2ⁿ 如果函数的指数如同2.0001,一般情况下高斯取值最大整数。
若存在正常数 和 ,使得对一切 都有
则记 。通俗地说: 足够大以后, 被 的某个常数倍压住。
配套记号(了解即可):
| 记号 | 含义 | 直觉 |
|---|---|---|
| 上界 | 增长不快于 | |
| 下界 | 增长不慢于 | |
| 紧确界 | 与 同阶 |
计算四步法
flowchart LR A["1. 找基本语句<br/>执行次数最多的语句"] --> B["2. 写出频度 f(n)<br/>把循环翻译成求和"] B --> C["3. 化简:<br/>去常数、只留最高阶"] C --> D["4. 写成 O(f(n))"]
第 3 步的化简规则(最重要):
- 加法规则:——并列的两段代码取较大者;
- 乘法规则:——循环嵌套相乘;
- 去常数:、;
- 去低阶:、。
常用求和公式
| 求和式 | 结果 | 数量级 |
|---|---|---|
| (调和级数) | ||
几何级数 是均摊分析的关键:每层规模减半,总和收敛到 。vector 扩容、Floyd 建堆都用它。
五类典型模型推导
模型 1:单层循环 →
for (int i = 0; i < n; i++)
x++;频度 ,故 。
模型 2:双重循环 →
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
x++;内层频度 ,外层重复 次,总频度 ,故 。
模型 3:三角循环 → ,但常数是
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
x++;频度 ,仍是 ,但比模型 2 少一半操作——大 O 相同不代表实际耗时相同。
模型 4:倍增循环 →
for (int i = 1; i < n; i *= 2)
x++;执行 次后 ,,故 。
模型 5:二分 →
每次把区间折半:,共 层,故 。
递归算法:递推方程求解
递归代码的复杂度要先写出递推方程 ,再解方程。
| 递推方程 | 展开过程 | 解 | 典型算法 |
|---|---|---|---|
| 1 加 次 | 递归求阶乘 | ||
| 递归插入排序最坏 | |||
| 折半 次 | 二分查找 | ||
| 每层节点翻倍,共 层 | 二叉树遍历 | ||
| 每层总代价 ,共 层 | 归并排序、快排平均 | ||
| 双叉递归树 | 朴素斐波那契 |
树形展开法(以 为例):
flowchart TD L0["n"] --> L1a["n/2"] L0 --> L1b["n/2"] L1a --> L2a["n/4"] L1a --> L2b["n/4"] L1b --> L2c["n/4"] L1b --> L2d["n/4"] L2a -.-> D["… 共 log₂n 层,每层总代价都是 n"]
- 第 0 层总代价 ,第 1 层 ,每一层总代价都是 ;
- 层数为 ;
- 总代价 ,故 。
主定理速查(,):
| 情况 | 条件 | 解 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | 且满足正则条件 |
代入验证:
- 归并排序 :, 属情况 2,解为 ;
- 二分查找 :, 属情况 2,解为 。
最好、最坏与平均情况
同一个算法,不同输入的执行次数不同,要分三种情况分析:
| 情况 | 含义 | 例(顺序查找) |
|---|---|---|
| 最好 | 最省时的输入 | 第一个就命中:1 次比较 |
| 最坏 | 最费时的输入 | 最后一个或不存在: 次比较 |
| 平均 | 按输入分布求期望 | 等概率下: |
平均情况的数学计算:先列出所有可能输入的代价,再按概率加权求期望:
通常假设”等概率”;实际分布未知时,平均复杂度只是一种参考。顺序表的插入/删除平均移动次数就是这种计算的直接应用,详见 线性表。
增长阶的直观感受
| 复杂度 | |||
|---|---|---|---|
| 1 | 1 | 1 | |
| 3 | 7 | 20 | |
| 10 | 100 | ||
| 33 | 664 | ||
| 100 | |||
| 1024 | 不可行 |
经验值: 次操作约 1 秒(现代 CPU 量级)。所以 的题目, 通常会超时, 安全。
空间复杂度的数学计算
定义与计算范围
空间复杂度 衡量算法运行所需的额外存储空间随 的增长关系,同样用大 O 表示。输入数据本身占用的空间不计入——只算算法为了运行额外申请的空间(辅助数组、递归栈、临时变量等)。
简单解释就是空间复杂度见于算法对于额外空间的调用规模,比如额外调用一个n的一维数组,那么空间复杂度为O(n),如果是调用n* n的二维数组,那么空间复杂度则为O(n²)
计算步骤:
- 找出所有随 增长的额外空间;
- 写出空间占用函数 ;
- 去常数、取最高阶,写成 。
原地算法(in-place):,即只用了常数个变量。
常见空间模型
| 模型 | 额外空间 | 复杂度 |
|---|---|---|
| 若干个临时变量 | 常数 | |
| 一维辅助数组 | ||
| 二维辅助数组 | ||
| 递归调用栈 | 递归深度 × 每帧空间 | |
| 新建链表节点 | 个节点 |
递归栈是最容易被忽略的空间:每次递归调用都会在调用栈上压入一个栈帧(保存参数、局部变量、返回地址),空间为 。
典型例题
例 1:数组逆置(原地)
void reverse(int* a, int n) {
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}只用 i、j、t 三个变量,,是原地算法。
例 2:递归求阶乘 vs 迭代
int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}递归深度为 ,每帧只有常数个变量,。改成循环只需一个累乘变量,——递归换空间、迭代省空间的典型对照。
例 3:归并排序与快速排序
归并排序的合并阶段需要一个与待合并区间等长的临时数组,最坏 ;快速排序原地分区 (不计递归栈),但递归栈期望深度为 ,最坏 。
例 4:斐波那契的三种解法
| 解法 | 时间 | 空间 |
|---|---|---|
| 朴素递归 | (栈深度) | |
| 记忆化数组 | ||
| 滚动变量迭代 |
同一个问题三种解法,时间与空间各不相同——这就是”时空权衡”的具体体现,也是下一节的内容。
复杂度计算练习
题 1(语句频度):求下列代码中 x++ 的频度与时间复杂度。
for (int i = 1; i <= n; i++)
for (int j = 1; j * j <= n; j++)
x++;外层执行 次;内层条件 等价于 ,内层执行 次。总频度 ,时间复杂度 。陷阱:只看到”双重循环”就写 是错的,内层次数并不随 线性增长。
题 2(对数循环):下列代码的时间复杂度是多少?
int i = n;
while (i > 0) {
x++;
i = i / 3;
}
i的取值为 ,执行次数是满足 的最大 ,即 ,时间复杂度 。底数不影响数量级,所以也写 。
题 3(递推方程):解 ,并说明它对应哪个算法。
用树形展开:每一层的总代价都是 ( 个子问题各贡献 ),共 层,总代价 ,故 。对应归并排序与快速排序的平均情况。
题 4(空间复杂度):递归版二分查找的空间复杂度是多少?
int bsearch(int* a, int l, int r, int key) {
if (l > r) return -1;
int mid = (l + r) / 2;
if (a[mid] == key) return mid;
if (a[mid] > key) return bsearch(a, l, mid - 1, key);
return bsearch(a, mid + 1, r, key);
}每次递归区间折半,递归深度 ,每帧只占常数空间,故 。若改成循环实现(
l、r递推更新),。
题 5(平均情况):对长度为 的顺序表进行等概率的顺序查找,求查找成功的平均比较次数。
查找第 个元素需要比较 次,每种位置概率 :
数量级为 。
题 6(判断与化简):化简下列表达式并判断大小关系。
- ,
- ,
- ,;当 足够大时 ,故 增长更慢。注意 这个常数不影响结论——低阶项与常数在数量级比较中会被吞掉,但小规模时实际性能可能相反。
- 是指数级, 是多项式级;无论 次方多大,指数最终都会反超, 增长更慢。
最优解与时空权衡
同一个问题往往有多种解法,选一个”又快又省”的就是最优解。注意时间和空间常常矛盾:
- 空间换时间:多存一些中间结果,避免重复计算,换来更快的运行;
- 时间换空间:少存东西、多算几遍,换取更低的内存占用。
| 策略 | 做法 | 典型例子 | 对应章节 |
|---|---|---|---|
| 空间换时间 | 预存结果、直接查表 | 哈希表平均 查找 | 哈希表 |
| 空间换时间 | 预处理前缀信息 | 前缀和 / 差分把区间查询降为 | 前缀和、差分 |
| 空间换时间 | 记录子问题答案 | 记忆化搜索、DP 表 | 动态规划、背包 DP |
| 空间换时间 | 缓存热点数据 | LRU 缓存(哈希表 + 双向链表) | 链表、哈希表 |
| 时间换空间 | 反复计算代替存储 | 不用备忘录的递归、滚动变量迭代 | 递推递归 |
| 时间换空间 | 原地操作、双指针 | 数组原地去重、就地逆置 | 双指针 |
| 综合优化 | 均摊、单调性与数据结构加速 | 单调栈 / 单调队列、线段树、树状数组 | 优化专题 |
没有绝对”最优”的结构,只有在给定数据规模、内存限制与操作分布下最合适的选择。这也是本教程每章都给出复杂度表的原因。
运行时内存布局
程序运行时,它的内存大致分成几块区域:
- 代码段:存放程序指令本身;
- 调用栈(stack):函数调用时自动分配空间,一层层”叠”起来,函数返回时自动回收。特点:自动管理、很快、大小有限(递归太深会溢出);
- 堆(heap):程序员手动申请的空间(C 的
malloc、C++ 的new),用完后要手动释放。特点:手动管理、灵活、空间大。
注意区分:这里的”栈 / 堆”是内存区域,不是数据结构”栈 / 堆”。
数据结构里的”栈”是指”后进先出”的规则——恰好函数调用也是后进先出(最晚调用的函数最先返回),所以这个内存区域才借用了”栈”的名字。这也解释了为什么”递归”总跟”栈”联系在一起。