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

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 换个切法：线性结构与非线性结构

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

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.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)。

反过来，在「已知前驱结点 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;
}

1.5 抽象数据类型 ADT：把「能做什么」和「怎么做」分开

1.5.1 ADT 的定义

抽象数据类型（Abstract Data Type, ADT）是指一个数学模型以及定义在该模型上的一组操作。 它由三部分组成：

• 数据对象：这个类型里能放哪些数据（例如「所有整数」）；
• 数据关系：这些数据之间满足什么结构（例如「一对一线性关系」）；
• 基本操作：能对它做哪些事，每个操作的语义是什么（做什么，而不是怎么做）。

ADT 的关键词是「抽象」。抽象的意思是：只保留「做什么」的说明，隐藏「怎么做」的细节。 你家里的电视机遥控器就是一个完美的 ADT——它告诉你「按 + 键音量变大」， 但绝不告诉你红外编码怎么发、功放电路怎么调。你也不需要知道。

在 C++ 里，ADT 可以用类（class）来落地：用 public 成员函数描述基本操作（接口）， 用 private 成员描述内部实现（数据与细节）；教材还常配上模板（template）支持泛型、 用纯虚函数定义接口契约。但请记住一句话：类只是表达 ADT 的一种语法外壳。 ADT 真正规定的是「有哪些操作、每个操作是什么语义」，至于这些操作用成员函数写还是用普通函数写， ADT 并不关心。竞赛代码里没有类、没有模板、没有虚函数，我们直接用 「全局数组 + 一组自由函数」表达同一个 ADT：函数名与教材 ADT 里的操作一一对应。

1.5.2 线性表 ADT 的接口约定（C++）

下面这段代码就是「线性表」这个 ADT 的完整规格说明。开头注释里那段用伪码写的形式化描述， 是教材里描述 ADT 的标准格式：数据对象 D、数据关系 R、基本操作 P；紧接着的每一个自由函数， 就是这份约定里的一个基本操作。

// list_adt.cpp —— 线性表的 ADT：先把「能做哪些事」定下来，不管「怎么做」
#include <bits/stdc++.h>
using namespace std;

/* ADT 的规格说明（教材用伪码写，这里保留原味）：
     ADT List {
       数据对象：D = { a_i | a_i ∈ ElemSet, i = 1..n, n ≥ 0 }
       数据关系：R = { <a_(i-1), a_i> | i = 2..n }        // 一对一的前驱后继
       基本操作：InitList / ListLength / GetElem / ListInsert / ListDelete / ListTraverse
     } ADT List

   注意：上面一个字都没提「数据放数组还是链表、容量怎么扩」——
   那些属于实现，不属于 ADT。接口一旦定下，实现可以有好几份。 */

const int MAXN = 100005;
int a[MAXN], n = 0;                       // 存储细节：调用方看不见这些

void initList()            { n = 0; }     // 清空
int  listLength()          { return n; }  // 求长度
int  getElem(int i)        { return a[i - 1]; }        // 取第 i 个
bool listInsert(int i, int x) {                        // 在第 i 个位置插入 x
    for (int k = n; k >= i; --k) a[k] = a[k - 1];
    a[i - 1] = x; ++n; return true;
}
bool listDelete(int i, int &e) {                       // 删除第 i 个，用 e 带回其值
    e = a[i - 1];
    for (int k = i - 1; k < n - 1; ++k) a[k] = a[k + 1];
    --n; return true;
}
void listTraverse() {                                  // 依次访问每个元素
    for (int i = 0; i < n; ++i) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
}

int main() {
    initList();
    for (int i = 1; i <= 5; ++i) listInsert(listLength() + 1, i * 10);
    printf("长度 %d，第 3 个是 %d，内容：", listLength(), getElem(3));
    listTraverse();
    int e; listDelete(1, e);
    printf("删掉 %d 后剩 %d 个：", e, listLength());
    listTraverse();
    return 0;
}

1.5.3 「抽象」到底体现在哪里

判断一个设计是否「抽象」，有一个很实用的测试：把实现整个换掉，调用方的代码需要改几行？ 如果一行都不用改，说明抽象是干净的；如果要改十处，那说明调用方偷偷依赖了实现细节。

// adt_client.cpp —— 体会 ADT 的作用：内部实现全换了，调用方一行都不用改
//
// 同一个线性表，用两套完全不同的存储各实现一遍：
//   数组版：元素在连续内存里         链表版：结点散在堆上，靠指针串起来
// 而调用方 use() 只认操作名和语义，根本不知道背后是哪种写法。
#include <bits/stdc++.h>
using namespace std;

namespace arrImpl {                    // 实现一：顺序存储
    int a[1005], n = 0;
    void init() { n = 0; }
    int  size() { return n; }
    void insert(int i, int x) {        // 第 i 个位置插入：后继整体后移 O(n)
        for (int k = n; k >= i; --k) a[k] = a[k - 1];
        a[i - 1] = x; ++n;
    }
    void traverse() { for (int i = 0; i < n; ++i) printf("%d ", a[i]); }
}

namespace linkImpl {                   // 实现二：链式存储（带头结点）
    struct Node { int val; Node *nxt; };
    Node *head = nullptr;
    void init() { head = new Node{0, nullptr}; }
    int  size() { int c = 0; for (Node *p = head->nxt; p; p = p->nxt) ++c; return c; }
    void insert(int i, int x) {        // 先走到第 i-1 个结点，再改两条指针
        Node *p = head;
        for (int k = 1; k < i; ++k) p = p->nxt;
        p->nxt = new Node{x, p->nxt};
    }
    void traverse() { for (Node *p = head->nxt; p; p = p->nxt) printf("%d ", p->val); }
}

/* ★ 下面这一行决定用哪个实现：改成 linkImpl 即可，其余一个字都不用动。
     用「命名空间 + 别名」表达「同一组操作」，比类加虚函数省事得多。 */
namespace impl = arrImpl;

/* 调用方：只用了 ADT 约定的那几个操作名，看不到、也没用到任何实现细节。
   所以 impl 指向谁，这段代码都不用改 —— 这就是抽象的价值。 */
void use() {
    impl::init();
    for (int i = 1; i <= 5; ++i) impl::insert(i, i * i);
    printf("元素个数 = %d，内容：", impl::size());
    impl::traverse();
    printf("\n");
}

int main() {
    use();                             // 输出：元素个数 = 5，内容：1 4 9 16 25
    return 0;
}

1.6 算法及其特性

1.6.1 算法的定义

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

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

1.6.2 算法的五大特性

1.6.3 算法与程序的区别

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

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

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 增大时这个次数的增长趋势，忽略常数与低阶项。 这就是「渐近分析」，也是整门课衡量算法优劣的统一语言。

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 变大后被彻底淹没。

1.7.3 大 O 记号的严格定义

上面我们反复说「同阶」，现在把它变成一个可以写进证明里的定义。这是本章必须逐字记住的第二个定义：

把定义拆成三块来看，每一块都有它的用意：

• 「存在正常数 c」：意思是允许你放大任意一个常数倍。因为常数倍只影响「快 3 倍还是慢 5 倍」， 不影响「n 翻倍时耗时翻几倍」这种本质差异。
• 「存在 n₀，当 n ≥ n₀」：意思是只看足够大的规模。小规模时低阶项可能占主导 （比如 n = 3 时 100n 比 n² 大得多），但渐近分析只关心大势。
• 「0 ≤ f(n) ≤ c·g(n)」：左边的不等式说明我们只讨论非负的运行时间， 右边的 ≤ 说明 c·g(n) 是 f(n) 的天花板。

所以大 O 的本质是：g(n) 是 f(n) 的一个渐进上界（asymptotic upper bound）， f 的增长不会快于 g。注意「上界」不等于「恰好等于」：

既然 3n²+2n+1 同时等于 O(n²)、O(n³)、O(2ⁿ)，那等号岂不是失效了？没错—— 大 O 里的「=」不是等价关系，而应当读作「属于」。 严格的写法是 f(n) ∈ O(g(n))，表示 f 这个函数落在 O(g) 这个函数集合里。 只是习惯上我们写等号，读作「是……阶的」。我们平时说「这个算法是 O(n²) 的」， 隐含的意思是「这是我们能给出的最紧的上界」。

1.7.4 顺带认识 Ω 与 Θ：下界与紧确界

大 O 只描述上界，那么「至少要花多少时间」呢？这就要用到 Ω；而当我们既能给出上界又能给出下界时， 就用 Θ 把两者合起来。

三者的关系一句话说清：Θ(g) = O(g) ∩ Ω(g)。 如果一个算法既满足 f = O(g) 又满足 f = Ω(g)，那么 f = Θ(g)。 例如 3n² + 2n + 1：它既是 O(n²) 又是 Ω(n²)，所以是 Θ(n²)——这才是关于它最准确的描述。

那为什么本课程（以及绝大多数工程讨论）几乎只用大 O？因为估计算法时我们最怕的是「最坏情况会有多糟」， 上界正是回答这个问题的；并且很多时候下界并不容易证明。 例如第 12 讲要讲的比较排序下界 Ω(n log n)，就是靠一棵决策树的叶子数才证出来的， 那是全课程里少见的高难度证明。

1.7.5 推导大 O 的三条法则

有了定义，实际计算时并不需要每次都去找 c 和 n₀。下面三条法则可以让你在几秒内写出答案， 它们全都可以由定义直接证明。

1.8 五道例题：手把手推导大 O

下面 5 道例题由浅入深，覆盖了考试和面试中 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;
}

变体思考：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 的通项，再让它满足退出条件：

变体思考：把 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)。

例 3　循环变量自乘（开方型）—— O(log log n)

// ex3_sqrt.cpp —— 循环变量以自身为倍数增长 / 自身开方：双对数级
#include <iostream>
#include <cmath>

int stepsSquare(int n) {
    int cnt = 0;
    for (int i = 2; i < n; i = i * i) ++cnt;   // i: 2, 4, 16, 256, 65536, ...
    return cnt;
}

int stepsSqrt(int n) {
    int cnt = 0;
    for (int i = n; i > 1; i = (int)std::sqrt((double)i)) ++cnt;  // i: n, √n, n^(1/4), ...
    return cnt;
}

int main() {
    std::cout << stepsSquare(1000000) << '\n';   // 4：2 → 4 → 16 → 256 → 65536
    std::cout << stepsSqrt(1000000) << '\n';     // 4：10^6 → 10^3 → 31 → 5 → 2
    return 0;
}

这类循环的规律是「每次把指数翻倍」，通项里会出现 2 的 2 的幂：

为什么它值得单独记一档？因为 O(log log n) 增长慢得惊人：n = 10⁶ 时才 4 次， n = 10⁹ 时才 5 次，n 取到宇宙原子总数（约 10⁸⁰）也不过 8 次。 埃拉托斯特尼筛法（埃氏筛）求 n 以内全部素数的复杂度是 O(n log log n)， 其中那个 log log n 正来自这种「标记倍数」的循环结构——第 13 讲会再见到它。

例 4　递归式 T(n) = 2T(n/2) + O(n) —— O(n log n)

这是分治法的典型形态：把问题一分为二（2 个规模 n/2 的子问题）， 再花线性时间把两半结果合起来。归并排序、快速排序的平均情况都是这个式子。

// ex4_merge_sort.cpp —— 归并排序：T(n) = 2T(n/2) + Θ(n) = O(n log n)
//
// 只用 4 个数，每次「分」「合」都打印出来（运行结果附在文件末尾），方便对照递归树。
// 读之前只需要记住一个约定：
//   区间写成 [l, r)，意思是「从下标 l 开始、到下标 r 之前为止」——左边算、右边不算。
//   好处是区间长度直接就是 r - l，不用到处写 +1 / -1，不容易错。
#include <iostream>
#include <vector>

std::vector<int> a = {5, 2, 9, 1};   // 要排序的数组（只有 4 个数，递归总共 2 层）
std::vector<int> buf(a.size());      // 合并时的临时缓冲区，大小和 a 一样（后面 1.11 讲空间复杂度会用到它）
int depth = 0;                       // 当前递归到第几层；只用来控制打印缩进，与算法无关

void pad() { for (int i = 0; i < depth; ++i) std::cout << "  "; }

/* 打印 a 的下标 [l, r) 这一段，元素之间用空格隔开（末尾不留多余空格） */
void printRange(int l, int r) {
    for (int t = l; t < r; ++t) {
        if (t > l) std::cout << " ";
        std::cout << a[t];
    }
}

/* 把区间 [l, r) 里的数排好序。
   [l, r) 的意思是「从下标 l 开始，到下标 r 之前为止」——左边算、右边不算。
   这样约定的好处：区间长度直接就是 r - l，不用到处写 +1 / -1，不容易错。 */
void mergeSort(int l, int r) {
    int len = r - l;                 // 这个区间里有几个数

    /* 【递归基】区间里只剩 0 个或 1 个数 —— 它自己就是有序的，直接返回。
       注意：这里「一次比较都不做」。只有 1 个数时，没有任何两个数需要比大小。
       （真正「比较一次」的是长度为 2 的那一层，见下面合的部分。） */
    if (len <= 1) return;

    /* 【分】从正中间切开：左半是 [l, m)，右半是 [m, r) */
    int m = l + len / 2;
    pad();
    std::cout << "分 [" << l << "," << r << ") → 左[" << l << "," << m
              << ") 右[" << m << "," << r << ")\n";

    /* 【治】两半各自排好序。写法就是「调用自己」，只是区间小了一半 */
    ++depth;                         // 进下一层，打印时多缩进两格
    mergeSort(l, m);
    mergeSort(m, r);
    --depth;                         // 回到本层

    /* 【合】此刻左右两半都「已经有序」了，把它们并成一个有序区间：
       i 指左半的第一个数、j 指右半的第一个数，每次挑小的那个搬进 buf。 */
    int i = l, j = m, k = l;
    while (i < m && j < r) {         // 两半都还有数：比一比，搬小的
        if (a[i] <= a[j]) buf[k++] = a[i++];
        else              buf[k++] = a[j++];
    }
    while (i < m) buf[k++] = a[i++];   // 右半搬完了，左半剩下的直接接上（不用再比）
    while (j < r) buf[k++] = a[j++];   // 左半搬完了，右半剩下的直接接上（不用再比）

    for (int t = l; t < r; ++t) a[t] = buf[t];   // 把排好的这一段搬回 a

    pad();
    std::cout << "合 [" << l << "," << r << ") → ";
    printRange(l, r);
    std::cout << "\n";
}

/* 对照递推式 T(n) = 2T(n/2) + cn，看上面代码的三个部分：
     「分」那一行          → 一次加法一次除法，常数时间 O(1)（递推式里忽略不计）
     两次 mergeSort 调用   → 2 × T(n/2)   ← 式子里的 2T(n/2) 说的就是它
     「合」那几行          → 每个元素都被搬进 buf 一次、搬回 a 一次，总次数与 n 成正比 Θ(n)
                            ← 式子里的 cn 说的就是它
   所以 T(n) = 2T(n/2) + cn。 */
int main() {
    std::cout << "原始数组：";
    printRange(0, (int)a.size());
    std::cout << "\n\n";

    mergeSort(0, (int)a.size());

    std::cout << "\n排序结果：";
    printRange(0, (int)a.size());
    std::cout << "\n";
    return 0;
}

/* ------- 运行结果（缩进就是递归树的层次，建议自己跑一遍对照） -------
原始数组：5 2 9 1

分 [0,4) → 左[0,2) 右[2,4)
  分 [0,2) → 左[0,1) 右[1,2)
  合 [0,2) → 2 5
  分 [2,4) → 左[2,3) 右[3,4)
  合 [2,4) → 1 9
合 [0,4) → 1 2 5 9

排序结果：1 2 5 9
   从输出能一眼看出两件事：
     ① 递归的顺序是「一路分到底，再一层层合上来」；
     ② 最底下的两次「合」都是把两个单独的数并起来 —— 那一次正好比较 1 次。
   ----------------------------------------------------------------- */

用递归树展开最直观：每一层的合并总代价都是 n，层数是对数级。

为什么它比 O(n²) 强这么多？因为每层只做 n 次合并，而层数只有 log₂n。 n = 10⁶ 时，n log n ≈ 2×10⁷，n² = 10¹²，相差 5 万倍。 第 12 讲会讲主定理（Master Theorem），用它可以一眼写出这类递推式的解， 不必每次画树。

例 5　递归式 T(n) = T(n/2) + O(1) —— O(log n)

这是「每次砍掉一半」的形态，二分查找是它的标准代表。 它比例 4 更妙的地方在于：每层只需常数时间，所以只剩层数一个因子。

// ex5_binary_search.cpp —— 二分查找：T(n) = T(n/2) + O(1) = O(log n)
#include <iostream>
#include <vector>

// 递归版：递推式 T(n) = T(n/2) + O(1)
int bsearchRec(const std::vector<int>& a, int l, int r, int key) {
    if (l > r) return -1;                              // 递归基：O(1)
    int m = l + (r - l) / 2;                           // O(1)，写成这样可防 l+r 溢出
    if (a[m] == key) return m;                         // O(1)
    if (a[m] < key) return bsearchRec(a, m + 1, r, key);   // 只走一边：T(n/2)
    return bsearchRec(a, l, m - 1, key);                   // 只走一边：T(n/2)
}

// 迭代版：循环次数 = 把 n 折半到 1 需要几步 = log2(n)
int bsearchIter(const std::vector<int>& a, int key) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == key) return m;
        if (a[m] < key) l = m + 1;
        else            r = m - 1;
    }
    return -1;
}

int main() {
    std::vector<int> a = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    std::cout << bsearchRec(a, 0, (int)a.size() - 1, 7) << '\n';   // 3
    std::cout << bsearchIter(a, 19) << '\n';                     // 9
    std::cout << bsearchIter(a, 8) << '\n';                      // -1（不存在）
    return 0;
}

注意一个前提：二分查找要求数据有序且支持随机访问。所以在链表上做二分查找是没有意义的 ——找到中点本身就要 O(n)，总复杂度反而退化成 O(n log n)。 这又是一个「存储结构决定算法能否成立」的例子。

1.8.1 五道例题速查表

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。分析前先做两条假设：

1. 表中元素互不相同；
2. 每个元素被查找的概率相等，即 p_i = 1/n（等概率假设）。

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

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

三种情况放在一起看：

如果概率不相等呢？那就老老实实按 p_i 加权。例如已知 「查第 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)，且常数因子是所有内排序中最小的之一。

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

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

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

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

1.10 常见复杂度增长对比

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

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

• n ≤ 10⁶ 时，O(n) 与 O(n log n) 都可以放心用；
• n > 10⁴ 时，O(n²) 基本告别，必须换成 O(n log n) 或 O(n)；
• n > 20 时，O(2ⁿ) 就只能靠剪枝、记忆化或彻底换思路（这正对应第 13 讲的动态规划）。

// 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) 指的是辅助空间（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(n) 缓冲）、计数 / 基数排序（O(n + k) 桶）；
• 快速排序是个特例：划分过程本身是原地的（只用几个下标变量）， 但递归调用需要栈空间 O(log n)（平均）～ O(n)（最坏），所以严格来说它不是严格的原地算法， 准确说法是「原地划分 + O(log n) 栈空间」。

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 S(n) 的常见形态

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

1.12 专业术语体系：43 条中英对照

数据结构是一门「术语密度」很高的课：同一件事在不同教材里可能叫「物理结构」也叫「存储结构」， 同一类结点在链表里叫 node、在树里叫 vertex。下面这张表把全课程最常用的 43 个术语一次性打好底， 后面 14 讲遇到时可以直接回来查。建议打印出来贴在书桌前，每学一章划掉几个。

数据
data

信息的载体，是能输入到计算机中并被程序识别和处理的符号集合。可以是数值、字符、图像、声音。

数据元素
data element

数据的基本单位，在程序中作为一个整体处理；在链表 / 树 / 图中也称作结点（node），在数据库中称作记录（record）。

数据项
data item

构成数据元素的、不可再分割的最小单位，也叫字段（field）。一个数据元素由若干数据项组成。

数据对象
data object

性质相同的数据元素的集合，是数据的一个子集。强调「有哪些成员」，不强调成员间的关系。

数据结构
data structure

相互之间存在一种或多种特定关系的数据元素的集合。= 逻辑结构 + 存储结构 + 数据的运算。

逻辑结构
logical structure

数据元素之间抽象的关系，分集合、线性、树形、图形四类。与计算机、语言、内存无关。

存储结构 / 物理结构
storage / physical structure

逻辑结构在计算机存储器中的表示，包括元素本身的表示与元素之间关系的表示。

顺序存储
sequential storage

用物理位置相邻表示逻辑相邻，关系不占额外空间，支持随机访问 O(1)，插入删除需搬移元素。

链式存储
linked storage

用指针显式指出后继（或前驱）的地址，物理位置任意，按位查找 O(n)，已知位置时插删 O(1)。

索引存储
indexed storage

在数据表之外另建一张「关键字 → 地址」的索引表，先查索引再取记录，以空间和维护开销换检索速度。

散列存储
hash storage

由散列函数 h(key) 直接算出存储地址，平均查找 O(1)，但失去顺序性、需处理冲突。

抽象数据类型
ADT, Abstract Data Type

一个数学模型以及定义在该模型上的一组操作，只规定「做什么」不规定「怎么做」，由数据对象、数据关系、基本操作三部分组成。

封装
encapsulation

把数据表示与操作实现隐藏在模块内部，只暴露接口。ADT 在 C++ 中常用 class 的 public / private 实现，用一组自由函数表达同一个 ADT 也可以。

算法
algorithm

对特定问题求解步骤的描述，是指令的有限序列；具备有穷性、确定性、可行性、输入、输出五大特性。

有穷性
finiteness

算法必须在执行有穷步后终止，且每一步都在有穷时间内完成。这是算法区别于程序的关键。

确定性
definiteness

每条指令含义确切、无二义性；相同输入在任何时刻都产生相同的输出。

可行性
effectiveness

算法中的每一步都能机械地执行，并且能在有限时间内完成（微观层面的「做得到」）。

输入 / 输出
input / output

算法有 0 个或多个输入，但必须有 1 个或多个输出；没有输出的算法没有意义。

语句频度
statement frequency

一条语句在算法中被重复执行的次数。所有语句频度之和记作 T(n)，是问题规模 n 的函数。

问题规模
problem size

刻画输入量大小的量，通常记作 n。数组是元素个数，图是顶点数 V 与边数 E，串是串长。

时间复杂度
time complexity

算法执行时间随问题规模增长的趋势，用 T(n) 的渐近阶表示，是事前分析估算的核心指标。

空间复杂度
space complexity

算法运行过程中临时占用的辅助空间随规模增长的趋势，记作 S(n)，不含输入数据本身。

渐进记号
asymptotic notation

描述函数在 n → ∞ 时增长量级的记号体系，包括 O（上界）、Ω（下界）、Θ（紧确界）、o、ω。

大 O 记号
big-O notation

存在正常数 c 与 n₀，使 n ≥ n₀ 时 0 ≤ f(n) ≤ c·g(n)，记 f(n) = O(g(n))。表示渐进上界，等号应读作「属于」。

上界 / 下界 / 紧确界
upper / lower / tight bound

O 给天花板，Ω 给地板，Θ 把两者夹住（Θ = O ∩ Ω）。上界可以很松，工程上习惯用最紧的那个。

最好 / 最坏 / 平均情况
best / worst / average case

同一算法在不同输入形态下的复杂度。默认讨论的是最坏情况，平均情况必须先声明概率假设。

平均查找长度
ASL, Average Search Length

查找过程中关键字比较次数的期望值，ASL = Σ pᵢ·cᵢ。顺序查找等概率下为 (n+1)/2。

均摊分析
amortized analysis

把偶尔出现的高代价操作平摊到一连串操作上。动态数组扩容的单次代价是 O(n)，但均摊到每次插入是 O(1)。

原地算法
in-place algorithm

只用 O(1) 辅助空间的算法。注意递归版即使只改几个变量，也可能因栈深而失去 O(1) 空间。

辅助空间
auxiliary space

除输入数据与程序代码之外，算法额外占用的存储空间，才是空间复杂度真正统计的对象。

递归 / 递归基 / 递归深度
recursion / base case / depth

函数直接或间接调用自身；递归基是终止条件；递归深度决定栈空间大小。

栈帧
stack frame

每次函数调用在运行时栈上压入的记录，保存参数、局部变量与返回地址。递归的空间代价主要来自它。

递归树
recursion tree

把递归展开成树形结构来求递推式解的方法：每层代价相加，层数决定因子（如归并排序每层 n、共 log n 层）。

分治法
divide and conquer

把问题分成若干规模更小的同类子问题，分别求解后合并。归并排序、二分查找、快速排序都是它的实例。

主定理
master theorem

直接求解 T(n) = aT(n/b) + f(n) 这类递推式的公式，第 13 讲会给出三种情况的判定方法。

时空权衡
time-space tradeoff

用更多内存换更快速度（哈希表、记忆化搜索），或用更多计算省内存（滚动数组、重新计算）。

随机访问 / 顺序访问
random / sequential access

随机访问指任意位置的存取代价相同（数组，O(1)）；顺序访问必须从头逐个走（链表，O(n)）。

存储密度
storage density

数据本身占用的空间 / 结点占用的总空间。顺序存储密度为 1，链式存储因指针而小于 1。

前驱 / 后继
predecessor / successor

线性结构中某元素的前一个 / 后一个元素。树中对应「父结点 / 孩子结点」，图中对应「邻接点」。

头结点 / 头指针 / 哨兵
head node / head pointer / sentinel

头指针指向链表的第一个结点；头结点是带头结点链表中附加在首元素之前的虚结点，可统一空表与非空表的操作；哨兵是嵌在边界、免去越界判断的特殊值。

稳定性
stability

排序后关键字相同的元素相对次序是否保持不变。稳定：冒泡、插入、归并、基数；不稳定：快排、选择、堆、希尔。

稠密图 / 稀疏图
dense / sparse graph

边数接近 V² 称稠密图（用邻接矩阵），边数远小于 V² 称稀疏图（用邻接表，空间 O(V+E)）。

指针 / 游标
pointer / cursor

指针存放地址；游标是用数组下标模拟指针的技术，用于静态链表等不能使用指针的场合。

1.13 学习建议

1.13.1 结构决定算法：先选结构，再谈算法

初学者常见的路径是「拿到题目直接想算法」，结果写完才发现：数据量 10⁵，而自己的做法是 O(n²)。 高手的路径恰好相反：先看数据的规模与操作的类型，据此确定数据结构；结构定了，算法几乎是自然长出来的。

举个例子：题目要求「维护一个集合，支持插入、删除、查询最小值」。 如果你用无序数组：查询最小值 O(n)；用有序数组：插入 O(n)； 用二叉堆：三种操作全是 O(log n)；用哈希表：查询最小值退化成 O(n)（因为哈希表不维护顺序）。 算法没变，变的是结构；结构一变，复杂度就变了。 再比如「频繁查询区间和」用前缀和（O(1) 查询）、「频繁区间修改 + 区间查询」用树状数组或线段树， 也都是结构决定算法的典型。

所以每学一个新结构，请固定问自己三个问题： ① 它支持哪些操作？② 每个操作的复杂度是多少？③ 什么样的场景该用它、什么样的场景千万别用？ 能答出这三问，这个结构才算真的学会了。

1.13.2 画图胜过背书

数据结构是「看得见」的学科。指针怎么指、树怎么长、栈怎么压、图的边怎么连， 全都可以画出来。我强烈建议你准备一个方格本，每学一个结构就画三张图：

1. 结构图：元素在内存里长什么样，指针指向谁，地址是怎么排的；
2. 操作图：执行一次插入 / 删除 / 旋转时，哪几条指针被改动，改动前后各是什么样（画两遍）；
3. 边界图：空结构、只有一个元素、在头部操作、在尾部操作时，图会变成什么样。 这一张最容易被忽略，也最容易在考场上丢分。

背定义只能应付名词解释，画图才能应付代码题。当你闭着眼睛能在脑海里「看见」指针的移动时， 写代码就只是把脑海里的图翻译成 C++ 而已。

1.13.3 动手实现比看代码重要十倍

看别人写的链表代码，你会觉得「不过如此」；等自己动手写，才会发现： 头指针什么时候要改、删除时怎么保证不断链、释放内存的顺序为什么不能颠倒—— 这些细节只有踩过坑才会记住。建议的学习闭环是：

• 第一遍：合上讲义，凭记忆把结构定义与基本操作写出来，能编译通过；
• 第二遍：自己写测试用例，特别是空表、单元素、首尾位置这几个边界，并打印中间状态检查；
• 第三遍：对照讲义的标准实现，找出差异，问自己「我的写法错在哪 / 会不会更差」；
• 第四遍：用 -Wall -Wextra 编译，用 valgrind 或 -fsanitize=address 检查内存问题（指针错误是数据结构作业的头号杀手）。

另外请养成先写测试再写实现的习惯。数据结构的代码往往不长，但指针操作极易出错； 有测试兜底，你才敢放心重构。

1.14 本章小结

1.15 易错点与考点

1.16 工程视角：大 O 之外，真实机器还在乎什么

大 O 有个刻意的取舍：常数因子与低阶项统统丢掉，只留「随 n 增长的趋势」。 于是就有了那个危险的错觉——两个都写成 O(n) 的算法，在真实机器上可以差 5 倍、10 倍甚至更多。 本节补上三把尺子：内存层次、缓存局部性与数据规模分布。

1.16.1 内存层次：主存比 L1 慢约 100 倍，磁盘又比主存慢约 10 万倍

CPU 做一次整数加法只要 0.3 ns，从主存取一个数却要 80～120 ns——一条加法的时间够执行三百条。 硬件把存储做成金字塔：越小越快越贵，越大越慢越便宜，每层都缓存下一层的副本。 必须记住的数量级是：L1 约 1 ns，L2 约 4 ns，L3 约 20 ns，主存约 100 ns，SSD 约 100 μs， 机械硬盘一次寻道约 10 ms。把一次 L1 命中当作 1 秒，一次主存访问就是 1 分 40 秒。 大 O 里这些都记作「一次访问」，代价却相差七个数量级。

CPU 几十年涨了上千倍，DRAM 延迟只从约 60 ns 挪到约 80 ns：1980 年代一次主存访问约等于 一条指令的时间，今天等于几百条——这条鸿沟就是内存墙（memory wall）。 它带来本节的中心命题：「执行了多少条指令」往往不是瓶颈，「访问内存的模式」才是。

1.16.2 缓存行与局部性：一次搬 64 字节，顺序与跳跃实测差 5 倍以上

CPU 与内存之间的搬运单位不是单个变量，而是缓存行（cache line）：x86-64 上一次 64 字节。 一个 int 只占 4 字节，所以读 a[0] 时硬件会顺手把 a[15] 一并搬进 L1—— 这就是空间局部性；再加上时间局部性（刚用过的马上还会用），缓存才得以生效。 反过来，跳跃访问时一条缓存行只用到 4 字节，命中率跌到 1/16。 下面这段代码把两种走法放在同一份数据上对比，变化的只是两层循环的次序。

// cache_locality.cpp —— 缓存局部性与常数因子实测
// 编译：g++ -std=c++17 -O2 cache_locality.cpp -o cache_locality
// 实验一：1024x1024 数组按行 / 按列遍历求和（加法次数相同）
// 实验二：小数组上插入排序 vs 手写快排（大 O 更差的反而更快）
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

const int N = 1024;          // 4 MB，超过常见 L2
int a[N][N];                 // 全局数组，不占栈
int pool[200000];
int buf[N];                  // 每次从这里拷 n 个数
long long g_check = 0;       // 防止被优化掉
unsigned g_seed = 20260916u;

int nextRand() {
    g_seed = g_seed * 1103515245u + 12345u;
    return (int)((g_seed >> 16) & 0x7fff);
}

/* ---------- 实验一：行优先 vs 列优先 ---------- */

// 行优先：一条 cache line（64 字节）喂 16 个 int
long long sumByRow() {
    long long s = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            s += a[i][j];
    return s;
}

// 列优先：相邻访问相隔 4096 字节 = 64 条 cache line
long long sumByCol() {
    long long s = 0;
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            s += a[i][j];
    return s;
}

/* ---------- 实验二：插入排序 vs 快排 ---------- */

void insertionSort(int* v, int n) {
    for (int i = 1; i < n; ++i) {
        int key = v[i], j = i - 1;
        while (j >= 0 && v[j] > key) { v[j + 1] = v[j]; --j; }   // 连续回扫
        v[j + 1] = key;
    }
}

// 三数取中 + Hoare 划分，不做小区间优化
void quickSort(int* v, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    if (v[mid] < v[lo]) swap(v[mid], v[lo]);
    if (v[hi]  < v[lo]) swap(v[hi],  v[lo]);
    if (v[hi]  < v[mid]) swap(v[hi], v[mid]);
    int pivot = v[mid];
    int i = lo, j = hi;
    while (i <= j) {
        while (v[i] < pivot) ++i;
        while (v[j] > pivot) --j;
        if (i <= j) { swap(v[i], v[j]); ++i; --j; }
    }
    quickSort(v, lo, j);
    quickSort(v, i, hi);
}

double benchInsert(int n, int repeat) {
    long long guard = 0;
    auto t0 = steady_clock::now();
    for (int r = 0; r < repeat; ++r) {
        memcpy(buf, pool + (r * n) % 100000, n * sizeof(int));
        insertionSort(buf, n);
        guard += buf[0] + buf[n - 1];
    }
    auto t1 = steady_clock::now();
    g_check += guard;
    return duration<double, micro>(t1 - t0).count() / repeat;
}

double benchQuick(int n, int repeat) {
    long long guard = 0;
    auto t0 = steady_clock::now();
    for (int r = 0; r < repeat; ++r) {
        memcpy(buf, pool + (r * n) % 100000, n * sizeof(int));
        quickSort(buf, 0, n - 1);
        guard += buf[0] + buf[n - 1];
    }
    auto t1 = steady_clock::now();
    g_check += guard;
    return duration<double, micro>(t1 - t0).count() / repeat;
}

int main() {
    for (int i = 0; i < 200000; ++i) pool[i] = nextRand();
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            a[i][j] = nextRand() & 0x7ff;

    sumByRow();  sumByCol();                  // 预热

    long long sRow = 0, sCol = 0;
    double rowMs = 1e9, colMs = 1e9;
    for (int r = 0; r < 3; ++r) {             // 各测 3 遍取最快
        auto t0 = steady_clock::now();
        sRow = sumByRow();
        auto t1 = steady_clock::now();
        sCol = sumByCol();
        auto t2 = steady_clock::now();
        rowMs = min(rowMs, duration<double, milli>(t1 - t0).count());
        colMs = min(colMs, duration<double, milli>(t2 - t1).count());
    }

    printf("=== 实验一：1024x1024 int 求和，-O2 ===\n");
    printf("行优先 sum = %lld，最快 %.3f ms\n", sRow, rowMs);
    printf("列优先 sum = %lld，最快 %.3f ms\n", sCol, colMs);
    printf("列优先 / 行优先 = %.2f 倍\n\n", colMs / rowMs);

    printf("=== 实验二：插入排序 vs 手写快排 ===\n");
    int sizes[3] = {8, 16, 32};
    for (int k = 0; k < 3; ++k) {
        int n = sizes[k];
        int repeat = 200000 / n;              // 规模越大重复越少
        double ti = benchInsert(n, repeat);
        double tq = benchQuick(n, repeat);
        printf("n = %2d：插入 %7.3f us，快排 %7.3f us，倍数 %.2f\n",
               n, ti, tq, tq / ti);
    }
    printf("校验和 = %lld\n", g_check);
    return 0;
}

在作者机器上（g++ 15.2，-O2，各测三遍取最快），实验一输出：

加法次数一模一样，只把 i 和 j 换个位置就差 5 倍多 （换台机器重复跑会在 4～6 倍之间波动，但差距不会消失）：行优先时 16 次连续加法 只付一次「搬缓存行」的钱，预取器还能顺着固定步长提前搬后面几条；列优先时每读一个 int 就新搬 64 字节，其中 60 字节当场作废。这正是第 06 讲二维数组「行优先存储」的性能后果。

工程上这条规律被反复利用：矩阵乘法分块（blocking）让子矩阵整块装进 L1，数据库分成行存与列存。 陷阱是：局部性优化依赖具体机器——L1 大小、有无向量指令、缓存行是 64 还是 128 字节， 都会改变最优分块大小，必须实测；而拆循环、重排数组会让代码变难读。

1.16.3 大 O 相同 ≠ 实际一样快：常数因子里装着什么

局部性只是常数因子的一个来源，第二个实验给出了另一个： n = 8 时插入排序比手写快排快约 1.4 倍，n = 16 与 n = 32 时快 1.8～2 倍， 尽管插入排序是 O(n²)、快排是 O(n log n)。原因全在被大 O 丢掉的那些项里：

• 调用开销：快排每层都要压栈、取中位数、跑一遍划分，n = 16 时递归树上有 15 次调用； 插入排序只有一层循环。
• 分支预测：插入排序的内层 while 在小数组上很少真正进入循环体，预测器几乎不猜错； 快排每次比较都要分支且方向难测，一次预测失败就是十几个周期。
• 访存局部性：插入排序只在一段连续区间里回扫，几乎全命中 L1；快排的划分两端交换，访问是跳跃的。

这是标准库真实采用的工程决定。第 12 讲会讲到的内省排序（introsort）就是： 整体用快排，区间长度降到 16 以下就切换成插入排序，递归层数超过 2·log₂n 再换堆排序兜底。 std::sort、Java 的 Arrays.sort、Python 的 Timsort 里都埋着同一个阈值： 第 11 讲讲插入排序时它是最慢的 O(n²)，到了工程实现里却成了高性能排序的最后一块拼图。

1.16.4 O(n²) 在小 n 上真的会赢：要看规模分布，不能只看阶

插入排序的代价约为 c₁·n²/4，归并排序约为 c₂·n·log₂n，交叉点落在 n ≈ 32～64： n 小于约 32 时，O(n²) 的插入排序比 O(n log n) 的归并排序还快。 上面 n = 32 那一行的 1.8 倍就是证据。

• 若一次调用里 95% 的时间都花在长度不超过 8 的小数组上， 那么优化大数组算法的收益还不如给小区间换个更笨但更快的小算法；
• 现实数据天然是「大量小集合」：哈希表每桶平均只有 1～2 个元素，B+ 树结点内只有几十个键， 分治递归到最后几层也全是小数组；
• 反过来，n 稳定在 10⁶ 以上时，常数因子再优化 2 倍也是杯水车薪。

第 10 讲讲哈希冲突时「桶内用链表顺序查找」之所以是主流，正因为绝大多数桶是空的或只装一个元素； 第 07 讲的 B+ 树在结点内部也用二分查找，而不是再挂一棵子树。陷阱在于：n 会长大—— 今天每桶 1 个元素，明天哈希函数一退化就可能是 100 个。阈值要来自实测，最坏情况仍要可控， 所以 std::sort 切到插入排序之后还要留堆排序兜底。

1.16.5 空间复杂度的工程代价：栈会溢出，工作集会掉出缓存

第一条硬边界是递归栈。递归深度决定同时存活的栈帧数量，而线程栈有限：Linux 默认 8 MB， Windows 默认 1 MB，嵌入式上常常只有几 KB。一个栈帧按 48～64 字节算，8 MB 约撑得住 10 万～15 万层； 可一旦递归深度是 O(n)，n = 10⁶ 就会当场栈溢出（stack overflow）。第 07 讲讲二叉树遍历时 那种「递归多优雅」的印象，一旦树退化成链，就必须改写成显式维护栈的迭代版本—— 第 03 讲的数据结构在这里从教学道具变成救命工具。

第二条是空间换时间的性价比，前提是「多出来的那块内存真的装得下，并且用得上」：

• 哈希表用 O(n) 额外空间把查找从 O(n) 降到平均 O(1)，是最经典的划算买卖；
• 动态规划用滚动数组把空间从 O(nm) 压到 O(m)，代价是不能再回溯出具体方案；
• 嵌入式设备只有几十 KB RAM，此时「原地（in-place）」不是编码风格，而是唯一可行方案； 第 12 讲的外部排序存在，也是因为数据量超过内存，只能借磁盘做多路归并；
• 最容易忽略的一层：工作集大小决定数据住在内存层次的哪一层。数据从 512 KB 涨到 8 MB， 同一算法就可能从「全在 L2」掉到「每次访问主存」。

陷阱是：递归改迭代并不总是划算，显式维护栈会带来新的出错点。

1.16.6 一张表：工程选型要同时看的五个维度

请注意：表里任何单独一列都不足以做决定——大 O 最漂亮的一行可能缓存最不友好， 最快的一版可能多占一倍内存；「大 O 分析」只回答一个问题——规模再涨十倍，它会不会崩。

这一节不直接考计算题，却是理解后面十几讲「为什么非要这么实现」的钥匙： 第 02 讲顺序表与链表的取舍、第 06 讲的数组存储顺序、第 10 讲的哈希桶设计、 第 11 讲与第 12 讲的排序实现，背后都是同一件事——让数据待在该待的那一层内存里。

1.17 概念自测（8 题）

先自己在本子上写答案，再展开对照。答案里有推导过程的，请重点看推导思路而不是结论。

1. 数据元素与数据项有什么区别？请各举一例。
   查看参考答案

   数据元素是数据的基本单位，在程序中作为一个整体被处理； 数据项是构成数据元素的、不可再分割的最小单位。 关系是「数据元素由若干数据项组成」。

   例：在学生成绩表中，「张三、学号 1001、计科 1 班、高数 92」这一整条记录是一个数据元素； 其中的「学号 1001」「姓名张三」「高数 92」分别是数据项。 注意：当数据元素只含一个数据项时（如一个整数数组元素 a[3] = 7），两者在形态上重合，但层级关系不变。

2. 数据结构的三要素是什么？为什么说「逻辑结构独立于存储结构」？
   查看参考答案

   三要素：逻辑结构 + 存储结构（物理结构） + 数据的运算。

   「独立」的理由：逻辑结构描述的是元素之间抽象的数学关系（一对一、一对多、多对多）， 定义里根本不涉及「地址」「字节」「内存」这些概念，因此它与计算机、编程语言、机器字长都无关。 同一个线性表，既可以用顺序存储，也可以用链式存储、静态链表甚至散列存储来实现， 逻辑语义完全一样。

   这个独立性的直接价值有两个：一是让我们能脱离具体机器分析算法（这正是大 O 记号成立的前提）； 二是让「换实现不改接口」成为可能（ADT 的价值）。

3. 判断并说明理由：顺序存储一定比链式存储快。
   查看参考答案

   错误。两者各有优势，取决于具体的运算：

   • 按位查找第 i 个元素：顺序表 O(1)（地址可算），链表 O(n)（必须顺着走）——顺序表快；
   • 已知位置插入 / 删除：链表 O(1)（只改指针），顺序表 O(n)（要搬移后继元素）——链表快；
   • 空间：顺序表存储密度为 1 但需预分配连续空间、可能扩容搬移；链表密度小于 1 但按需分配。 当元素很大而表很稀疏时，链表反而更省内存。

   正确说法是：读多写少的场景选顺序表，频繁在中间插删且已持有位置信息的场景选链表。

4. 求下列代码的时间复杂度：for (int i = 1; i <= n; i *= 3) for (int j = 1; j <= i; j += 2) ++cnt;
   查看参考答案

   外层循环：i 取值为 1, 3, 9, 27, …，即 3^k，退出条件是 3^k > n， 所以外层执行次数为 ⌊log₃n⌋ + 1。

   内层循环：当外层为 i 时，j 从 1 开始每次加 2，执行约 i/2 次。

   总次数 = Σ_k=0..log₃n (3^k/2) = (1/2)·(3^log₃n+1 − 1)/2 = (1/2)·(3n − 1)/2 ≈ 0.75n = O(n)。

   结论：O(n)。这是一个很有迷惑性的题——外层看着像对数，但内层次数与 i 成正比， 而 i 是指数增长的，指数求和的结果由最后一项主导，最终是 O(n)。

5. 顺序查找中，若每个元素被查找的概率相等，平均查找长度 ASL 是多少？请写出推导。
   查看参考答案

   设表长为 n，查找第 i 个元素需要比较 i 次；等概率时 p_i = 1/n。则

   ASL = Σ_i=1..n p_i·c_i = (1/n)·Σ_i=1..n i = (1/n)·n(n+1)/2 = (n+1)/2

   所以平均比较次数约为 n/2，平均时间复杂度为 O(n)。 注意区分：最好情况是 1 次（O(1)），最坏情况是 n 次（O(n)，查找失败时也是 n 次）。

   延伸：若各元素被查概率不等，则 ASL = Σ p_i·c_i 需按实际分布计算。 工程上的优化手段就是把高频元素前移（自适应线性表）。

6. 递归式 T(n) = 2T(n/2) + O(n) 的解是什么？为什么归并排序的递归树每层代价都是 n？
   查看参考答案

   T(n) = O(n log n)。

   递归树第 k 层有 2^k 个子问题，每个规模为 n/2^k， 而每个子问题的合并代价与它的规模成正比，所以第 k 层的总代价 = 2^k × c·(n/2^k) = c·n， 与层数无关，恒为 n。这说明「分得越细，问题越多，但每个问题越小，总量恰好抵消」。

   树高：n/2^k = 1 时触底，得 k = log₂n。 但要数清楚：归并只发生在 k = 0 … log₂n − 1 这 log₂n 层（子问题规模 n、n/2、…、2）； 触底那一层的子问题规模是 1，mergeSort 直接 return，不做归并、不产生代价 （比较 0 次、搬移 0 次）。所以「每层代价都是 n」这句话只对那 log₂n 层成立。 因此 T(n) = cn·log₂n + O(n) = O(n log n)。

   补充一句：这里没有「+ 1」这一层，是因为规模 1 的递归基什么都不用做； 对比二分查找 T(n) = T(n/2) + c：它的 T(1) = c 本身就要做 1 次比较， 那一层躲不掉，所以才写成 c(log₂n + 1)。

   对照记忆：如果合并代价降为 O(1)（如二分查找只走一边），就退化成 T(n) = T(n/2) + O(1) = O(log n)。

7. 递归求阶乘 fact(n) = n * fact(n-1) 的空间复杂度是多少？为什么不是 O(1)？
   查看参考答案

   S(n) = O(n)。

   每进入一层递归，系统就在运行时栈上压入一个栈帧（保存参数 n、局部变量与返回地址）。 在 fact(1) 触底之前，n 个栈帧同时存在，直到开始逐层返回才依次弹出。 因此最大栈深度为 n，辅助空间为 O(n)。

   对比：同样功能的迭代版本只用 r、i 两个变量，S(n) = O(1)。 这也解释了为什么 n 很大时递归会栈溢出（Stack Overflow）——工程代码在深度不可控时优先写迭代。

8. 大 O 是上界还是下界？3n² + 2n + 1 = O(n³) 成立吗？既然成立，为什么我们通常写 O(n²)？
   查看参考答案

   大 O 表示渐进上界：存在正常数 c 与 n₀，使 n ≥ n₀ 时 0 ≤ f(n) ≤ c·g(n)。

   O(n³) 成立。取 c = 1、n₀ = 6：当 n ≥ 6 时有 3n² + 2n + 1 ≤ n³。 所以定义上没有问题——上界可以很松。

   之所以通常写 O(n²)，是因为我们要的是最紧的上界：它携带的信息量最大。 写成 O(n³) 虽然不错，但会误导读者以为算法在 n = 10⁶ 时要跑 10¹⁸ 次。 另外注意，大 O 里的等号不是等价关系而是「属于」（f ∈ O(g)）， 否则 3n²+2n+1 = O(n³) 与 n³ ≠ 3n²+2n+1 会构成矛盾。