第 01 讲 绪论:数据结构与算法分析
这一讲不写复杂算法,只做一件事:把「数据结构」这四个字拆开揉碎,让你知道后面 14 讲要学的每一个结构 究竟在解决什么问题;再交给你一把尺子——大 O 记号,用来衡量任何一个算法的快慢与省费。
- 先立概念:数据、数据元素、数据项、数据对象四个词经常被混用,考试却专挑它们出选择题。
- 再分两层:逻辑结构(跟计算机无关的关系)与存储结构(内存里怎么摆),两层分清,后面所有结构都是这两层的组合。
- 然后抽象:抽象数据类型 ADT 把「能做什么」和「怎么做」彻底分开,这是工程代码能长期维护的根本原因。
- 最后量尺:算法效率不看秒表看渐近,本章给出大 O 的严格定义、三条推导法则、8 道手推例题。
- 顺手打底:末尾 43 条中英对照术语表覆盖全课程,建议打印出来贴在书桌前。
1.1 四个底层术语:数据、数据元素、数据项、数据对象
这四个词是层层包含的,先在最熟悉的场景——学生成绩表——里把它们一次性认清:
- 数据 data
- 能输入计算机并被程序识别处理的符号集合。整数
65与字符'A'在内存里都是0x41——同一份存储,不同解释即不同数据。 - 数据项 data item
- 不可再分的最小单位,也叫字段。如「学号 = 1001」;再往下拆成 1、0、0、1 就失去含义了。
- 数据元素 data element
- 数据的基本单位,由若干数据项组成,也叫记录或结点。如「张三 1001 计科1班 92」这一整条记录。
- 数据对象 data object
- 性质相同的数据元素的集合。全班成绩记录格式一致,构成一个数据对象。
要特别注意数据对象与数据结构的区别:数据对象回答「有哪些成员」,数据结构回答 「成员之间是什么关系」。下面这张图把四者的包含关系画了出来——
1.1.1 数据结构的严格定义
把上面的铺垫收拢,给出教材上那个必须一字不差记住的定义:
这个定义里最值钱的是「关系」两个字。数组里有下标相邻关系,链表里有指针指向关系, 二叉树里有父子关系,图里有邻接关系。所以学一个新结构时,第一句要问的就是: 它的元素之间到底是什么关系?
但这还不完整。只谈关系,算法没法运行,因为关系必须落到内存上。于是数据结构包含三个方面的内容:
- 逻辑结构:数据元素之间的抽象关系,面向问题、面向人,与计算机无关;
- 存储结构:逻辑结构在计算机存储器中的表示,也叫物理结构,与机器、语言实现有关;
- 数据的运算:定义在该结构上的一组操作(增、删、改、查、遍历、排序……), 运算「定义在逻辑结构上」,但「实现依赖于存储结构」。
这三者的关系可以用一句话概括:逻辑结构决定「能做什么运算」,存储结构决定「这些运算要花多少代价」。 后面第 1.4 节会用顺序表和链表把这个结论演示得非常具体。
1.2 逻辑结构:四类基本结构
逻辑结构只关心一件事:元素之间有没有关系、是什么关系。按关系的复杂程度,可以把常见的逻辑结构 分成四类:集合结构、线性结构、树形结构、图形结构(网状结构)。 这四类几乎覆盖了本课程后面全部的章节,所以务必把它们的图示刻进脑子里。
1.2.1 集合结构:只有「同属一伙」这一种关系
集合结构中的元素除了「同属于一个集合」之外,没有任何其他关系。元素之间没有次序、没有层级、 没有邻接。它是四类里关系最弱的一种。
典型的例子是并查集(Union-Find)里维护的等价类,或者 C++ 的 std::set:
你只关心「某个元素在不在这个集合里」,不关心它排第几、旁边是谁。
集合结构的运算通常是:判断元素是否属于集合、求并集、求交集、求差集。
1.2.2 线性结构:一对一的前驱后继
线性结构就是一条链:所有元素排成一列,每个元素最多只有一个直接前驱、一个直接后继, 并且链条有头有尾——恰好一个元素没有前驱(首元素),恰好一个元素没有后继(尾元素)。 教材上那四条性质,说的就是这一件事。
线性结构是本课程最庞大的家族:线性表、栈、队列、双端队列、串、数组都属于线性结构。 它们之间的区别只在于「限制在哪里」——栈限制只能在一端插入删除,队列限制一端进另一端出, 串限制元素是字符且操作以「子串」为单位。抓住这条主线,第 2~6 讲会非常轻松。
1.2.3 树形结构:一对多的层次关系
树形结构中,数据元素之间存在一对多的层次关系:每个元素最多有一个直接前驱(父结点), 但可以有多个直接后继(孩子结点)。树形结构最贴近现实世界的组织方式——文件目录、家族谱系、 公司组织架构、HTML 文档结构,全都是树。
树形结构天生适合表达「分类」与「层次」:从根到叶的一条路径就是一次「细分」。 也正因为层次的存在,树上的查找、插入、删除可以做到 O(log n)(平衡树), 这是线性结构做不到的——这就是「结构决定算法」的最好例证。
1.2.4 图形结构(网状结构):多对多
图形结构中,数据元素之间存在多对多的任意关系:任一元素都可以与任意多个其他元素相邻。 图是四类逻辑结构里表达能力最强、也最难处理的:交通网、社交网络、课程先修关系、 状态机、依赖关系图,都只能用它描述。
强表达能力的代价是算法复杂度。比如「求两点间最短路径」,在树上是唯一的简单路径(沿树走即可), 在图上却要考虑指数级的路径数量,于是才有了 Dijkstra、Floyd、Bellman-Ford 这些算法。
1.2.5 换个切法:线性结构与非线性结构
四类结构还可以再粗分一刀,这也是考试里出现频率极高的一个划分: 线性结构(线性表、栈、队列、串、数组)与非线性结构(集合、树、图)。 判断标准只有一个:元素之间是否是一对一的线性关系。
| 划分 | 包含的逻辑结构 | 关系特征 | 本课程对应章节 | 典型运算代价 |
|---|---|---|---|---|
| 线性结构 | 线性表、栈、队列、双端队列、串、数组 | 一对一,有唯一首元素与唯一尾元素 | 第 02 ~ 06 讲 | 按位置访问 O(1)(顺序存储)或 O(n)(链式) |
| 非线性结构 | 集合、树形结构、图形结构 | 一对多(树)、多对多(图)、无关系(集合) | 第 07 ~ 09 讲 | 树查找 O(log n)、图遍历 O(V+E) |
1.3 存储结构(物理结构):四种落地手段
逻辑结构是纸上谈兵,它必须被放进计算机的存储器里才能真正跑起来。存储结构(也叫物理结构) 研究的就是:数据元素本身怎么存,元素之间的关系怎么存。请注意这句话有两半,很多人只做了前一半。 只把数据丢进内存是不够的,你还得把「谁挨着谁」「谁指向谁」也存下来——而表示关系的方式, 恰恰是区分不同存储结构的唯一标准。
教材上把存储结构分成四种:顺序存储、链式存储、索引存储、散列存储。前两种是基础, 后两种是「加外挂」的思路。下面逐一拆解。
1.3.1 顺序存储:用「物理相邻」表示「逻辑相邻」
顺序存储把逻辑上相邻的元素存放在物理位置也相邻的存储单元里,元素之间的逻辑关系 不需要额外空间来记录——因为「挨着」这件事本身就蕴含了「相邻」这个关系。 这就是顺序存储最漂亮的地方:关系是免费的。
由于每个元素占用的字节数固定,第 i 个元素的地址可以直接算出来:
有了这个公式,随机访问(random access)就成了可能:访问第 1 个元素和访问第 10⁶ 个元素, 花的时间完全一样,都是 O(1)。代价也很直接——插入和删除时,为了保持「物理相邻」, 必须成片地搬移元素,最坏 O(n)。另外,顺序存储通常要求预先分配一段连续空间, 空间不够要扩容(重新申请 + 整体拷贝),空间富余则浪费。
典型例子:C++ 的 std::vector、std::array、字符串的字面量存储、
完全二叉树的顺序存储(第 07 讲)。
1.3.2 链式存储:用「指针」显式记录关系
链式存储不要求物理相邻,它在每个元素上附加指针(pointer),用指针的取值 显式地指出下一个元素在哪儿。这时「关系」不再免费——每个结点都要多花几个字节来存指针。 换来的是巨大的灵活性:
- 插入删除快:只要改几条指针,不必搬移别的元素(前提是已经拿到位置);
- 空间按需分配:来一个结点申请一个结点,不需要大块连续内存,不会因扩容整体搬移;
- 失去随机访问:想找第 i 个结点,只能从头指针开始一个一个数过去,O(n)。
典型例子:单链表、双向链表、循环链表、静态链表(用数组下标模拟指针)、 二叉链表(第 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 × 内层 n | O(n²) | |
| 2 | i *= 2 / i /= 2 | k ≈ log₂n + 1 | 通项 i = 2k | O(log n) | |
| 3 | i = i * i / i = √i | k ≈ log₂log₂n + 1 | 通项 i = 22k | O(log log n) | |
| 4 | 归并排序 T(n) = 2T(n/2) + cn | T(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) + c | T(n) = c(log₂n + 1) | 每层常数代价 × log 层 | O(log n) |
下面这张图是本章最重要的一张图:同一个逻辑结构(线性表)分别用顺序存储与链式存储实现。 请特别留意图中标注的内存地址与指针箭头的差别。
1.4 逻辑结构与存储结构的关系
1.4.1 为什么逻辑结构独立于存储结构
逻辑结构描述的是「元素之间的关系」,这个关系是数学意义上的关系,与元素在内存第几个字节毫无关系。 同一份逻辑关系,你可以用 C++ 写,也可以用 Python 写;可以放在 32 位机器上,也可以放在 64 位机器上。 逻辑结构不变,只是因为它压根没提过「地址」这两个字。
这个「独立性」不是文字游戏,它带来两个非常实用的好处:
- 可以脱离实现思考算法。分析算法时我们只关心「这个操作要访问几个元素」, 不关心机器是几核、内存多快。这就是大 O 记号能够成立的前提——它只统计运算次数的增长趋势。
- 可以换实现而不改接口。今天用顺序表实现了栈,明天发现数据量太大需要换成链栈, 只要 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)。
反过来,在「已知前驱结点 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;
}
| 运算 | 顺序存储(顺序表) | 链式存储(单链表) | 原因 |
|---|---|---|---|
| 按位查找第 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 个或多个输出,没有输出的算法毫无意义 | 算完什么也不留下,等于白算 | 只做计算却从不使用结果的代码 |
1.6.3 算法与程序的区别
很多人把两者当成同义词,其实它们有明确区别:
| 比较维度 | 算法 algorithm | 程序 program |
|---|---|---|
| 存在形式 | 一种解决问题的方法 / 思想,可以脱离语言存在 | 用某种程序设计语言写成的具体代码 |
| 有穷性 | 必须满足,否则不能叫算法 | 可以不满足:操作系统、服务器主循环会一直运行 |
| 描述精度 | 可以用自然语言、流程图、伪码描述 | 必须严格符合语言的语法与语义 |
| 是否含 IO / 交互 | 只关心「计算」,不关心界面与文件 | 可以包含输入输出、图形界面、网络通信 |
| 关系 | 算法 + 数据结构 + 语言实现 = 程序;一个算法可以有无数个程序实现 | |
一句话记住:程序可以永远不结束,算法不行。这也是为什么我们能在纸上分析算法, 却往往难以在纸上分析一个完整程序。
1.6.4 评价算法的四个维度
同一个问题往往有很多算法,怎么比?教材给了四个维度,注意它们是有优先级的:
- 正确性(correctness)——最高优先级。算法应当能正确处理合法输入,并且对典型、 苛刻、边界输入都能给出符合规格说明的结果。一个跑得飞快但答案是错的算法,价值是负的。
-
可读性(readability)——第二优先级。算法首先是给人看的,其次才是给机器执行的。
可读性差的代码无法维护、无法调试、无法被别人复用。变量名
a1、a2、tmp2泛滥的代码,两周后连作者自己都看不懂。 - 健壮性(robustness)——面对非法输入时的表现。用户输入了负数、字符串、空指针, 算法应该给出恰当反应(报错、返回错误码、使用默认值),而不是崩溃或悄悄算出一个错答案。
- 效率(efficiency)——包括时间效率(运行快慢)与存储效率(占用空间大小), 两者往往互相矛盾:想快就得多花内存(空间换时间),想省内存就得多算几遍(时间换空间)。
为什么把效率排在最后?因为前三个不达标时,效率毫无意义。但反过来说, 当输入规模达到 10⁶、10⁷ 时,效率就成了唯一的瓶颈——一个 O(n²) 的「正确」算法 在 n = 10⁶ 时要跑上万亿次操作,根本等不到它输出正确答案。这也是本讲后半部分 要花大力气研究复杂度分析的原因。
1.7 算法效率的度量:从掐秒表到渐近分析
1.7.1 事后统计法 vs 事前分析估算法
想知道一个算法快不快,最直接的办法就是跑一遍看时间。这叫事后统计法。 它直观,但作为研究方法几乎不可用,原因有四条:
- 必须先把程序写出来并跑起来,如果算法本身是错的或写不出来,就无从统计;
- 时间依赖于机器硬件(CPU 主频、缓存大小)、编译选项(
-O0还是-O2)、 运行时环境(有没有别的进程抢 CPU),换个环境结论就变了; - 测试数据规模太小看不出差别,规模太大又等不起;不测到 n = 10⁶ 以上, 往往分辨不出 O(n log n) 和 O(n²);
- 只能比较「已实现的几个算法」,无法预测「换一种思路会不会更好」。
所以我们改用在纸面上就能做的事前分析估算法:认为算法运行时间正比于其中基本操作的执行次数, 只考察当问题规模 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² | |
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 指的是什么。
1.8 两道例题:手把手推导大 O
下面 2 道例题由浅入深,覆盖了考试和面试中 95% 的复杂度分析场景。每道题的格式都是固定的: 代码 → 逐行计数表 → 频度求和 → 化简得阶。请务必自己先遮住答案推一遍, 推不出来再看我的过程——只看不推,等于没学。
例 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 = 0 | 1 | 1 |
外层条件判断 i <= n | n + 1 | n |
内层条件判断 j <= n | n × (n + 1) = n² + n | n² |
++cnt | n × n = n² | n² |
| T(n) = 2n² + 2n + 2 | O(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 的值 | 是否继续 |
|---|---|---|
| 0 | 1 | 1 < n,继续 |
| 1 | 2 | 继续 |
| 2 | 4 | 继续 |
| … | … | … |
| k | 2k | 当 2k ≥ n 时退出 |
| T(n) = ⌊log₂n⌋ + 1 | O(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 × 内层 n | O(n²) |
| 例 2 | i *= 2 / i /= 2 | k ≈ log₂n + 1 | 通项 i = 2k | O(log n) |
1.9 最好、最坏与平均时间复杂度
1.9.1 为什么同一个算法会有三个复杂度
算法运行时间不仅与问题规模 n 有关,还与输入数据的具体形态有关。 同样是顺序查找,要找的元素恰好在第一个位置,与恰好在最后一个位置,比较次数差了 n 倍。 如果只给一个笼统的「复杂度」,这个信息就丢失了。于是我们分三种口径:
- 最好情况(best case):在所有规模为 n 的输入中,使算法执行最少基本操作的输入所对应的复杂度。 它给出的是乐观下界,实用价值有限,但可以用来判断「最理想能到多快」。
- 最坏情况(worst case):使算法执行最多基本操作的输入所对应的复杂度。 它给出的是保证——「无论输入多恶劣,都不会比这个更慢」。 实时系统、竞赛做题、工程 SLA 都以最坏情况为准。
- 平均情况(average case):在所有可能的输入上,按出现概率对操作次数做加权平均。 它最贴近真实体验,但需要假设输入的概率分布,数学上也最难算。
在没有特别说明时,我们平常说的「这个算法是 O(?) 的」,默认指最坏情况。 因为最坏情况最容易分析(构造一个最差输入即可),而且是唯一能给用户承诺的指标。
1.9.2 顺序查找:把平均情况算到底
顺序查找(sequential search)从表头开始逐个比较,找到就返回下标。 设表长为 n,数组下标 1 ~ n,要找的元素为 key。分析前先做两条假设:
- 表中元素互不相同;
- 每个元素被查找的概率相等,即 pi = 1/n(等概率假设)。
查找第 i 个元素时,需要比较 i 次。于是成功查找的平均查找长度为:
当 n 很大时,(n+1)/2 与 n 同阶,所以平均时间复杂度是 O(n)。 注意这里必须区分「平均比较次数」与「渐进复杂度」: 平均比较次数是 (n+1)/2(n = 8 时约 4.5 次),而渐近阶是 O(n),两者并不矛盾。
三种情况放在一起看:
| 情况 | 触发输入 | 比较次数 | 渐进复杂度 |
|---|---|---|---|
| 最好 | 要找的元素恰在第 1 个位置 | 1 | O(1) |
| 平均 | 等概率分布,期望值 | (n+1)/2 | O(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 讲会展开)。
1.9.3 快速排序:三种情况天差地别
快速排序每轮选一个基准(pivot),把序列划分成「小于基准」和「大于基准」两段,再递归处理。 设一趟划分的代价为 O(n),则总复杂度取决于划分是否均衡:
- 最好情况:每次划分都把序列对半分,递推式 T(n) = 2T(n/2) + O(n), 由例 4 得 O(n log n);
- 最坏情况:每次划分都极不均衡(例如对已排好序的序列取首元素为基准, 每次只能分出 1 个元素),递推式退化为 T(n) = T(n−1) + O(n), 累加得 O(n²);
- 平均情况:随机输入下,平均划分比例虽然有波动,但期望深度仍是 O(log n), 数学上可以证明平均复杂度为 O(n log 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−1 | 0 | O(n) |
| 平均 | 随机排列 | ≈ n(n−1)/4 | ≈ n(n−1)/4 | O(n²) |
| 最坏 | 完全逆序(如 n,…,2,1) | n(n−1)/2 | n(n−1)/2 | O(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 = 10 | n = 100 | n = 1000 | n = 10⁶ | n = 10⁶ 时的直观感受 |
|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 瞬间完成,与规模完全无关 |
| O(log n) | 3 | 7 | 10 | 20 | 瞬间完成,n 翻倍只多 1 次 |
| O(n) | 10 | 100 | 10³ | 10⁶ | 约 0.01 秒,轻松通过 |
| O(n log n) | 33 | 664 | 9966 | 2×10⁷ | 约 0.2 秒,排序算法的目标线 |
| O(n²) | 100 | 10⁴ | 10⁶ | 10¹² | 约 2.8 小时,不可接受 |
| O(n³) | 10³ | 10⁶ | 10⁹ | 10¹⁸ | 约 317 年,必须换算法 |
| O(2ⁿ) | 1024 | 1.3×10³⁰ | 10³⁰¹ | 天文数字 | n = 100 就已经算不完了 |
| O(n!) | 3.6×10⁶ | 9.3×10¹⁵⁷ | 巨大 | 巨大 | 只能处理 n ≤ 10 左右的规模 |
请特别记住三条「红线」,它们决定了竞赛与工程中的算法选型:
- n ≤ 10⁶ 时,O(n) 与 O(n log n) 都可以放心用;
- n > 10⁴ 时,O(n²) 基本告别,必须换成 O(n log n) 或 O(n);
- n > 20 时,O(2ⁿ) 就只能靠剪枝、记忆化或彻底换思路(这正对应动态规划优化)。
// 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。
swap(a[i], a[n-1-i]) 的双指针法反转数组,辅助空间是 O(1),
尽管它改了 n 个元素、执行了 n/2 次交换——时间与空间是两码事。
用「另开一个数组倒着存」的办法则是 O(n) 空间。
考试喜欢在这里设陷阱:问「时间 O(n)、空间 O(1) 的反转算法」,答案就是双指针法。
1.11.3 递归的栈空间必须计入
这是空间复杂度里最容易漏掉的一项。每次函数调用,系统都要在运行时栈上压入一个 栈帧(stack frame),里面保存参数、局部变量和返回地址。函数返回时栈帧才弹出。 所以递归算法的空间复杂度至少等于最大递归深度。
以递归求阶乘为例: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;
}
再看斐波那契数列,它是「时间与空间反差」的最佳教材。朴素递归写法
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;
}
1.11.4 时间与空间的取舍
最后强调一个实用的判断顺序:分析一个算法时,先看时间,再看空间。 因为绝大多数场合时间是瓶颈;只有当内存成为硬约束(嵌入式、超大矩阵、流式数据)时, 空间才上升为第一指标。而「时间换空间」与「空间换时间」的取舍, 贯穿了本课程几乎每一章的算法设计——哈希表(空间换时间)、滚动数组(时间换空间)、 记忆化搜索(空间换时间)都是这个思想的产物。