数据结构与算法设计 · 第 01 讲

第 01 讲 绪论:数据结构与算法分析

这一讲不写复杂算法,只做一件事:把「数据结构」这四个字拆开揉碎,让你知道后面 14 讲要学的每一个结构 究竟在解决什么问题;再交给你一把尺子——大 O 记号,用来衡量任何一个算法的快慢与省费。

预计 90 分钟 前置:C++ 基础语法(变量 / 数组 / 函数 / 指针) 关键词:逻辑结构 · 存储结构 · 抽象数据类型 · 时间复杂度 · 空间复杂度
本章导读
  • 先立概念:数据、数据元素、数据项、数据对象四个词经常被混用,考试却专挑它们出选择题。
  • 再分两层:逻辑结构(跟计算机无关的关系)与存储结构(内存里怎么摆),两层分清,后面所有结构都是这两层的组合。
  • 然后抽象:抽象数据类型 ADT 把「能做什么」和「怎么做」彻底分开,这是工程代码能长期维护的根本原因。
  • 最后量尺:算法效率不看秒表看渐近,本章给出大 O 的严格定义、三条推导法则、8 道手推例题。
  • 顺手打底:末尾 43 条中英对照术语表覆盖全课程,建议打印出来贴在书桌前。

1.1 四个底层术语:数据、数据元素、数据项、数据对象

这四个词是层层包含的,先在最熟悉的场景——学生成绩表——里把它们一次性认清:

数据 data
能输入计算机并被程序识别处理的符号集合。整数 65 与字符 'A' 在内存里都是 0x41——同一份存储,不同解释即不同数据。
数据项 data item
不可再分的最小单位,也叫字段。如「学号 = 1001」;再往下拆成 1、0、0、1 就失去含义了。
数据元素 data element
数据的基本单位,由若干数据项组成,也叫记录或结点。如「张三 1001 计科1班 92」这一整条记录。
数据对象 data object
性质相同的数据元素的集合。全班成绩记录格式一致,构成一个数据对象。

要特别注意数据对象与数据结构的区别:数据对象回答「有哪些成员」,数据结构回答 「成员之间是什么关系」。下面这张图把四者的包含关系画了出来——

数据 data:一切能输入计算机并被程序处理、具有含义的符号集合 数据对象:学生成绩表 data object —— 性质相同的数据元素的集合 数据元素 1:张三 1001 计科1班 92 数据元素 2:李四 1002 计科1班 78 数据元素 3:王五 1003 计科2班 85 … 共 n 条记录,每一条都是一个数据元素 … (在链表 / 树 / 图中,也常被称为「结点 node」) 取出一条 一个数据元素(一条记录 / 一个结点) 数据项 1:学号 = 1001 数据项 2:姓名 = 张三 数据项 3:班级 = 计科 1 班 数据项:不可再分割的最小单位(也叫「字段 field」) 数据元素:数据的基本单位,由若干数据项组成 数据对象:性质相同的数据元素的集合,是数据的子集 层级关系:数据 ⊇ 数据对象 ⊇ 数据元素 ⊇ 数据项
图 1-1 数据、数据对象、数据元素、数据项四者的层级关系(以学生成绩表为例)

1.1.1 数据结构的严格定义

把上面的铺垫收拢,给出教材上那个必须一字不差记住的定义:

定义 1-1 数据结构(data structure) 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 换句话说,数据结构 = 数据元素 + 元素之间的关系。没有关系的一堆数据只是「一袋土豆」, 戴上关系这顶帽子,它才成为「结构」。

这个定义里最值钱的是「关系」两个字。数组里有下标相邻关系,链表里有指针指向关系, 二叉树里有父子关系,图里有邻接关系。所以学一个新结构时,第一句要问的就是: 它的元素之间到底是什么关系?

但这还不完整。只谈关系,算法没法运行,因为关系必须落到内存上。于是数据结构包含三个方面的内容:

数据结构 = 逻辑结构 + 存储结构(物理结构) + 数据的运算

这三者的关系可以用一句话概括:逻辑结构决定「能做什么运算」,存储结构决定「这些运算要花多少代价」。 后面第 1.4 节会用顺序表和链表把这个结论演示得非常具体。

数据结构 ① 逻辑结构 ② 存储结构(物理) ③ 数据的运算 集合 / 线性 / 树形 / 图形 面向问题,与计算机无关 研究「元素之间是什么关系」 顺序 / 链式 / 索引 / 散列 面向机器,与语言实现有关 研究「关系在内存里怎么表示」 增 / 删 / 改 / 查 / 遍历 / 排序 定义在逻辑结构上 实现依赖存储结构,代价不同 存储结构是逻辑结构的「机器投影」;运算效率由二者共同决定 记忆口诀:逻辑结构管「关系」 · 存储结构管「落地」 · 运算管「操作」 · 三者合起来才叫数据结构
图 1-2 数据结构的三要素:逻辑结构、存储结构与数据的运算
一个常见误解 不少同学把「数据结构」等同于「存储结构」,于是觉得「数组是一种数据结构,链表是另一种数据结构」。 更准确的说法是:线性表是逻辑结构,顺序表和链表是它的两种存储实现。 把这句话想通,第 1.4 节就无须再讲。

1.2 逻辑结构:四类基本结构

逻辑结构只关心一件事:元素之间有没有关系、是什么关系。按关系的复杂程度,可以把常见的逻辑结构 分成四类:集合结构、线性结构、树形结构、图形结构(网状结构)。 这四类几乎覆盖了本课程后面全部的章节,所以务必把它们的图示刻进脑子里。

1.2.1 集合结构:只有「同属一伙」这一种关系

集合结构中的元素除了「同属于一个集合」之外,没有任何其他关系。元素之间没有次序、没有层级、 没有邻接。它是四类里关系最弱的一种。

典型的例子是并查集(Union-Find)里维护的等价类,或者 C++ 的 std::set: 你只关心「某个元素在不在这个集合里」,不关心它排第几、旁边是谁。 集合结构的运算通常是:判断元素是否属于集合、求并集、求交集、求差集。

1.2.2 线性结构:一对一的前驱后继

线性结构就是一条链:所有元素排成一列,每个元素最多只有一个直接前驱、一个直接后继, 并且链条有头有尾——恰好一个元素没有前驱(首元素),恰好一个元素没有后继(尾元素)。 教材上那四条性质,说的就是这一件事。

记忆抓手:只数「两个 1」 判断是不是线性结构,不必背四条,只数两个数:每个元素的前驱数 ≤ 1,后继数 ≤ 1。 满足就是「线」,不满足就是「网」。首尾那两个特殊元素,只是为了保证这条线是完整的一条。

线性结构是本课程最庞大的家族:线性表、栈、队列、双端队列、串、数组都属于线性结构。 它们之间的区别只在于「限制在哪里」——栈限制只能在一端插入删除,队列限制一端进另一端出, 串限制元素是字符且操作以「子串」为单位。抓住这条主线,第 2~6 讲会非常轻松。

1.2.3 树形结构:一对多的层次关系

树形结构中,数据元素之间存在一对多的层次关系:每个元素最多有一个直接前驱(父结点), 但可以有多个直接后继(孩子结点)。树形结构最贴近现实世界的组织方式——文件目录、家族谱系、 公司组织架构、HTML 文档结构,全都是树。

树形结构天生适合表达「分类」与「层次」:从根到叶的一条路径就是一次「细分」。 也正因为层次的存在,树上的查找、插入、删除可以做到 O(log n)(平衡树), 这是线性结构做不到的——这就是「结构决定算法」的最好例证。

1.2.4 图形结构(网状结构):多对多

图形结构中,数据元素之间存在多对多的任意关系:任一元素都可以与任意多个其他元素相邻。 图是四类逻辑结构里表达能力最强、也最难处理的:交通网、社交网络、课程先修关系、 状态机、依赖关系图,都只能用它描述。

强表达能力的代价是算法复杂度。比如「求两点间最短路径」,在树上是唯一的简单路径(沿树走即可), 在图上却要考虑指数级的路径数量,于是才有了 Dijkstra、Floyd、Bellman-Ford 这些算法。

1 2 3 4 5 元素间无任何连线
图 1-3 集合结构(关系:同属一个集合)
a1 a2 a3 a4 一对一:唯一前驱 / 唯一后继 除首尾外每个元素前后各一个
图 1-4 线性结构(关系:一对一)
A B C D E F
图 1-5 树形结构(关系:一对多的层次)
1 2 3 4
图 1-6 图形结构(关系:多对多,任意相连)

1.2.5 换个切法:线性结构与非线性结构

四类结构还可以再粗分一刀,这也是考试里出现频率极高的一个划分: 线性结构(线性表、栈、队列、串、数组)与非线性结构(集合、树、图)。 判断标准只有一个:元素之间是否是一对一的线性关系。

划分包含的逻辑结构关系特征本课程对应章节典型运算代价
线性结构 线性表、栈、队列、双端队列、串、数组 一对一,有唯一首元素与唯一尾元素 第 02 ~ 06 讲 按位置访问 O(1)(顺序存储)或 O(n)(链式)
非线性结构 集合、树形结构、图形结构 一对多(树)、多对多(图)、无关系(集合) 第 07 ~ 09 讲 树查找 O(log n)、图遍历 O(V+E)
逻辑结构 线性结构(一对一) 非线性结构(一对多 / 多对多) 线性表 栈 队列 串 / 数组 (都只有唯一前驱与后继) 集合 树 图 (关系不再是一对一)
图 1-7 逻辑结构的两种分法:四分类与「线性 / 非线性」二分
易错点:「数组是线性结构」要说清是在哪一层 说「数组是线性结构」,指的是它的逻辑结构——元素一个一个排下去,每个最多一个前驱、一个后继。 这与它在内存里怎么摊开是两件事:二维数组为了塞进一维内存,必须人为约定「先横着排还是先竖着排」, 于是才有了行优先 / 列优先的地址计算。那是存储层面的选择,不改变它的逻辑结构(第 06 讲细讲)。

1.3 存储结构(物理结构):四种落地手段

逻辑结构是纸上谈兵,它必须被放进计算机的存储器里才能真正跑起来。存储结构(也叫物理结构) 研究的就是:数据元素本身怎么存,元素之间的关系怎么存。请注意这句话有两半,很多人只做了前一半。 只把数据丢进内存是不够的,你还得把「谁挨着谁」「谁指向谁」也存下来——而表示关系的方式, 恰恰是区分不同存储结构的唯一标准。

教材上把存储结构分成四种:顺序存储、链式存储、索引存储、散列存储。前两种是基础, 后两种是「加外挂」的思路。下面逐一拆解。

1.3.1 顺序存储:用「物理相邻」表示「逻辑相邻」

顺序存储把逻辑上相邻的元素存放在物理位置也相邻的存储单元里,元素之间的逻辑关系 不需要额外空间来记录——因为「挨着」这件事本身就蕴含了「相邻」这个关系。 这就是顺序存储最漂亮的地方:关系是免费的。

由于每个元素占用的字节数固定,第 i 个元素的地址可以直接算出来:

LOC(ai) = LOC(a1) + (i − 1) × sizeof(ElemType)

有了这个公式,随机访问(random access)就成了可能:访问第 1 个元素和访问第 10⁶ 个元素, 花的时间完全一样,都是 O(1)。代价也很直接——插入和删除时,为了保持「物理相邻」, 必须成片地搬移元素,最坏 O(n)。另外,顺序存储通常要求预先分配一段连续空间, 空间不够要扩容(重新申请 + 整体拷贝),空间富余则浪费。

典型例子:C++ 的 std::vector、std::array、字符串的字面量存储、 完全二叉树的顺序存储(第 07 讲)。

1.3.2 链式存储:用「指针」显式记录关系

链式存储不要求物理相邻,它在每个元素上附加指针(pointer),用指针的取值 显式地指出下一个元素在哪儿。这时「关系」不再免费——每个结点都要多花几个字节来存指针。 换来的是巨大的灵活性:

典型例子:单链表、双向链表、循环链表、静态链表(用数组下标模拟指针)、 二叉链表(第 07 讲)、邻接表(第 08 讲)、散列表的链地址法。 一句话总结:顺序存储用「地址的算术」换「关系空间」,链式存储用「关系空间」换「地址的算术」。

1.3.3 索引存储:主表 + 索引表的二级结构

索引存储同时维护两份数据:一份是存放全部元素的数据表(主表),另一份是 索引表,索引表的每一项形如「关键字 → 该记录的存储地址」。查找时先查索引表定位, 再按地址直接取记录。

它的优点是检索速度快(索引表通常远小于数据表,可以常驻内存甚至做成树形索引), 缺点是多了一份索引的空间开销,而且插入、删除记录时必须同步维护索引表, 否则索引就失效了。现实中的数据库索引(B+ 树)、图书目录、字典的部首表都是这个思路。 注意索引存储里的数据表本身既可以是顺序的,也可以是链式的——这再次说明 存储结构的四种划分不是互斥的,而是可以叠加的。

1.3.4 散列存储:由关键字直接算出地址

散列存储(哈希存储)用散列函数 h(key) 直接由关键字算出存储地址, 理想情况下「查找一次命中」,平均时间复杂度 O(1)。它最激进的地方在于: 它放弃了元素之间的顺序关系。散列表里元素是「乱」的,所以你没法做范围查询 (「查所有成绩在 80~90 之间的学生」),也没法按序遍历。

另一个必须面对的问题是冲突(collision):不同的 key 可能算出同一个地址。 解决办法有开放定址法、链地址法、再散列法、公共溢出区法四种,第 10 讲会逐一展开, 并教你手算平均查找长度 ASL。这里先记住结论:散列存储是用「顺序性」换「常数级查找」。

存储结构关系怎么表示随机访问插入 / 删除空间特点典型例子
1双层嵌套T(n) = 2n² + 2n + 2外层 n × 内层 nO(n²)
2i *= 2 / i /= 2k ≈ log₂n + 1通项 i = 2kO(log n)
3i = i * i / i = √ik ≈ log₂log₂n + 1通项 i = 22kO(log log n)
4归并排序 T(n) = 2T(n/2) + cnT(n) = cn·log₂n + O(n)归并在规模 n、n/2、…、2 这 log₂n 层,每层 cn;规模 1 那层只 return,不归并O(n log n)
5二分查找 T(n) = T(n/2) + cT(n) = c(log₂n + 1)每层常数代价 × log 层O(log n)

下面这张图是本章最重要的一张图:同一个逻辑结构(线性表)分别用顺序存储与链式存储实现。 请特别留意图中标注的内存地址与指针箭头的差别。

① 逻辑结构:线性表 L = (a1, a2, a3, a4) —— 元素之间是一对一的前驱后继关系 a1 a2 a3 a4 逻辑相邻 ≠ 物理相邻,逻辑结构不规定存放位置 ② 顺序存储:逻辑相邻 ⇒ 物理相邻,地址可以算出来 1000 1004 1008 1012 a1 a2 a3 a4 下标 0 下标 1 下标 2 下标 3 相邻元素地址相差 sizeof(ElemType) = 4 字节 地址连续 ⇒ 第 i 个元素地址可直接计算 ⇒ 随机访问 O(1) 插入 / 删除需整体搬移后继元素 ⇒ 最坏 O(n) 容量固定,扩容要重新申请并整体拷贝 ③ 链式存储:结点 = 数据域 + 指针域,地址任意(不必连续) 2000 2104 2020 2160 a1 next a2 next a3 next a4 NULL head 2104 2020 2160 · 结点之间靠指针 next 相连,内存地址可以不连续(2000 → 2104 → 2020 → 2160) · 想找第 i 个结点,必须从 head 顺着指针走 i 步,无法直接算地址 ⇒ 按位查找 O(n);已知前驱时插入只需改两条指针 ⇒ O(1)
图 1-8 同一个逻辑结构(线性表)的两种存储结构对照:上部是逻辑结构,中部是顺序存储,下部是链式存储
索引存储 index storage:给「专业」建一张索引表 某大学 70 万名学生,分在 100 个专业里,每个专业正好 7000 人;学生记录按「同专业放在一起」连续存放。 现在要查「计算机专业学号 1005 的学生」——查得快不快,全看有没有下面这张索引表。 索引表:只有 100 项,一项 = 一个专业的起始位置 专业 起始记录号 计算机 第 0 条起 数学 第 7000 条起 物理 第 14000 条起 数据表:70 万条记录,按专业分块连续存放 计算机7000 人 数学7000 人 物理7000 人 …其余专业97 个 一共 100 个这样的块,合起来 70 万条 索引直接指到计算机块的第 1 条 不建索引:只能从第 1 条开始逐条比对专业,直到碰上「计算机」——最坏要翻过 99 个专业、约 69.3 万条记录。 → 查找代价:最多约 70 万次(等于把整张表扫一遍) 建了索引:先在只有 100 项的索引表里二分查找(log₂100 ≈ 7 次比较)定位到「计算机」,   再从它后面的 7000 人里逐个比学号 → 查找代价:7 + 最多 7000 次 这就是索引的全部意义:把「翻遍 70 万条」变成「查 100 项 + 翻 7000 条」,快了约 100 倍;索引本身只占 100 项的空间,非常划算。
图 1-9 索引存储:给「专业」建索引后,查一个学生从「最多约 70 万次」降到「7 + 最多 7000 次」,快约 100 倍
散列存储 hash storage:不建索引、也不排序,由关键字直接算出该去哪个桶 演示:4 个桶(编号 0~3),散列函数 h(key) = key % 4。把 key 丢进去,算出的余数就是它该待的桶号。 下面往表里放 3 个 key:1001、1009、2002,看看它们各自去哪。 ① 由 key 算出桶号(一次取模,不需要任何比较) 1001 % 4 = 1 1009 % 4 = 1 2002 % 4 = 2 桶号 ② 桶数组:[0] 和 [3] 空着,1001 与 1009 撞进同一个桶 [0] 空 [1] 1001 张三 1009 李四 ← 链 两个 key 都算出 1,这叫冲突;查 1009 要在这个桶里比 2 次 [2] 2002 王五 桶里只有它一个,比 1 次就找到 [3] 空 优势:定位一个 key 只要「算一次 %」+「看这一个桶」, 与总记录数 n 无关——这是真正的 O(1), 比索引存储的 O(log k) 还快一步。 代价一:会冲突,桶里要再逐个比较(如上) 代价二:元素是「乱」的,顺序性被放弃, 不能做「取成绩 80~90 之间的学生」这类范围查询 所以散列存储是「用顺序性换常数级查找」:查单个 key 最快,但按顺序、按范围的需求它就无能为力了(第 10 讲细讲)。 注:桶数取 4 只为画得下;真实实现里桶数是几万到几百万,且元素变多时会自动扩容。
图 1-10 散列存储:由关键字直接算出桶号(O(1) 定位),代价是必须处理冲突、且放弃顺序性

1.4 逻辑结构与存储结构的关系

1.4.1 为什么逻辑结构独立于存储结构

逻辑结构描述的是「元素之间的关系」,这个关系是数学意义上的关系,与元素在内存第几个字节毫无关系。 同一份逻辑关系,你可以用 C++ 写,也可以用 Python 写;可以放在 32 位机器上,也可以放在 64 位机器上。 逻辑结构不变,只是因为它压根没提过「地址」这两个字。

这个「独立性」不是文字游戏,它带来两个非常实用的好处:

  1. 可以脱离实现思考算法。分析算法时我们只关心「这个操作要访问几个元素」, 不关心机器是几核、内存多快。这就是大 O 记号能够成立的前提——它只统计运算次数的增长趋势。
  2. 可以换实现而不改接口。今天用顺序表实现了栈,明天发现数据量太大需要换成链栈, 只要 ADT 接口不变,调用方的代码一行都不用改。这就是 1.5 节要讲的抽象数据类型。

1.4.2 为什么同一逻辑结构可以有多种存储结构

因为「关系」只是一个约束,满足这个约束的物理排布方式往往有很多种。线性表要求「一对一、有首有尾」, 那么:

它们全都满足线性结构的逻辑约束,但性能特征截然不同。所以选存储结构,本质是在时间、空间、 实现复杂度之间做取舍——这也是本课程后面每一章都在重复的动作。

1.4.3 存储结构如何影响算法效率:一个必须亲手算一遍的例子

「取线性表中第 i 个元素」这个运算,在逻辑结构层面是一模一样的:给定位置 i,返回对应元素。 但换成不同存储结构,代价的增长方式完全不同。

顺序表:元素地址 = 首地址 + (i-1) × 元素大小。一次乘法加一次访存, 与表长 n 无关——取第 1 个和取第 100 万个耗时一样,所以是 O(1)。

单链表:第 i 个结点在哪里?没有人知道。必须从 head 出发, 沿着 next 一步一步走 i-1 次,与 i 成正比,最坏(i = n)走 n 步,所以是 O(n)。

注意:两种不同的方式,实现同一个逻辑,竟然差了 n 倍 上面两个操作在逻辑上完全一样——都是「取第 i 个元素」、都是「在第 i 个位置插入」, 但换一种存储方式,代价就相差 n 倍。 这正是「存储结构影响算法效率」最直接的证据,也是本章最该记住的一句话。

反过来,在「已知前驱结点 p」的位置插入一个新元素:链表只要改两条指针,O(1); 顺序表却要把 p 后面的所有元素整体后移,O(n)——这一次是链表快 n 倍。 所以没有绝对的好坏,只有场景的匹配:读多写少、需要按下标随机访问时选顺序表; 频繁在中间插删、且已经拿到位置信息时选链表。这也正是「结构决定算法」最直观的一课。

// seqlist_access.cpp —— 顺序存储:逻辑相邻 ⇒ 物理相邻,按位查找 O(1)
//
// 为什么顺序表能「一步到位」?因为第 i 个元素的地址可以直接算出来:
//     LOC(a_i) = LOC(a_1) + (i - 1) * sizeof(int)
// 一次乘法 + 一次访存,跟表长 n 毫无关系 —— 这就是随机存取 O(1)。
// 代价藏在插入里:为了保持物理相邻,位序 i 及其后的元素必须整体后移。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;              // 容量:这类题 n 一般 <= 1e5,一次开够,不做扩容
int a[MAXN];                          // 数据就放在这段连续空间里:下标相邻 = 物理相邻
int len = 0;                          // 元素个数

// 按位查找(GetElem):与 i 和 len 都无关
int getElem(int i) {                  // i 是位序,从 1 开始
    if (i < 1 || i > len) return -1;  // 越界返回 -1,竞赛里不抛异常
    return a[i - 1];                  // 一次地址计算:&a[i-1] = &a[0] + (i-1)*sizeof(int)
}

// 插入(ListInsert):位序 i 及其后的元素整体后移一位 → 最坏 O(n)
// 长度为 n 时有 n+1 个可插入位置,插在第 i 个位置要搬 n-i+1 个元素,
// 等概率下平均搬移 (n + (n-1) + ... + 0) / (n+1) = n/2 个 —— 仍是 O(n)
// 返回本次搬移的元素个数(-1 表示位置非法),方便亲手数一数代价
int insertAt(int i, int x) {
    if (i < 1 || i > len + 1 || len == MAXN) return -1;
    int moved = 0;
    for (int k = len; k >= i; --k) { a[k] = a[k - 1]; ++moved; }
    a[i - 1] = x;
    ++len;
    return moved;
}

int main() {
    for (int i = 1; i <= 5; ++i) insertAt(len + 1, i * 10);   // 尾插:10 20 30 40 50
    printf("第 4 个元素 a[3] = %d(算一次地址就取到,O(1))\n", getElem(4));
    printf("地址公式实测:&a[3] - &a[0] = %lld 字节 = 3 * sizeof(int)\n",
           (long long)&a[3] - (long long)&a[0]);
    printf("头部插 999 要搬 %d 个元素(最坏 O(n))\n", insertAt(1, 999));
    printf("现在第 1 个元素 = %d,表长 = %d\n", getElem(1), len);
    return 0;
}
// linklist_access.cpp —— 链式存储:靠指针串联,按位查找 O(n)
#include <iostream>

struct Node {
    int val;
    Node* next;
    Node(int v, Node* n = nullptr) : val(v), next(n) {}
};

// 按位查找:必须从头指针出发走 i 步,无法直接算出地址,最坏 O(n)
Node* locate(Node* head, int i) {
    Node* p = head;
    while (p != nullptr && i-- > 0) p = p->next;
    return p;
}

// 已知前驱结点 p 时的插入:只改两条指针,与表长无关 → O(1)
void insertAfter(Node* p, int v) {
    Node* s = new Node(v, p->next);
    p->next = s;
}

int main() {
    Node* head = nullptr;
    for (int i = 5; i >= 1; --i) head = new Node(i * 10, head);
    std::cout << locate(head, 3)->val << '\n';   // 40:走了 3 步,O(n)
    insertAfter(head, 999);                      // O(1)
    std::cout << locate(head, 1)->val << '\n';   // 999
    return 0;
}
逻辑结构:线性表 顺序表 单链表 / 双向链表 静态链表 散列表 数组存数据 逻辑相邻 = 物理相邻 随机访问 O(1) 插删要搬元素 O(n) 结点 + 指针 物理位置任意 按位查找 O(n) 已知前驱插删 O(1) 用数组下标当游标 不依赖指针类型 容量固定 需维护空闲链表 关键字 → 地址 平均查找 O(1) 顺序性丢失 不支持范围查询 存储结构可以随便换,逻辑结构始终不变 —— 这就是「逻辑结构独立于存储结构」的含义
图 1-11 一个逻辑结构,多种存储实现:换的是代价,不换的是语义
考点 三种代价的对比 设线性表长度为 n,在下表所列操作上,两种存储结构的复杂度差异是必考内容:
运算顺序存储(顺序表)链式存储(单链表)原因
按位查找第 i 个O(1)O(n)地址可否直接计算
按值查找O(n)O(n)都得逐个比较
已知位置插入 / 删除O(n)O(1)是否需要搬移后继元素
表尾追加O(1)(均摊)O(1)(保留尾指针)或 O(n)是否维护尾指针
存储密度(数据占比)= 1< 1(要存指针)是否需要额外关系空间

1.6 算法及其特性

1.6.1 算法的定义

算法(algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列, 其中每条指令表示一个或多个操作。更通俗地说:算法就是「把输入变成输出的一套确定步骤」。

程序 = 数据结构 + 算法,这句话是 Pascal 之父沃斯(Niklaus Wirth)说的, 它点明了一个事实:数据结构负责「把数据摆好」,算法负责「按步骤处理」, 两者缺一不可。只有好的结构没有算法,数据是死物;只有算法没有合适的结构, 再聪明的算法也会被低效的存储拖垮。

1.6.2 算法的五大特性

特性含义不满足时会发生什么典型反例
有穷性
finiteness
算法必须在执行有穷步之后结束,且每一步都在有穷时间内完成 程序永远不返回,用户等到天荒地老 用 while 循环求「所有自然数之和」
确定性
definiteness
每条指令有确切含义,无二义性;相同输入在任何时候都产生相同输出 同一份数据跑两次结果不同,无法调试 「若 x 较大则……」却没说多大算较大
可行性
effectiveness
每一步都能机械地执行,并且能在有限时间内完成;可以只由基本运算构成 写出计算机根本做不到的步骤 「若方程无实根,则跳过」这类无法机械判定的描述
输入
input
有 0 个或多个输入(0 个也算:如求 1+2+…+100 的固定算式) — —
输出
output
必须有 1 个或多个输出,没有输出的算法毫无意义 算完什么也不留下,等于白算 只做计算却从不使用结果的代码
最容易搞混的两个:有穷性 vs 可行性 有穷性说的是「整个算法会结束」,是宏观的;可行性说的是「每一步都能做到」, 是微观的。一个算法可以每一步都可行,但整体不终止(死循环),此时它违反的是有穷性而不是可行性。 反过来,如果某一步是「求出任意大整数的精确阶乘并立刻打印」,在有限字长的机器上这一步不可行, 哪怕它会结束,也违反可行性。

1.6.3 算法与程序的区别

很多人把两者当成同义词,其实它们有明确区别:

比较维度算法 algorithm程序 program
存在形式一种解决问题的方法 / 思想,可以脱离语言存在用某种程序设计语言写成的具体代码
有穷性必须满足,否则不能叫算法可以不满足:操作系统、服务器主循环会一直运行
描述精度可以用自然语言、流程图、伪码描述必须严格符合语言的语法与语义
是否含 IO / 交互只关心「计算」,不关心界面与文件可以包含输入输出、图形界面、网络通信
关系算法 + 数据结构 + 语言实现 = 程序;一个算法可以有无数个程序实现

一句话记住:程序可以永远不结束,算法不行。这也是为什么我们能在纸上分析算法, 却往往难以在纸上分析一个完整程序。

1.6.4 评价算法的四个维度

同一个问题往往有很多算法,怎么比?教材给了四个维度,注意它们是有优先级的:

  1. 正确性(correctness)——最高优先级。算法应当能正确处理合法输入,并且对典型、 苛刻、边界输入都能给出符合规格说明的结果。一个跑得飞快但答案是错的算法,价值是负的。
  2. 可读性(readability)——第二优先级。算法首先是给人看的,其次才是给机器执行的。 可读性差的代码无法维护、无法调试、无法被别人复用。变量名 a1、a2、tmp2 泛滥的代码,两周后连作者自己都看不懂。
  3. 健壮性(robustness)——面对非法输入时的表现。用户输入了负数、字符串、空指针, 算法应该给出恰当反应(报错、返回错误码、使用默认值),而不是崩溃或悄悄算出一个错答案。
  4. 效率(efficiency)——包括时间效率(运行快慢)与存储效率(占用空间大小), 两者往往互相矛盾:想快就得多花内存(空间换时间),想省内存就得多算几遍(时间换空间)。

为什么把效率排在最后?因为前三个不达标时,效率毫无意义。但反过来说, 当输入规模达到 10⁶、10⁷ 时,效率就成了唯一的瓶颈——一个 O(n²) 的「正确」算法 在 n = 10⁶ 时要跑上万亿次操作,根本等不到它输出正确答案。这也是本讲后半部分 要花大力气研究复杂度分析的原因。

1.7 算法效率的度量:从掐秒表到渐近分析

1.7.1 事后统计法 vs 事前分析估算法

想知道一个算法快不快,最直接的办法就是跑一遍看时间。这叫事后统计法。 它直观,但作为研究方法几乎不可用,原因有四条:

  1. 必须先把程序写出来并跑起来,如果算法本身是错的或写不出来,就无从统计;
  2. 时间依赖于机器硬件(CPU 主频、缓存大小)、编译选项(-O0 还是 -O2)、 运行时环境(有没有别的进程抢 CPU),换个环境结论就变了;
  3. 测试数据规模太小看不出差别,规模太大又等不起;不测到 n = 10⁶ 以上, 往往分辨不出 O(n log n) 和 O(n²);
  4. 只能比较「已实现的几个算法」,无法预测「换一种思路会不会更好」。

所以我们改用在纸面上就能做的事前分析估算法:认为算法运行时间正比于其中基本操作的执行次数, 只考察当问题规模 n 增大时这个次数的增长趋势,忽略常数与低阶项。 这就是「渐近分析」,也是整门课衡量算法优劣的统一语言。

对比项事后统计法事前分析估算法
时机程序写完之后算法设计阶段即可分析
依赖条件硬件、编译器、测试数据、运行环境只依赖算法本身的控制结构
结论形式具体毫秒数(会随环境变化)渐近量级,如 O(n log n)
能否预测大规模行为不能能,正是它的目的
典型用途工程调优时最后的实测验证算法选型、考试分析、论文比较

1.7.2 语句频度:把「时间」换成一个可以数的量

语句频度(statement frequency)指一条语句在算法中被重复执行的次数。 算法中所有语句的频度之和记作 T(n),它是问题规模 n 的函数。我们约定: T(n) 越大,算法执行时间越长(两者成正比,比例常数由机器决定,我们不去管它)。

来看一个最经典的例子,请顺便留意计数口径的问题:

// count_ops.cpp —— 亲手统计语句频度,观察 T(n)/n^2 收敛到常数
#include <iostream>
#include <iomanip>

// 计数口径:统计「条件判断 + 循环体」这两类语句的执行次数
long long T(long long n) {
    long long c = 0;
    ++c;                                  // 语句 1:long long x = 0;
    for (long long i = 0; i < n; ++i) {
        ++c;                              // 语句 2:外层条件判断(成立)  执行 n 次
        for (long long j = 0; j < n; ++j) {
            ++c;                          // 语句 3:内层条件判断(成立)  执行 n^2 次
            ++c;                          // 语句 4:循环体 x++            执行 n^2 次
        }
        ++c;                              // 语句 5:内层条件判断(不成立)执行 n 次
    }
    ++c;                                  // 语句 6:外层条件判断(不成立)执行 1 次
    return c;
}

int main() {
    std::cout << std::fixed << std::setprecision(4);
    long long ns[] = {1, 2, 5, 10, 100, 1000, 10000};
    for (long long n : ns) {
        long long t = T(n);
        std::cout << "n = " << std::setw(6) << n
                  << "   T(n) = " << std::setw(12) << t
                  << "   T(n)/n^2 = " << (double)t / (double)(n * n) << '\n';
    }
    return 0;
}
// 输出节选:n=1000 时 T(n)=2002002,T(n)/n^2 = 2.0020 —— 比值稳定在 2 附近,
// 说明 T(n) 与 2n^2 同阶,记作 T(n) = O(n^2)。低阶项 2n+2 在 n 变大后被彻底淹没。
语句执行次数(语句频度)说明
long long c = 0;1只执行一次
外层 for 条件判断 i < n(成立)n每轮外层循环一次
外层 for 条件判断(不成立、退出)1循环退出时多判一次
内层 for 条件判断 j < n(成立)n²外层 n 轮 × 每轮 n 次
内层 for 条件判断(不成立)n外层每轮多判一次
循环体 x++n²真正干活的部分
合计 T(n) = 2n² + 2n + 2最高阶项:n²
为什么不同教材算出的式子不一样? 同一段代码,有的教材写成 T(n) = 3n² + 2n + 1,有的写成 2n² + 2n + 2,还有的干脆只算循环体得到 n²。 差别就在计数口径:算不算 for 的初始化?算不算最后一次失败的判断? 但请注意:无论怎么数,最高阶项都是 n²,系数都是常数。 这正是大 O 记号干脆把系数和低阶项全部扔掉的理由——它们本就不携带「增长趋势」的信息。

1.7.3 大 O 的直观说法(不要求证明)

大 O 用来描述算法的增长趋势:只保留最高阶项、忽略常数系数。 例如 3n² + 2n + 1 记作 O(n²),2n + 5 记作 O(n)。

本课程只要求会算、会判断常见代码的复杂度,不要求用 c 和 n₀ 写形式证明; 需要严格定义时再查资料。

1.7.5 推导大 O 的三条法则

下面三条法则只讲「怎么算」,不要求证明;会用它们判断常见代码的复杂度即可。

法则一 加法法则:只保留最高阶项

若 T(n) = T₁(n) + T₂(n),且 T₁(n) = O(f(n))、T₂(n) = O(g(n)), 则 T(n) = O(max(f(n), g(n)))。

为什么?设 f 是较高阶的那个,那么 f(n) + g(n) ≤ f(n) + f(n) = 2f(n)(当 n 足够大时 g 不超过 f), 取 c = 2 即可。这说明低阶项被高阶项吸收: T(n) = n³ + 100n² + 5000n,当 n = 10⁴ 时 n³ = 10¹²,而后两项加起来才 1.5×10⁷, 占比百万分之十五,完全可以忽略。

法则二 乘法法则:忽略常数系数

对任意正常数 c,有 O(c · f(n)) = O(f(n))。

因为 c 只是个放大倍数,不改变增长趋势:3n²、n²/2、100n² 全是 O(n²)。这条法则还告诉我们嵌套循环的复杂度是各层相乘: 外层 O(f)、内层 O(g),总复杂度 O(f·g)。例如外层 n 次、内层 log n 次,结果就是 O(n log n)。

法则三 常数一律记为 O(1)

无论一个操作要执行 1 次还是 1000 次,只要这个次数与 n 无关,就是 O(1),称为常量级。

请特别注意:O(1) 不是「只执行一次」。两条语句是 O(1), 一万条不含循环的语句也是 O(1);哈希表的一次查找平均也是 O(1)。 同理,O(n) 里的 n 不一定是数组长度——在图算法里它经常是顶点数 V 或边数 E, 在串算法里是串长 m、n。写复杂度时必须说清 n 指的是什么。

速算流程(考试直接用) 第一步:找出代码里与 n 有关的循环 / 递归,写出频度表达式; 第二步:把所有系数、低阶项、常数项删掉,只留最高阶项; 第三步:检查有没有嵌套相乘、有没有对数因子(循环变量倍增 / 折半)。 三步走完,答案自然落地。接下来我们就用 8 道例题把这套流程练到条件反射。

1.8 两道例题:手把手推导大 O

下面 2 道例题由浅入深,覆盖了考试和面试中 95% 的复杂度分析场景。每道题的格式都是固定的: 代码 → 逐行计数表 → 频度求和 → 化简得阶。请务必自己先遮住答案推一遍, 推不出来再看我的过程——只看不推,等于没学。

本题组的分析口径(三句话约定) ① 只统计与规模 n 有关的语句;for 的条件判断执行次数 = 循环执行次数 + 1(最后一次判假); ② 变量初始化、单条赋值、比较、四则运算都视为 O(1) 的基本操作; ③ 得到精确频度表达式后,删系数、删低阶、只留最高阶,得到大 O。

例 1 双层嵌套 —— O(n²)

// ex1_double_loop.cpp —— 双层嵌套:总次数 = 外层 × 内层
#include <iostream>

long long countPairs(int n) {
    long long cnt = 0;                       // 1
    for (int i = 1; i <= n; ++i) {           // 条件判断 n + 1 次
        for (int j = 1; j <= n; ++j) {       // 条件判断 n * (n + 1) 次
            ++cnt;                           // n * n 次
        }
    }
    return cnt;
}

// 变体:内层依赖外层(三角形循环),次数减半但阶不变
long long countTriples(int n) {
    long long cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)         // 内层次数 = i
            ++cnt;                           // 总次数 = 1 + 2 + ... + n = n(n+1)/2
    return cnt;
}

int main() {
    std::cout << countPairs(100) << '\n';    // 10000
    std::cout << countTriples(100) << '\n';  // 5050
    return 0;
}
语句频度化简后
cnt = 011
外层条件判断 i <= nn + 1n
内层条件判断 j <= nn × (n + 1) = n² + nn²
++cntn × n = n²n²
T(n) = 2n² + 2n + 2O(n²),平方阶

变体思考:countTriples 的总次数是 n(n+1)/2 = 0.5n² + 0.5n, 比 n² 少了一半,但阶仍然是 O(n²)。系数减半不改变阶—— 这是初学者最容易犯的错:看到「内层从 j ≤ i 变成 j ≤ n/2」就以为复杂度降级了, 其实还是同一量级。只有当「n 出现在指数或对数位置」时,改动才可能改变阶。

例 2 循环变量倍增 —— O(log n)

// ex2_double_step.cpp —— 倍增型循环:循环次数是对数级的
#include <iostream>

int steps(int n) {
    int cnt = 0;
    for (int i = 1; i < n; i *= 2) ++cnt;    // i 依次为 1, 2, 4, 8, ..., 2^k
    return cnt;
}

int stepsDiv(int n) {
    int cnt = 0;
    for (int i = n; i > 1; i /= 2) ++cnt;    // i 依次为 n, n/2, n/4, ...
    return cnt;
}

int main() {
    std::cout << steps(1000) << '\n';         // 10:因为 2^10 = 1024 > 1000
    std::cout << stepsDiv(1000) << '\n';      // 9
    return 0;
}

关键是找出循环变量 i 的通项,再让它满足退出条件:

第 k 次迭代时 i = 2k(k 从 0 开始)→ 退出条件 2k ≥ n → k ≥ log2n → 循环次数 ≈ log2n + 1
迭代次数 ki 的值是否继续
011 < n,继续
12继续
24继续
………
k2k当 2k ≥ n 时退出
T(n) = ⌊log₂n⌋ + 1O(log n),对数阶

变体思考:把 i *= 2 换成 i *= 3,次数变为 log₃n。 由换底公式 log₃n = log₂n / log₂3,只差一个常数因子,所以大 O 记号里对数的底数可以省略, 一律写成 O(log n)。这是面试常问的一个细节。另外,i /= 2 的写法次数为 ⌊log₂n⌋(n = 1000 时为 9),与倍增写法一致,同为 O(log n)。

1.8.1 两道例题速查表

题号代码形态频度推导关键结果
例 1双层嵌套T(n) = 2n² + 2n + 2外层 n × 内层 nO(n²)
例 2i *= 2 / i /= 2k ≈ log₂n + 1通项 i = 2kO(log n)
把它们连成一句话 看到循环就问「循环体执行多少次」:与 n 成正比 → O(n);是嵌套的乘积 → 相乘; 变量倍增或折半 → 出现 log。 递归式的推导不在这里展开;归并与二分的复杂度结论会在对应章节直接给出。

1.9 最好、最坏与平均时间复杂度

1.9.1 为什么同一个算法会有三个复杂度

算法运行时间不仅与问题规模 n 有关,还与输入数据的具体形态有关。 同样是顺序查找,要找的元素恰好在第一个位置,与恰好在最后一个位置,比较次数差了 n 倍。 如果只给一个笼统的「复杂度」,这个信息就丢失了。于是我们分三种口径:

在没有特别说明时,我们平常说的「这个算法是 O(?) 的」,默认指最坏情况。 因为最坏情况最容易分析(构造一个最差输入即可),而且是唯一能给用户承诺的指标。

1.9.2 顺序查找:把平均情况算到底

顺序查找(sequential search)从表头开始逐个比较,找到就返回下标。 设表长为 n,数组下标 1 ~ n,要找的元素为 key。分析前先做两条假设:

  1. 表中元素互不相同;
  2. 每个元素被查找的概率相等,即 pi = 1/n(等概率假设)。

查找第 i 个元素时,需要比较 i 次。于是成功查找的平均查找长度为:

ASL成功 = Σi=1..n pi · ci = Σi=1..n (1/n) · i = (1/n) · n(n+1)/2 = (n+1)/2

当 n 很大时,(n+1)/2 与 n 同阶,所以平均时间复杂度是 O(n)。 注意这里必须区分「平均比较次数」与「渐进复杂度」: 平均比较次数是 (n+1)/2(n = 8 时约 4.5 次),而渐近阶是 O(n),两者并不矛盾。

三种情况放在一起看:

情况触发输入比较次数渐进复杂度
最好要找的元素恰在第 1 个位置1O(1)
平均等概率分布,期望值(n+1)/2O(n)
最坏要找的元素在第 n 个位置,或根本不存在n(失败时 n 次)O(n)

如果概率不相等呢?那就老老实实按 pi 加权。例如已知 「查第 1 个元素的概率是 1/2,其余 n−1 个各为 1/(2(n−1))」,则 ASL = 1×(1/2) + Σi=2..n i/(2(n−1)) ≈ n/4,比等概率时快一倍。 这提示我们一个工程技巧:把最常查的元素放在表头,平均查找长度会显著下降 (「自适应线性表」就是这个思想,在第 10 讲会展开)。

0 2 4 6 8 比较次数 1 2 3 4 5 6 7 8 元素在表中的位置 i ASL = (n+1)/2 = 4.5(n = 8 时) 最好:1 次 最坏:8 次 查找第 i 个元素需比较 i 次
图 1-13 顺序查找:位置 i 需要 i 次比较,等概率下的平均值正好是 (n+1)/2

1.9.3 快速排序:三种情况天差地别

快速排序每轮选一个基准(pivot),把序列划分成「小于基准」和「大于基准」两段,再递归处理。 设一趟划分的代价为 O(n),则总复杂度取决于划分是否均衡:

这就是为什么工程实现要花力气「避免最坏情况」:随机选基准(随机化快排)、 三数取中、小区间改用插入排序(内省排序)都是为了让最坏情况几乎不出现。 第 11 讲 11.7 节会给出完整实现与对抗测试。

1.9.4 冒泡排序:可以提前结束的排序

冒泡排序每轮把当前最大值「冒」到末尾,共进行 n−1 轮,每轮比较 n−i 次。 总比较次数为 Σi=1..n−1(n−i) = n(n−1)/2,所以最坏与平均都是 O(n²)。 但加上「本轮无交换则提前退出」的优化后,最好情况出现了:

情况输入特征比较次数交换次数渐进复杂度
最好已经有序(如 1,2,3,…,n)n−10O(n)
平均随机排列≈ n(n−1)/4≈ n(n−1)/4O(n²)
最坏完全逆序(如 n,…,2,1)n(n−1)/2n(n−1)/2O(n²)

冒泡排序还有一个隐藏优点:稳定(相同关键字的相对次序不变),因为相邻比较时用的是严格 > 而不是 ≥。这也是「同一量级的算法之间还要比稳定性」的典型场景。

考点 三种复杂度在考试中的常见陷阱
  • 题目说「时间复杂度为 O(n²) 的排序算法」——如果只写最坏情况,冒泡、插入、选择、快排都符合; 但若问「最好情况能达到 O(n)」,只有冒泡(带优化)与直接插入可以,简单选择排序不行(它总是 n(n−1)/2 次比较)。
  • 「平均情况」必须说明概率假设。不说明假设就谈平均,是伪命题。
  • 最好情况的复杂度不能用来评价算法优劣——快排最好情况 O(n log n) 与归并排序相同, 但快排的最坏是 O(n²),归并的最坏仍是 O(n log n),这才是两者的分水岭。

1.10 常见复杂度增长对比

把常见的八种复杂度放在同一张表里,代入 n = 10、100、1000、10⁶ 四个规模, 能直观感受到「阶」这个概念的威力。下面的估算按「普通计算机每秒执行约 10⁸ 次基本操作」换算, 换算结果只是为了建立量级感,不必当成精确结论。

复杂度n = 10n = 100n = 1000n = 10⁶n = 10⁶ 时的直观感受
O(1)1111瞬间完成,与规模完全无关
O(log n)371020瞬间完成,n 翻倍只多 1 次
O(n)1010010³10⁶约 0.01 秒,轻松通过
O(n log n)3366499662×10⁷约 0.2 秒,排序算法的目标线
O(n²)10010⁴10⁶10¹²约 2.8 小时,不可接受
O(n³)10³10⁶10⁹10¹⁸约 317 年,必须换算法
O(2ⁿ)10241.3×10³⁰10³⁰¹天文数字n = 100 就已经算不完了
O(n!)3.6×10⁶9.3×10¹⁵⁷巨大巨大只能处理 n ≤ 10 左右的规模

请特别记住三条「红线」,它们决定了竞赛与工程中的算法选型:

1 10 100 10³ 10⁴ 10⁵ 10⁶ 运算次数(对数刻度) 1 4 7 10 13 16 数据规模 n(对数刻度纵轴,便于在同一张图里比较 1 与 10⁶) O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) 图例 纵轴取对数后, 曲线越陡 = 增长 越快。2ⁿ 呈直线 上升,说明它是 指数级爆炸。
图 1-14 六种常见复杂度的增长曲线对比(纵轴为对数刻度):n = 16 时 2ⁿ 已达 65536,而 log₂n 只有 4
怎么看这张图 纵轴是对数刻度,所以「看起来差不多高」其实差别巨大: 在 n = 16 处,O(1) 是 1 次、O(log n) 是 4 次、O(n) 是 16 次、O(n log n) 是 64 次、 O(n²) 是 256 次、O(2ⁿ) 是 65536 次。把横轴拉到 n = 10⁶, O(n²) 与 O(n log n) 的差距会扩大到 5 万倍——这就是为什么「降一个阶」比「优化常数」重要得多。
// growth_timing.cpp —— 亲手实测三种复杂度的增长(-O2 编译,观察列之间的倍数关系)
#include <iostream>
#include <chrono>

int main() {
    std::cout << "n\t\tO(n)\t\tO(n log n)\tO(n^2)\n";
    for (int n = 1000; n <= 16000; n *= 2) {
        volatile long long sink = 0;                 // volatile:阻止编译器优化掉整个循环

        auto t0 = std::chrono::steady_clock::now();
        long long s1 = 0;
        for (int i = 0; i < n; ++i) s1 += i;         // O(n)

        auto t1 = std::chrono::steady_clock::now();
        long long s2 = 0;
        for (int i = 0; i < n; ++i)                  // O(n log n):外层 n,内层 log n
            for (int j = 1; j < n; j *= 2) s2 += j;

        auto t2 = std::chrono::steady_clock::now();
        long long s3 = 0;
        for (int i = 0; i < n; ++i)                  // O(n^2)
            for (int j = 0; j < n; ++j) s3 += i * j;

        auto t3 = std::chrono::steady_clock::now();
        sink = s1 + s2 + s3;
        (void)sink;

        auto ms = [](auto a, auto b) {               // C++14 泛型 lambda
            return std::chrono::duration<double, std::milli>(b - a).count();
        };
        std::cout << n << "\t\t" << ms(t0, t1) << "\t"
                  << ms(t1, t2) << "\t\t" << ms(t2, t3) << '\n';
    }
    return 0;
}
// 典型输出(不同机器数值不同,但规律一致):
// n        O(n)      O(n log n)   O(n^2)
// 1000     0.002     0.003        0.9
// 2000     0.003     0.007        3.6      ← O(n^2) 列大约 ×4,因为它随 n^2 增长
// 4000     0.006     0.015        14.3
// 8000     0.012     0.031        57.2
// 16000    0.024     0.066        228.9

1.11 空间复杂度

1.11.1 定义:只算「额外」的那部分

空间复杂度(space complexity)记作 S(n),是对一个算法在运行过程中 临时占用存储空间大小的量度,同样用大 O 记号表示。 一个算法在内存里占的地方可以分成三块,我们必须分清哪块算、哪块不算:

组成部分内容是否计入 S(n)原因
程序代码本身编译后的指令、常量不计入与问题规模 n 无关,是个固定开销
输入数据待处理的数组、矩阵、字符串不计入否则任何算法都至少是 O(n),无法比较优劣
辅助空间临时变量、递归栈帧、缓冲区、辅助数组计入这才是「算法自己额外花的钱」

所以严格来说,S(n) 指的是辅助空间(auxiliary space)。 例如「把数组原地反转」:输入数组 n 个元素不算,只用了一个临时变量 t, 于是 S(n) = O(1);而「归并排序」需要一个与原数组等长的缓冲区 buf, 所以 S(n) = O(n)。

1.11.2 原地算法(in-place algorithm)

如果算法所需的辅助空间与问题规模 n 无关,即 S(n) = O(1), 就称它为原地算法。这在实际工程中价值极高:处理 10⁸ 个整数时, 原地算法可以直接在用户给的内存上操作,而非原地算法可能要再申请几百 MB。

易错:数组反转到底是 O(1) 还是 O(n)? 用swap(a[i], a[n-1-i]) 的双指针法反转数组,辅助空间是 O(1), 尽管它改了 n 个元素、执行了 n/2 次交换——时间与空间是两码事。 用「另开一个数组倒着存」的办法则是 O(n) 空间。 考试喜欢在这里设陷阱:问「时间 O(n)、空间 O(1) 的反转算法」,答案就是双指针法。

1.11.3 递归的栈空间必须计入

这是空间复杂度里最容易漏掉的一项。每次函数调用,系统都要在运行时栈上压入一个 栈帧(stack frame),里面保存参数、局部变量和返回地址。函数返回时栈帧才弹出。 所以递归算法的空间复杂度至少等于最大递归深度。

S递归(n) = O(最大递归深度) + O(每层额外申请的堆空间)

以递归求阶乘为例:fact(4) 会依次调用 fact(3)、fact(2)、fact(1), 四个栈帧同时存在,直到最内层返回才开始逐个弹出。因此最大深度为 n,S(n) = O(n)。

// factorial_space.cpp —— 同样是 O(n) 时间,空间却可能差一个量级
#include <iostream>

// 递归版:时间 O(n),空间 S(n) = O(n) —— n 个栈帧同时存在
long long factRec(int n) {
    if (n <= 1) return 1;              // 递归基
    return n * factRec(n - 1);         // 本层必须等下层返回,栈帧一直压着
}

// 迭代版:时间 O(n),空间 S(n) = O(1) —— 只用了 r、i 两个变量
long long factIter(int n) {
    long long r = 1;
    for (int i = 2; i <= n; ++i) r *= i;
    return r;
}

int main() {
    std::cout << factRec(10) << '\n';    // 3628800
    std::cout << factIter(20) << '\n';   // 2432902008176640000
    // factRec(1000000);                 // 栈溢出 Stack Overflow:O(n) 栈空间也会爆
    return 0;
}
运行时栈(每进入一层递归就压入一个栈帧) 递归返回时自底向上逐层弹栈 fact(4) n = 4 保存返回地址 → main fact(3) n = 3 保存返回地址 → fact(4) fact(2) n = 2 保存返回地址 → fact(3) fact(1) n = 1 命中递归基,开始返回 调用深度增加 ← 栈底(先压入) ← 栈顶(后压入) ① fact(1) 触底 → 返回 1 ② fact(2) = 2 × 1 = 2 ③ fact(3) = 3 × 2 = 6 ④ fact(4) = 4 × 6 = 24 最大栈深度 = n ⟹ S(n) = O(n)
图 1-15 递归求 n! 时的调用栈:任一时刻栈里有 n 个栈帧,所以 S(n) = O(n)

再看斐波那契数列,它是「时间与空间反差」的最佳教材。朴素递归写法 fib(n) = fib(n−1) + fib(n−2) 会展开成一棵指数级的递归树, 时间 O(2ⁿ);但注意:它同一时刻只保留一条从根到叶的路径, 算完左子树再去算右子树时,左子树的栈帧早已弹出。所以它的空间只有 O(n)。

这个「时间指数、空间线性」的反差非常反直觉,也是理解递归调用机制的试金石。 记住判断栈空间的方法:不是在递归树上有多少个结点,而是任意时刻同时存活多少层。

// fib_space.cpp —— 斐波那契:朴素递归时间 O(2^n)、空间 O(n);记忆化后时间 O(n)
#include <iostream>
#include <vector>

// 朴素递归:子问题重复计算,时间 O(2^n);但递归树任意时刻只走一条路径,空间 O(n)
long long fibNaive(int n) {
    if (n < 2) return n;                        // fib(0)=0, fib(1)=1
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// 记忆化搜索:用 O(n) 的表换掉重复计算,时间降到 O(n),空间 O(n)(表 O(n) + 栈 O(n))
long long fibMemo(int n, std::vector<long long>& memo) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];          // 命中缓存,直接返回,不再往下递归
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// 递推写法(滚动变量):时间 O(n),空间 O(1) —— 空间优化的极致
long long fibIter(int n) {
    long long a = 0, b = 1;                     // 只保留最近两项
    for (int i = 0; i < n; ++i) { long long t = a + b; a = b; b = t; }
    return a;
}

int main() {
    std::cout << fibNaive(30) << '\n';          // 832040:n 再大就明显变慢
    std::vector<long long> memo(91, -1);
    std::cout << fibMemo(90, memo) << '\n';     // 2880067194370816120
    std::cout << fibIter(90) << '\n';          // 同上
    return 0;
}
f(5) f(4) f(3) f(3) f(2) f(2) f(1) f(1) f(0) … … 叶子 时间:每层子问题翻倍 总结点数 ≈ 2ⁿ,重复计算极多 ⟹ T(n) = O(2ⁿ) 空间:同一时刻只保留 一条根到叶的路径 ⟹ S(n) = O(n) 优化:f(3) 被算了 2 次, f(2) 被算了 3 次 —— 记忆化 或递推可把时间降到 O(n) (动态规划的主角)
图 1-16 斐波那契朴素递归的调用树:结点数指数级(时间),但深度只有 n(空间)

1.11.4 时间与空间的取舍

最后强调一个实用的判断顺序:分析一个算法时,先看时间,再看空间。 因为绝大多数场合时间是瓶颈;只有当内存成为硬约束(嵌入式、超大矩阵、流式数据)时, 空间才上升为第一指标。而「时间换空间」与「空间换时间」的取舍, 贯穿了本课程几乎每一章的算法设计——哈希表(空间换时间)、滚动数组(时间换空间)、 记忆化搜索(空间换时间)都是这个思想的产物。