Week 2 和 Week 3 是 CS50 的第一次「爬坡」。Week 2 把编译流程从黑箱变成白箱，引入数组和字符串，终结了「CS50 的 string 是魔法」的幻觉。Week 3 则是算法与复杂度的全面展开——Malan 会把学生叫上讲台，用真人演示排序，用横轴和纵轴画出算法效率的视觉直觉。这两周的内容叠加在一起，构成一个分水岭：在此之前你在学「怎么写」，在此之后你开始学「怎么想」。
上一篇：Week 0 & 1 · 下一篇：Week 4 & 5
| 关键词 | 一句话说明 |
|---|---|
| 预处理（Preprocessing） | 编译第一步——把 #include 替换成对应头文件的全文，把 #define 宏展开 |
| 汇编（Assembly） | 比 C 低一级、比机器码高一级的中间语言——人类能勉强读懂的最后一级 |
| 链接（Linking） | 编译最后一步——把你编译好的目标文件和库文件缝在一起，生成可执行文件 |
| debug50 | CS50 的图形化调试器——在代码里设断点、逐行执行、实时查看变量值。命令行版就是 GDB |
| ⭐ 数组越界 | C 不会阻止你读 array[100]（哪怕数组只有 10 个元素）——它会读相邻内存的垃圾值，或者直接让你的程序崩溃 |
| 字符串 = char 数组 | Week 4 伏笔至此揭晓——string 就是 char *，一个指向字符数组第一个元素的指针。字符串末尾有一个隐藏的 '\0'（空字符）标记结束 |
| argc / argv | 命令行参数——argc = 参数个数，argv = 参数数组（字符串数组） |
| 退出码（Exit Status） | return 0 表示成功，return 1（或任何非零值）表示出错。命令行里用 echo $? 查看上一条命令的退出码 |
| 凯撒密码 | 最简单的加密算法——把每个字母向后移动固定位数。A→D, B→E（移动 3 位）。Week 2 的 Problem Set |
| ⭐ 大 O 记号（Big O） | 算法在最坏情况下的运行时间增长趋势——O(n²) 意味着数据量翻倍，时间翻四倍 |
| Ω（Omega）记号 | 算法在最好情况下的运行时间——冒泡排序最好 Ω(n)（数据已排好），最坏 O(n²) |
| 线性搜索 | 从头到尾一个一个找。O(n)。最简单也最慢 |
| 冒泡排序 | 相邻两两比较，大的往后「冒」。O(n²)。教学用，实战基本没人用 |
| 选择排序 | 每轮挑出最小的放在最前面。O(n²)。比冒泡少一些交换次数，但比较次数一样多 |
| 归并排序 | 分治法的经典——把数组不断对半切，切到只剩 1 个元素，再两两合并。O(n log n)。效率质变 |
| ⭐ 递归（Recursion） | 函数调用自身。必须有一个「基准条件」来停止，否则无限递归 → 栈溢出（Segmentation Fault） |
| 结构体（struct） | 把多个不同类型的变量打包成一个新类型。比如 struct person { string name; int age; }; |
| 宏 / #define | 预处理器功能——不是变量，是文本替换。带参数的宏必须给每个参数加括号，否则灾难性展开 |
| 魔术数字（Magic Number） | 代码里孤立的裸数字（如 for (i=0; i<3; i++) 里的 3）。用 #define 或 const 替换 |
| 静态链接 vs 动态链接 | 库代码嵌入你的程序（静态）还是运行时共享（动态）。动态是默认——安全补丁不需要重编译你的程序 |
| 安全字符串函数 | strncpy / strncat / fgets——带上 n 的版本限制拷贝长度，防止缓冲区溢出 |
| 莫里斯蠕虫 | 1988 年利用 gets() 缓冲区溢出感染互联网 10% 的电脑。史上第一个重大网络安全事件。肇事者后来成了 MIT 教授 |
| Θ（Theta）记号 | 当最好情况和最坏情况相同时的紧界记号——如归并排序 Θ(n log n) |
| 调用栈（Call Stack） | 函数调用时压栈、返回时弹栈的内存区域。递归过深 → 栈溢出。Week 4 内存布局的核心概念 |
| 快速排序（Quick Sort） | O(n log n) 排序的另一个支柱——选 pivot 分左右，原地排序。平均比归并快，最坏 O(n²) |
Week 1 结束时，你已经能用 C 写猜数字游戏——但有一个神秘的词汇挥之不去：编译。你只知道「make 把我的代码变成程序」，但不知道里面发生了什么。Week 2 前半段，Malan 把编译的黑箱撬开给你看。后半段，他引入数组——从单一变量到成排数据，编程的尺度第一次真正放大。而当他揭穿 string 就是 char 数组时，Week 1 埋下的伏笔兑现了。
Malan 在第 1 周用 make hello 一笔带过。第 2 周他把整个过程拆成四步，每一步在终端手动执行一遍：
| 步骤 | 命令 | 输入 → 输出 | 干什么 |
|---|---|---|---|
| ① 预处理 | clang -E hello.c | .c → 预处理后的文本 | 把头文件（如 stdio.h）的全文复制粘贴进你的代码。处理 #define 宏替换。Malan 跑完这步后把输出打到屏幕上——原本 5 行的 hello.c 变成了几百行。 |
| ② 编译 | clang -S hello.c | .c → .s（汇编） | 把 C 翻译成汇编语言——人类能勉强读懂的、最接近机器码的一层。你会看到 movl、call、ret 这些指令。 |
| ③ 汇编 | clang -c hello.c | .c → .o（目标文件） | 把汇编转成纯 0 和 1 的机器码。但此时还不能运行——因为引用的 printf 还没有接上。 |
| ④ 链接 | clang hello.o -o hello | .o → 可执行文件 | 把你的 hello.o 和标准库中的 printf 机器码「缝」在一起，生成最终的 hello 可执行文件。 |
Malan 做了一个漂亮的类比：「预处理就像做菜前把食材从冰箱拿出来放在台面上。编译是把食材切好。汇编是下锅炒。链接是装盘上桌。」每一步的输出都可以单独保存和查看——这不是什么神秘魔法，只是一条流水线。
Malan 演示了另一个预处理器的核心功能——宏替换。在 C 中，#define 告诉预处理器：看到 A 就替换成 B：
#define PI 3.14159
#define COURSE "CS50"
int main(void)
{
printf("欢迎来到 %s\n", COURSE); // 预处理器把 COURSE 替换成 "CS50"
printf("圆周率约等于 %f\n", PI); // PI 替换成 3.14159
}
预处理之后，编译器收到的代码里根本没有 PI 和 COURSE 这两个词——它们已经被替换成字面量了。这和变量完全不同——宏不占内存、没有类型、不参与编译。它只是「查找替换」。
Malan 还演示了带参数的宏：
#define SQUARE(x) (x * x) // 使用 int area = SQUARE(5); // → 5 * 5 = 25
然后他写了一个陷阱——不加括号会怎样：
#define BAD_SQUARE(x) x * x // 注意：没有括号！ int result = BAD_SQUARE(1 + 2); // 展开后：1 + 2 * 1 + 2 = 1 + 2 + 2 = 5 // 你期望的：3 * 3 = 9 ← 错了！
宏的黄金法则：给每个参数和整个表达式都加括号。
#define SQUARE(x) ((x) * (x))。多一对括号不会有人受伤，少一对可能让你 debug 到凌晨三点。
Malan 在第 2 周提到一个连接（linking）的分岔口——你的程序用到的库代码，是「嵌进」可执行文件里（静态链接），还是「运行时去系统里找」（动态链接）？
| 静态链接 | 动态链接 | |
|---|---|---|
| 怎么做 | 库的机器码被直接复制进你的可执行文件 | 库的机器码单独存放（.so / .dll / .dylib），运行时加载 |
| 文件大小 | 大（每个程序各带一份库的副本） | 小（所有程序共享同一份库文件） |
| 更新库 | 必须重新编译程序 | 替换库文件即可，不需要重编译程序 |
| 速度 | 略快（不需要运行时查找） | 略慢（但几乎感觉不到） |
| CS50 中 | clang hello.c -static -o hello | clang hello.c -o hello（这是默认行为） |
Malan 的评论：「动态链接是现代操作系统的默认选择——在你的 Mac 上打开『活动监视器』，你能看到几十个程序都在共享同一套系统库。如果库有安全漏洞，替换一个文件就能修好所有程序。这是计算机科学里最漂亮的共享设计之一。」
Malan 先演示了最朴素的调试法——printf 大法：在怀疑出问题的地方插 printf("到这里了，x = %i\n", x);。他说「这是全世界程序员最常用的调试技术，虽然不高级，但有效。」
然后他掏出真正的武器：debug50（CS50 封装的 GDB 前端）。设断点、单步执行、查看变量——Malan 现场演示了一段有 bug 的代码（数组求和，但没有初始化 sum 为 0，结果是垃圾值），然后用 debug50 逐行追踪，让学生眼睁睁看着 sum 从 32767 变成了 32768——「看，这就是内存里的垃圾。」
| 调试方法 | 怎么做 | 什么时候用 |
|---|---|---|
| printf 大法 | 在关键位置插 printf 打印变量值 | 快速定位「哪一步数据不对了」 |
| debug50 / GDB | 设断点 → 逐行执行 → 查看变量 → 看调用栈 | 逻辑 bug、需要看每一步变化时 |
| 橡皮鸭调试法 | 对着一个橡皮鸭（或任何不会还嘴的东西）逐行解释你的代码 | 你被卡住超过 15 分钟的任何时候。Malan 专门带了一只橡皮鸭到讲台上 |
Malan 的原话：「调试不是'找 bug'——调试是修正你对代码的认知。你写的代码做了你以为你让它做的事，而不是你以为它应该做的事。调试器让你看到真相。」
到目前为止你只能声明 int score1, score2, score3;。但如果你有 100 个学生呢？这就是数组存在的理由——一个名字，一组同类型的数据，用编号（索引）区分。
// 声明一个数组：3 个 int 排成一排
int scores[3]; // scores[0], scores[1], scores[2] 三个位置
// 赋值
scores[0] = 72;
scores[1] = 85;
scores[2] = 93;
// 声明 + 初始化二合一
int scores[3] = {72, 85, 93};
// 遍历数组——for 循环 + 数组 = 天生一对
for (int i = 0; i < 3; i++)
{
printf("第 %i 个学生的成绩：%i\n", i + 1, scores[i]);
}
几个硬核细节，Malan 会反复强调：
array[0]，不是 array[1]。这是计算机科学最古老的传统（因为 0 偏移量在底层寻址中更自然）malloc 见Malan 特别讨厌代码里的裸数字——3 个学生还好，100 个呢？每个用到的地方都要改。他用一行 #define 解决：
#define TOTAL 3 // 常量——要改只需要改这一行
int scores[TOTAL];
for (int i = 0; i < TOTAL; i++)
{
scores[i] = get_int("成绩 %i: ", i + 1);
}
这种「写死在代码里的数字」叫魔术数字（Magic Number）——过两周你自己都看不懂为什么这里写了个 3。
这是 Week 2 到 Week 4 之间最重要的伏笔。Malan 演示了把数组传给函数来求平均值：
float average(int array[], int length)
{
int sum = 0;
for (int i = 0; i < length; i++)
sum += array[i];
return (float) sum / length;
}
然后甩出一句话：「为什么我要同时传 array 和 length？因为 array 一进函数就退化成指针了——函数里只知道第一个元素的地址，根本不知道数组有多长。」 大部分学生听到这里只是默默点头。到 Week 4 学指针时他们才会惊觉——Malan 在第 2 周就已经说过答案了。
这是 C 语言最危险的特性之一。Malan 写了一段代码：
int scores[3] = {72, 85, 93};
// 故意越界
printf("%i\n", scores[3]); // scores 只有 0-2，3 是越界！
printf("%i\n", scores[-1]); // 负数索引！
C 不会阻止你。 它会乖乖地读出 scores[3] 所在的内存位置的值——那是什么？可能是另一个变量的值。可能是函数返回地址。可能是任何东西。Malan 把这种行为比喻成「你走到邻居家门口，发现门没锁，走进去拿了冰箱里的东西——没人阻止你，但后果自负。」
这就是 C 的双刃剑：给你完全的权力，也给你完全的责任。 大多数现代语言（Python、Java、Go）会在数组越界时直接报错并终止程序。C 不。这是它快的原因之一——它不检查。这也是它危险的原因之一。
Malan 终于揭开了 string 的真面目。他在黑板上画了一排格子：
索引: [0] [1] [2] [3] [4] [5] 字符: H i ! \0 ? ? // ↑ 空字符——字符串结束的标志
当你写 string s = "Hi";，内存里存的不是 2 字节，而是3 字节——H、i、和看不见的 \0（空字符，ASCII 码为 0）。这个 \0 是字符串的「终点标记」——printf 从第一个字符开始打印，遇到 \0 就停。
如果没有 \0 会怎样？printf 会继续往内存后面读——打印出一串垃圾，直到碰巧撞上下一个 \0。
C 的字符串不像 Python 那样自带方法。你不能 s.length()，不能 s1 == s2。你需要用标准库函数——都来自 #include <string.h>：
| 函数 | 做什么 | 注意 |
|---|---|---|
strlen(s) | 返回字符串长度（不含 \0） | 逐个数字符直到找到 \0。如果字符串没有 \0，它会一路数到天荒地老 |
strcmp(s1, s2) | 比较两个字符串是否相等。返回 0 表示相等 | 不能用 ==！ s1 == s2 比较的是两个内存地址，不是内容 |
strcpy(dest, src) | 把 src 拷贝到 dest | 你负责确保 dest 有足够空间。空间不够 → 缓冲区溢出 → 可能被黑客利用 |
strcat(dest, src) | 把 src 拼接在 dest 后面 | 同样，dest 必须有足够空间 |
Malan 在这一点上特别严肃：「
strcpy和strcat是历史上最臭名昭著的漏洞来源之一。1988 年莫里斯蠕虫——互联网第一个重大安全事故——就是利用了gets()函数（strcpy的表亲）的缓冲区溢出。」
标准库的补救措施：每个「危险」函数都有一个对应的「限制长度」版本——函数名里多加一个 n：
| 不安全的 | 安全的替代 | 区别 |
|---|---|---|
strcpy(dest, src) | strncpy(dest, src, n) | 最多拷贝 n 个字符，超出就截断 |
strcat(dest, src) | strncat(dest, src, n) | 最多拼接 n 个字符 |
gets(str) | fgets(str, n, stdin) | gets 在 C11 标准中已被彻底移除——它没有任何长度限制，是教科书级的危险函数 |
莫里斯蠕虫简史（1988 年 11 月 2 日）： 康奈尔大学研究生 Robert Morris 写了一个实验性程序——本意是想「偷偷数一下互联网上有多少台电脑」。但他代码里出了个小失误：蠕虫在侵入一台电脑后没有检查这台电脑是否已经被感染过。结果——同一台电脑被反复感染，直到系统崩溃。 蠕虫利用了 Unix 系统上
fingerd服务的gets()缓冲区溢出漏洞。大约 6000 台电脑宕机（占当时互联网的 10%）。Morris 被判 3 年缓刑 + 400 小时社区服务 + $10,050 罚款。后来他成了 MIT 教授……还是 Y Combinator 的联合创始人。
你之前写的 C 程序都是 int main(void)——注意那个 void，意思是「我不收任何参数」。但 main 其实可以这样写：
int main(int argc, string argv[])
{
// argc = 参数个数（包括程序名本身）
// argv = 参数数组（每个参数是一个字符串）
printf("你好，%s\n", argv[1]); // 打印第一个参数
}
这是你的程序第一次能像 gcc hello.c -o hello 这样从命令行接收参数。Malan 的解释非常简洁：
argc = argument count。永远至少是 1——因为 argv[0] 是程序自己的名字argv = argument vector。一个字符串数组你一直在写 return 0;，但可能没想过这个 0 去了哪里。Malan 演示：
int main(int argc, string argv[])
{
if (argc != 2)
{
printf("用法：%s <名字>\n", argv[0]);
return 1; // 非 0 = 出错了
}
printf("你好，%s\n", argv[1]);
return 0; // 0 = 一切正常
}
然后在终端跑完后输入 echo $?——它会打印上一个程序的退出码。0 是成功，非 0 是失败。这是程序之间通信的最基本方式。
Malan 用凯撒密码把数组、字符串、命令行参数、循环全串起来。任务：接受一个数字作为密钥，把输入文本中的每个字母向后移动 N 位。
密钥 = 1 明文：Hello 密文：Ifmmp （H→I, e→f, l→m, l→m, o→p） 密钥 = 13 明文：Hello, World! 密文：Uryyb, Jbeyq! （这是著名的 ROT13——来回转 13 位，两次回到原文）
这道题要求的核心能力：遍历字符串（字符数组）、判断大小写、处理 Z→A 的回绕（'Z' + 1 不是 'A'，是 '['！你必须自己写回绕逻辑）、用 argv[1] 读取密钥、用 atoi() 把字符串转成整数。
Malan 在黑板上逐步搭建的代码框架，还原如下（这是 CS50 Problem Set 2 的标准解法雏形）：
#include <stdio.h>
#include <stdlib.h> // atoi
#include <string.h> // strlen
#include <ctype.h> // isupper, islower, isalpha
int main(int argc, string argv[])
{
// === 第 1 步：验证命令行参数 ===
if (argc != 2)
{
printf("用法：%s <密钥>\n", argv[0]);
return 1;
}
int key = atoi(argv[1]); // 把字符串 "13" 转成整数 13
// === 第 2 步：获取明文 ===
string plaintext = get_string("明文：");
// === 第 3 步：逐字符加密 ===
printf("密文：");
for (int i = 0, n = strlen(plaintext); i < n; i++)
{
char c = plaintext[i];
if (isupper(c)) // 大写字母
{
// 'A' = 65。减去 'A' 得到 0-25 → 加密钥 → 取模 26 → 加回 'A'
printf("%c", (c - 'A' + key) % 26 + 'A');
}
else if (islower(c)) // 小写字母
{
printf("%c", (c - 'a' + key) % 26 + 'a');
}
else // 非字母（空格、标点）→ 原样输出
{
printf("%c", c);
}
}
printf("\n");
return 0;
}
核心公式 (c - 'A' + key) % 26 + 'A' 拆开看：
c - 'A'：把字母映射到 0-25 的数字空间（A=0, B=1, ..., Z=25）+ key：向后移动 N 位% 26：解决回绕问题——Z(25) + 1 = 26，取模 26 → 0 → A。没有这步，'Z' + 1 = '['+ 'A'：从数字空间映射回字母这段代码把 Week 2 分散的知识点全部缝在了一起：命令行参数（
argc/argv）、字符串转整数（atoi）、字符数组遍历（strlen）、ctype.h库函数、ASCII 算术运算、取模回绕。写完这道题，你对 C 的「手感」就基本成型了。
Week 3 是 CS50 的哲学课。前两周围绕「怎么写」，这一周围绕「怎么想」。Malan 会问一个简单到让人一愣的问题——「在电话簿里找一个人——最快的方法是什么？」——然后花整节课证明，这个问题的答案完全取决于电话簿的数据结构。他会在黑板上画出搜索和排序算法的运行轨迹，把学生叫上讲台站成两排演示冒泡排序和归并排序。到这节课结束时，你会掌握一个终身受用的思维工具——大 O 复杂度分析。
Malan 用两个问题开场：
// 在一个无序数组中找 needle。逐个看，找到了就返回 true
bool linear_search(int array[], int size, int needle)
{
for (int i = 0; i < size; i++)
{
if (array[i] == needle)
return true;
}
return false;
}
最坏情况：要找的元素在最后（或根本不存在）→ 需要查完所有 N 个元素。时间复杂度 O(n)。
Malan 重新拿起电话簿（Week 0 的记忆呼应）。这次他用 C 代码写出来：
bool binary_search(int array[], int size, int needle)
{
int left = 0;
int right = size - 1;
while (left <= right)
{
int middle = (left + right) / 2;
if (array[middle] == needle)
return true;
else if (array[middle] < needle)
left = middle + 1; // 丢掉左半
else
right = middle - 1; // 丢掉右半
}
return false;
}
每次循环砍掉一半搜索范围。1000 个元素 → 最多 10 步。100 万个元素 → 最多 20 步。时间复杂度 O(log n)。 这是质的飞跃——当 n 从 1000 变成 100 万，线性搜索慢了 1000 倍，二分搜索只多了一倍的步数。
Malan 在这里做了一个残酷的对比：「如果你的程序用线性搜索处理 40 亿条数据，而你用的是二分搜索——你的用户会以为你的程序没运行。因为 32 步后就出结果了，屏幕甚至还没来得及刷新。」
二分搜索快，但代价是数组必须先排序。Malan 在这里把讲台变成了真人场景——叫了 8 个学生上台，每人举一个数字牌，站成一排。 然后他逐个演示三种排序算法。
Malan 让相邻的学生两两比较——数字大的往右移一步。一轮下来，最大的数字「冒」到了最右边。然后对剩下的 n−1 个数字重复。学生们在讲台上像气泡一样来回交换位置，场面一度混乱。
void bubble_sort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
// 交换——还记得 Week 0 的杯子吗？
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
O(n²)。 两层循环嵌套 → n × n 次比较。100 个元素 ≈ 10000 次操作。10000 个元素 ≈ 1 亿次。Malan 的评价很直接：「教科书教你冒泡排序，是让你理解什么是 O(n²)——不是为了让你真的用它。」
这一轮策略不同：每一轮在整个数组中找出最小值，放到最前面。
void selection_sort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
int min_index = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[min_index])
min_index = j;
}
// 把找到的最小值与 i 位置交换
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
还是 O(n²)。 比较次数和冒泡一样多，但交换次数更少（每轮最多一次）。所以实际比冒泡快一点——但不多。
Malan 的表情变了。他说：「现在我们来点真正的算法。」归并排序的核心思想——分治法（Divide and Conquer）：
他在黑板上画了一棵树——从 8 个元素切到 1 个，再从 1 个合并回 8 个。树的高度是 log₂8 = 3 层，每一层需要合并 N 个元素。所以总操作量 = n × log n。O(n log n)。
Malan 让上台的学生重新演示——这次他们把数字分成两组、四组、八个单元素……然后按步骤合并。场面从混乱变成了有序的「舞蹈」。
O(n²) vs O(n log n) 的残酷对比：对 100 万元素排序——冒泡排序需要约 1 万亿次比较；归并排序只需要约 2000 万次。差距是 50000 倍。 这就是为什么「算法」不是一个可以「以后学」的话题——它是你代码性能的决定性因素。
Malan 在白板上画了一个坐标系——横轴是数据量 n，纵轴是操作次数。然后他画了四条线：
| 复杂度 | 名字 | n=1000 时 | n=100万时 | 典型算法 |
|---|---|---|---|---|
| O(1) | 常数时间 | 1 步 | 1 步 | 哈希表查找、数组索引 arr[i] |
| O(log n) | 对数时间 | ~10 步 | ~20 步 | 二分搜索 |
| O(n) | 线性时间 | 1000 步 | 100 万步 | 线性搜索、单层循环 |
| O(n log n) | 线性对数 | ~10000 步 | ~2000 万步 | 归并排序、快速排序 |
| O(n²) | 平方时间 | 100 万步 | 1 万亿步 | 冒泡、选择排序、双层嵌套循环 |
| O(2ⁿ) | 指数时间 | — | — | 暴力破解密码、某些递归问题。Malan：「这基本等于没用」 |
Malan 特别强调了大 O 的含义：「它不是精确的步数——它是当 n 趋于无穷时，运行时间的增长趋势。 O(n²) 的意思是，如果把数据量翻倍，运行时间大约翻四倍。你不需要知道精确数字——你只需要知道这件事有多严重。」
大 O 描述的是上界（最坏情况）。Omega 描述的是下界（最好情况）。同一个算法，两种记号可以不一样：
| 算法 | Ω（最好） | O（最坏） |
|---|---|---|
| 线性搜索 | Ω(1)——第一个就是 | O(n)——在最后或不存在 |
| 冒泡排序 | Ω(n)——数据已经排好了 | O(n²)——完全反序 |
| 二分搜索 | Ω(1)——第一刀就中了 | O(log n) |
Malan 在 Omega 之后再加了一个希腊字母——Theta（Θ）。当算法的最好情况和最坏情况完全相同时，你不需要分别说 Ω 和 O——直接用 Θ。
| 场景 | 例子 |
|---|---|
| 一个 for 循环遍历长度为 n 的数组 | 不管数据是什么，你都必须访问全部 n 个元素。Θ(n)。 |
| 数组求平均值 | 你必须把 n 个数全加一遍。无论数据怎么排——Θ(n)。 |
| 找数组中的最大值 | 你必须检查每一个元素才能确定谁最大——Θ(n)。 |
三种记号的关系图——Malan 在黑板上画的「复杂度三明治」：
Ω(最好) Θ(紧界) O(最坏) 线性搜索 Ω(1) — O(n) ← 最好≠最坏，没有 Θ 二分搜索 Ω(1) Θ(log n) O(log n) ← 其实平均和最坏一样 归并排序 Ω(n log n) Θ(n log n) O(n log n) ← 不管数据怎么排都一样 冒泡排序 Ω(n) — O(n²) ← 有 Θ 吗？没有，好坏差太多
「递归」是归并排序背后的核心机制，Malan 用一个更简单的问题引入——画一个三角形。 他在黑板上画了一个倒金字塔：
# ## ### ####
迭代（循环）写法你立刻就能写出来：
void draw(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
printf("#");
printf("\n");
}
}
然后他写了递归版——没有一句循环：
void draw(int n)
{
if (n <= 0)
return; // ← 基准条件：停止递归
draw(n - 1); // ← 递归调用：先画 n-1 层的三角形
for (int i = 0; i < n; i++)
printf("#"); // ← 然后画第 n 行
printf("\n");
}
Malan 的解释：「递归就像俄罗斯套娃。你打开一个娃娃，里面还有一个娃娃。你一直打，直到打到最小的那个——然后一层层合上。基准条件就是那个最小的、不再继续打开的娃娃。」
每个递归函数必须有两个部分：
| 组件 | 是什么 | draw(n) 中对应 |
|---|---|---|
| 基准条件（Base Case） | 什么时候停下来，不再调用自己 | if (n <= 0) return; |
| 递归调用（Recursive Call） | 用更小/更简单的问题调用自己 | draw(n - 1) |
忘了写基准条件 = 无限递归 = 栈溢出（Stack Overflow）。 每次函数调用都会在内存的「调用栈」上压一帧。递归没有终点 → 栈被压满 → 程序崩溃。那个著名的程序员问答网站 Stack Overflow 的名字就是这么来的。
画三角形很好，但递归的「教科书入门」是阶乘。Malan 在黑板上演示——比三角形更短，但比三角形更触及递归的数学本质：
// 阶乘的数学定义：
// fact(1) = 1
// fact(n) = n × fact(n-1) for n > 1
int fact(int n)
{
if (n == 1)
return 1; // ← 基准条件
else
return n * fact(n - 1); // ← 递归调用
}
Malan 在黑板上画了 fact(4) 的调用过程——一个向下扩展、再向上收缩的树：
fact(4)
→ 4 * fact(3)
→ 3 * fact(2)
→ 2 * fact(1)
→ return 1 ← 触底！基准条件
→ return 2 * 1 = 2
→ return 3 * 2 = 6
→ return 4 * 6 = 24
这就是「调用栈」（Call Stack）的视觉化：每层递归都是在栈上压一个「等着结果」的函数帧。 当 fact(1) 返回 1 时，最底层的帧弹出，结果向上传递——一路弹回 fact(4)，24 出炉。
Malan 在这里画了一张在后续课程中反复出现的图——一个栈，每次递归调用时向下生长一帧，归时逐帧销毁。这是 Week 4 内存布局（栈区 vs 堆区）的完美前奏。
看到了递归之后，Malan 回到归并排序，这次用递归写出来：
void merge_sort(int arr[], int left, int right)
{
if (left >= right)
return; // 基准条件：只剩 1 个元素
int mid = (left + right) / 2;
merge_sort(arr, left, mid); // 递归：排左半
merge_sort(arr, mid + 1, right); // 递归：排右半
merge(arr, left, mid, right); // 合并两个已排好的子数组
}
Malan 没有完整写 merge()——它太长了，会分散注意力。但他在黑板上画出了合并的过程：两个有序小数组，各有一个「手指」指着当前最小元素，比较两个手指指向的值，取小的放进大数组，手指后移——就像整理两副已经按大小排好的扑克牌。
这段代码完美展示了递归的本质：你把「排一整副牌」的问题，分解成「排半副牌」的问题——分解到每副牌只有 1 张（基准条件），然后从底层一层层合并。 你不需要理解每一步合并的细节——你只需要相信
merge_sort能排好半副牌，然后你负责合并。
Malan 在课上没有完整写 merge()（太长），但作为笔记，这里补全——它展示了临时数组、双指针扫描、和「剩余元素一次搬完」这三个核心技巧：
// 把 arr[left..mid] 和 arr[mid+1..right] 两个已有序的子数组合并
void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1; // 左半边元素个数
int n2 = right - mid; // 右半边元素个数
// 临时数组——存储左右两半的副本
int L[n1], R[n2];
// 拷贝数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 三根指针：i 指 L，j 指 R，k 指 arr
int i = 0, j = 0, k = left;
// 核心循环：比较 L[i] 和 R[j]，小的放进 arr[k]
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
// 扫尾：L 或 R 可能还剩元素没放完（另一方已经空了）
while (i < n1) arr[k++] = L[i++]; // L 有剩余
while (j < n2) arr[k++] = R[j++]; // R 有剩余
// 临时数组 L 和 R 是局部变量，函数结束时自动销毁
}
这段代码的几个巧思（Malan 会逐行拆解）：
arr[k++] = L[i++]——这是 C 语言的经典简写：先把值赋过去，然后两个指针都往后移。等效于 arr[k] = L[i]; k++; i++;Malan 在第 3 周末尾引入了 struct——这是为 Week 5 的数据结构（链表、哈希表）做铺垫。你之前只能声明 int、string、float——这些是 C 语言自带的。但如果想表示「一个人」（有名字和电话号码），你需要把不同类型的变量打包在一起：
// 定义一个新类型——就像你自己造了一个"模具"
typedef struct
{
string name;
string number;
}
person;
// 使用这个新类型
person alice;
alice.name = "Alice";
alice.number = "+1-617-495-1000";
// 数组里也可以放结构体
person phonebook[3];
phonebook[0].name = "Alice";
phonebook[0].number = "+1-617-495-1000";
. 是成员访问运算符——取这个结构体里的某个字段。Malan 说：「记住这个点。Week 5 你会需要它。」
Malan 把一个简单 phonebook 数组的搜索搬到了 struct 版本——这是你第一次把「算法」和「自定义数据类型」拼在一起：
// 在电话簿中按姓名搜索——线性搜索的结构体版
person find(person phonebook[], int size, string target)
{
for (int i = 0; i < size; i++)
{
if (strcmp(phonebook[i].name, target) == 0)
return phonebook[i];
}
person empty = {"", ""};
return empty; // 没找到，返回一个空 person
}
到这里，你已经把 Week 0-3 的知识全串起来了：结构体存储数据 → 数组组织数据 → 线性搜索查找数据 → strcmp 比较字符串。到 Week 5，Malan 会说「线性搜索太慢了」——然后掏出链表和哈希表来替换这个 phonebook 数组。
Malan 没有在第 3 周详细讲快排（它会在 Week 5 作为递归的深入案例回归），但他简要提了一句：归并排序不是唯一达到 O(n log n) 的算法，还有一个叫「快速排序」的，用的是分区而不是分半。
| 归并排序 | 快速排序 | |
|---|---|---|
| 策略 | 分治法——对半切，分别排序，再合并 | 分治法——选一个「基准」（pivot），小的丢左边，大的丢右边，再递归左右 |
| 时间复杂度 | Θ(n log n)——稳定不变 | O(n log n) 平均，O(n²) 最坏（每次选的 pivot 都是最小/最大值） |
| 空间 | 需要额外数组（L 和 R） | 原地排序——不需要额外的大数组。空间更省 |
| 选谁 | 当你需要稳定性（相同值的元素保持原顺序），或不能接受最坏 O(n²) 时 | 大多数实战场景——平均快于归并，且不额外占用内存 |
这可能是整个 CS50 最经典的场景，值得用文字还原：
Malan 叫了 8 个学生站上讲台，每人拿一个大数字牌，面朝观众站成一排。数字是乱的——7, 2, 5, 4, 1, 6, 0, 3。
冒泡排序演示：Malan 让学生们按相邻两人一组比较。第一轮：「7 大于 2？换位置。」讲台上两个人笨拙地交换位置。一轮结束，最大的 7 在最右边。然后：「再来一轮！但这次最右边那个已经排好了，不用动他。」 台下的学生开始笑——他们看到了 O(n²) 的「笨拙」。
选择排序演示：Malan 让学生们在整排里找最小的数字。「0！」拿着 0 的学生跑到最左边，和原来在那里的人交换。下一个最小的是 1——跑到第二位。这次少了很多交换，但找最小值的「扫视」依然要扫完整排。
归并排序演示：Malan 让学生先分散开——每个人自己就是一个「已排序数组」（只有一个元素当然有序）。然后两人一组合并——「2 和 7 谁小？2 排前面。4 和 5 谁小？4 排前面。」然后再四人一组合并。八个人像编舞一样在两分钟内完成了排序。台下一片掌声。
这个演示的精妙之处：你不需要一行代码，就直观地理解了 O(n²) 为什么比 O(n log n) 差。 看人演示算法，比看代码效率高一百倍。这也是为什么 Malan 愿意花 20 分钟做这些「街头魔术」——它种下的直觉会在你写代码时自动浮现。