CS-Fundamentals

上一篇讲怎么让程序跑快，这一篇回到起点：我们自己天天在用的那个东西，到底是怎么跑起来的。 bash、zsh、PowerShell，这些东西看起来平平无奇——你敲一行，它执行一行。但把它拆开看，CSAPP 前半本讲的所有东西都在里面：进程、文件描述符、系统调用、信号、进程组。写一个能跑的 shell，等于把整本书穿一遍。 所以这篇是收尾，也是串线。我会从零写一个能跑的最小 shell（msh），边写边把前面散落的知识点挂上去。全文的实验在 WSL（Ubuntu 22.04，gcc 13）里真编译真运行，strace 抓的原样贴出来。 一、shell 循环：那个看起来傻其实很妙的四步shell 的主结构简单到有点让人失望： flowchart TB R[读一行输入] --> P[解析成 argv] P --> B{内建命令?} B -- 是 --> E[在 shell 自己进程里执行] B -- 否 --> F[fork 出子进程] F --> X[子进程 exec 目标程序] X --...

写完并发再回头看性能，顺序其实是反的。按理说该先讲怎么让单线程跑快，再讲怎么把它拆到多核上去，CSAPP 第 5 章就是这个位置，夹在优化编译器和存储器层次中间。所以本篇的主线是单线程：同一份算法，换个写法，差出两三倍甚至几十倍，靠的到底是什么。 先摆一个反常的观察。我把同一个求和的三种写法放在本机跑了一遍： 123朴素双重 for 110.36 ms手工 4 路展开 180.79 mssum() 内建 19.90 ms 手工展开，教科书上正儿八经的“减少循环开销”手段，在这里比什么都不做还慢了 64%。而换成 sum() 之后快了 5.5 倍。 这个结果把我原本准备好的叙述顺序打乱了。它说明一件事：优化不是往代码里加招式，是先搞清楚瓶颈长在哪里，再决定动不动手。 下面按“先量、再改、改完再看”的次序走一遍。 一、先建立度量单位性能讨论最怕的就是含糊。所以先把两把尺子立起来。 flowchart LR A[时钟周期 CPE<br/>Cycles Per Element] --> B[每元素耗几个周期<br/>...

上一篇给临界区配了锁，看起来万事大吉。可锁这东西有个脾气：它让你在等别人的时候，也把别人挡在门外。挡得好是排队，挡出环来就是永久僵住——这就是本文要讲的死锁。 CSAPP 12.7 后半段把死锁拆成四句话：谁在等谁、环怎么形成、怎么防、防不住时怎么办。竞争那一半放在前面讲，因为它比死锁更常出现、更难发现。 一、两个病不是一回事先用一句话切开： 竞争（race）：多个执行流没同步地读写同一份数据，结果取决于调度顺序。它让程序结果错。 死锁（deadlock）：多个执行流互相等着对方持有的资源，谁也不肯放。它让程序永远停。 竞争是"算错了但还在跑"，死锁是"干脆不跑了"。从观测上讲，竞争比死锁难抓得多——死锁至少能看见进程挂住，而竞争经常跑一万次都对，等上线才咬你。上一篇里那个跨进程计数器丢掉的 81 万次，就是竞争留下的证据。 二、死锁的四个条件课本里叫 Coffman 条件，四条同时成立才可能死锁： flowchart TB D[死锁] D --> C1[互斥<br/>资源同一时刻只归一个人] ...

上一篇的 Echo 服务器有个致命毛病：accept 拿到连接之后，它就守着这一个客户端，对方不发数据，整个服务器就傻站着，后面排队的连接一个也进不来。想同时招呼几百个客户端，程序就得同时干几件事——这就是并发。 CSAPP 第 12 章有意思的地方在于，它前半章教你三种并发写法，后半章几乎全在讲这些写法会怎么咬你。这篇讲前半：并发的三条路线、线程共享了什么、丢失更新怎么来的、以及把窗口关上的那把锁。竞争与死锁的完整细节留给下一篇。 一、并发和并行，不是一回事日常说话这俩词混着用，课本里是两码事： 并发（concurrency）：多个逻辑流在同一个时间窗口内推进，物理上可以只有一个核，靠切换制造"同时在跑"的错觉。 并行（parallelism）：多个逻辑流在同一时刻真的同时执行，得有多个核。 flowchart TB subgraph C1[单核：并发] direction LR A1[A 跑] --> B1[B 跑] --> A2[A 跑] --> B2[B 跑] end sub...

你给异地的朋友寄过信吗？信封上写收件人地址，邮局按地址一层层转发，对方拆信读内容。计算机网络干的是同一件事，只不过把"信"换成"字节"，把"邮局"换成路由器，把"地址"换成 IP。CSAPP 第 11 章讲的就是：程序员怎么用一套统一的接口（socket），让两台机器像读写文件一样交换数据。 本文把客户端-服务器模型、协议分层、TCP/UDP、socket 接口、字节序坑、以及一个最小 Echo 服务器一次讲透。代码能跑的我都跑了，跑不了的（C 版需要 gcc）明确标出来。 一、客户端-服务器模型：一切网络的原点不管上层多花哨，绝大多数网络应用都逃不出这个模型： flowchart LR C[客户端<br/>发起请求 等响应] -->|网络| S[服务器<br/>常驻 被动等待请求] S -->|响应| C 客户端是主动方：在某个时刻启动，向已知地址发起连接，拿到结果就走人（浏览器、SSH 客户端都是）。 服务器是被动方：开机就常驻，绑...

一句话本质：Unix 把「一切皆文件」贯彻到极致——磁盘、键盘、屏幕、管道、socket，在进程眼里全是「一串字节」。你拿到手的不是文件对象，而是一个小整数（文件描述符 fd），所有读写都靠这个整数在系统调用层完成。理解 I/O，就是理解「fd 这个把手是怎么挂到内核里那张打开文件表上的」。 1. 钩子：为什么 printf 最终都落到屏幕？写 C 的人几乎都从 printf("hello\n") 起步，但很少有人追问：那串字符凭什么出现在终端上，而不是写进某个文件、或者发到网络？答案藏在两层间接之后——printf 先把字节塞进标准库的缓冲区，缓冲区满了或者遇到换行才调用 write(1, ...)；而 1 这个 fd，从进程出生的那一刻起就被内核默认指向了「终端」。 说白了，I/O 不是「操作文件」，是「拿着一个编号，去内核里翻一张表」。这一章就把这张表、这条链、以及几个最容易踩坑的返回值讲透。 2. Unix I/O 模型：万物皆字节流CSAPP 把输入/输出抽象得极简。一个 Linux 文件就是「一个 m 字...

一句话本质：虚拟内存是「一个间接层」——它让每个进程都以为自己独占一整块连续、从 0 开始的地址空间，而背后由操作系统 + MMU 悄悄把虚拟地址映射到物理内存的任意角落。这一层间接解决三件事：缓存（当主存用）、内存管理（隔离进程）、内存保护（权限）。 1. 钩子：为什么每个进程都「独享」4 GB？你在自己机器上同时开着浏览器、IDE、微信。它们都在读写「地址 0x400000」。如果地址就是物理内存，三个程序早就把彼此踩烂了。但现实是它们相安无事——因为程序看到的地址（虚拟地址）根本不是内存条上的物理位置，中间隔了一层由硬件+内核维护的页表。 CSAPP 把虚拟内存（VM）讲成三件独立但共用一套机制的事，这是本章和 61C《虚拟内存》最大的视角区别：61C 偏「硬件如何让地址翻译跑得快」，CSAPP 偏「VM 作为编程抽象，它给进程提供了哪三种能力」。 2. 地址空间：一个 N 元素的大数组地址空间就是「可能地址的有序集合」。虚拟地址空间大小为 $N=2^n$（$n$ 为地址位数；x86-64 用 48 位有效虚拟地址，即 $2^{48}$）。物理地址空间是内存条...

引子：CPU 跑得飞快，内存却拖了后腿上一篇我们聊了处理器怎么靠流水线把 IPC 怼上去。但有个尴尬的事实：CPU 算得再快，数据要是还在慢吞吞的内存里，它也只能干等。 现代 CPU 一个时钟周期能执行好几条指令，而从主存（DRAM）取一个字，动辄要几百个周期。这个时间差就是「存储器墙」。CSAPP 第 6 章给出的解法是存储器层次结构（memory hierarchy）——用一层层更小更快、也更贵的存储，把慢存储的延迟「藏」起来。而其中最关键的一层，就是 Cache。 本质一句话：Cache 之所以能加速，靠的不是魔法，而是「程序大多在反复访问同一小块数据」这个事实——局部性原理。 本文从存储技术讲起，落到 Cache 的地址划分、映射方式、缺失类型和写策略，把第 6 章的骨架讲透。 1. 为什么要分层：一个金字塔存储器的核心矛盾是：快的东西贵且小，大的东西便宜但慢。于是系统设计者把它们叠成金字塔——越往上越快越贵越小，越往下越慢越便宜越大。 graph TD L0["寄存器<br/>&lt;1ns · 几百字节"] ...

上一章我们看 gcc -Og -S 的输出，一条 C 语句常变成三五行汇编。但如果你以为 CPU 是"执行完一条再取一条"，那所有性能直觉都会跑偏：现代处理器在同一时刻手里至少攥着五条指令。 最典型的一幕是这样两行： 12mrmovq 8(%rsp), %rax # 从内存读一个值addq %rax, %rbx # 立刻用它 第二条在"执行"阶段就要用 %rax，可第一条的结果还卡在"访存"阶段。按最朴素的算法，CPU 得干等两拍；实际只停了一拍。这一章要拆的就是这个窟窿是怎么被填上的——顺带回答另一个问题：为什么整个流水线里最贵的指令是 jne。 1. ISA 是合同，微架构是实现先把两个容易混的词分清： ISA（指令集架构）：程序员看到的一切——有哪些指令、有哪些寄存器、内存怎么寻址、异常怎么触发。它是硬软件之间的合同。 微架构：这份合同的一种实现。同样的 x86-64 合同，Intel 用乱序超标量实现，AMD 用另一套，结果都能跑同一个二进制。 CSAPP 为了讲清微架构，自己造了...

两个 .c 文件，一个定义 int sum(int)，另一个 extern 声明它，各自编译都过，最后 gcc main.o sum.o 才变成一个能跑的进程。可如果你把这两个 .o 的顺序换成 gcc sum.o main.o 之外再加个静态库，就可能蹦出一句 undefined reference to 'addvec'——而那个符号明明就在你传给链接器的 .a 里。链接器不是"把一堆字节拼起来"，它是一道有状态的扫描过程：先收集符号，再决定谁被留下，最后才把地址填进指令里。 这一篇把 CSAPP 第 7 章讲透：编译系统四步、ELF 目标文件的内部结构、强/弱符号的三条规则、静态库为什么对命令行顺序敏感、重定位那条 PC 相对公式怎么手算、以及动态链接里 GOT/PLT 是怎么做到"第一次慢、以后直接跳"的。 1. 从 hello.c 到 a.out：四步走 预处理器 cpp hello.c → hello.i 编译器 cc1 hello.i → hello.s 汇编器 as hello....

一个"读一行输入再打印出来"的小程序，塞进去 80 个字母就崩了；同一个二进制，换台机器跑同样的输入却没事；某些崩溃信息里赫然写着 *** stack smashing detected ***，而另一些则静悄悄地把控制权交给了别人。这三件事背后是同一个机制：C 语言不为数组访问做任何边界检查，而函数的返回地址就躺在局部数组的高地址侧 —— 于是"写越界"这件事，在物理上等同于"改写程序接下来要执行哪条指令"。 这一篇把 CSAPP 3.10 那套攻防逻辑讲透：溢出是怎么发生的、攻击者如何从"改一个地址"升级到"执行自己的代码"、现代编译器和操作系统架了哪三道防线、以及这三道防线各自的缝在哪。 1. 先看清栈帧：返回地址就在缓冲区头顶函数调用时，x86-64 在栈上给被调函数划一块帧。以 echo() 里有一个 char buf[64] 为例，帧内从高地址到低地址依次是： echo() 的栈帧：返回地址就压在 buf 的头顶 高地址 0x7fffffffe1a8 返回地址（...

递归层数稍多一点程序就 Segmentation fault；两个看起来一样的循环，改了一行判断顺序性能差一倍；多线程里 i++ 累加结果永远小于预期。这三件事在 C 源码层面都"看起来没问题"——因为决定它们的是编译器生成的那条机器指令序列，而不是你写的那行 C。CSAPP 第 3 章干的事，就是把 C 和机器之间那层黑盒掀开：读得懂汇编，你才有资格谈"这段代码快不快"。 1. 从 C 到可执行文件：四步流水线一段 main.c 变成能跑的 a.out，中间经历四道工序，每一步产物都能落在磁盘上： 12345gcc -E main.c -o main.i # 1 预处理：展开 #include / #definegcc -Og -S main.i -o main.s # 2 编译：C -> 汇编文本（人能读的最后一层）gcc -c main.s -o main.o # 3 汇编：汇编 -> 可重定位机器码gcc main.o -o a.out # 4 链接：多个 .o + 库 ->...

0.1 + 0.2 在 C/Java 里都不等于 0.3；300 强转成 unsigned char 会变成 44；网络里收到的 0x12345678 在你本机读出来是 0x78563412。这三个"离谱"现象，根子都在同一个问题上：计算机怎么用 0/1 表示一个数。CSAPP 整门课都在讲"程序员的计算机系统视角"，第一篇就从地基开始——信息表示。 1. 位、字节与字长计算机只能存两种状态，记作 0 和 1，一位就叫一个 bit（位）。8 个 bit 组成 1 字节（byte），这是内存编址的最小单位。所谓"机器字长"，指 CPU 一次能处理的位数——64 位机器上指针就是 8 字节。写一段代码把"地基尺寸"打出来： 1234567891011#include <stdio.h>int main(void) { printf("sizeof(char) = %zu 字节\n", sizeof(char)); printf(...

1. 双核变四核，为什么没快 4 倍老板说"加机器就能快"，于是核心数从 1 涨到 4、到 64。可你一测：1 核跑 100 秒的任务，4 核跑了 30 秒——不是 25 秒；64 核竟然还有 20 秒。钱花出去了，倍数却越来越"不划算"。 这不是编译器偷懒，而是一条冷冰冰的物理/数学上限在起作用——Amdahl 定律。它回答的是：一个程序里只有一部分能并行，整体到底最多能快多少？ 本质一句话：程序里跑不并行的那一块，决定了它再怎么加核也快不到哪去。 2. 加速比：先定义"快了多少"记： 原串行总耗时 T₁（1 个核心跑完）。 并行化比例 P（0~1）：原本可以并行执行的那部分时间占比。 串行比例 1 − P：怎么都并行不了的硬骨头（初始化、I/O、临界区、依赖链）。 用 N 个核心跑，并行部分耗时按 N 等分缩成 P·T₁ / N，串行部分纹丝不动，仍是 (1 − P)·T₁。 于是 N 核总耗时： 12T(N) = (1 − P)·T₁ + P·T₁ / N = T₁ · [ (1...

1. 一行 C 代码，凭什么能点亮一盏灯嵌入式里最让人"上头"的一行代码，大概是这样的： 1*((volatile unsigned *)0x10012000) = 1; // 把 GPIO 某个引脚置 1，灯就亮了 从语法看，它无非是"往一个地址写 1"。可那个地址上既没变量、也没内存，而是一颗 LED 的引脚寄存器。为什么一行赋值就能让物理世界的灯亮？ 答案藏在一个核心事实里：软件和硬件之间，从来不是靠"魔法"对接，而是靠一份早就约定好的地址与规则——这份契约，就是本文的主题"硬件 / 软件接口"。 本质一句话：软件能指挥硬件，是因为有人把"硬件的开关"映射成了软件能访问的"地址"，并规定了访问它的规矩。 2. ISA：软硬件之间的第一份契约最底层的接口是指令集架构（ISA，Instruction Set Architecture）。它是 CPU 设计者和编译器作者之间的一份"互不入侵"的契约： 对软件（编译器 ...

1. 为什么 CPU 不能"干等"外设设想一个场景：CPU 想从磁盘读一个扇区。磁盘是机械部件——磁头要移动、盘片要旋转，一次读取就是几毫秒。而 CPU 的时钟周期以纳秒计，几毫秒相当于上百万个周期。 如果 CPU 发出读命令后就在原地等，那等于一台 3 GHz 的机器，为了等一个慢六个数量级的外设，把上百万个周期白白烧掉。这就是"CPU 与外设的速度鸿沟"——也是本章所有 I/O 机制的出发点。 本质一句话：I/O 的全部学问，就是想办法让慢速外设别把快速 CPU 拖死。 2. I/O 的三种基本方式处理器与设备交换数据，历史上演化出三种方式： 方式 等待期间 CPU 在干嘛 每块数据代价 适用场景 轮询（polling） 空转查状态位 等满整个设备延迟 极简单、极低速设备 中断（interrupt） 干自己的正事，就绪才被"打断" 一次上下文切换 中低速、事件驱动设备 DMA 完全不管，数据由控制器搬 只有开始/结束各一次中断 大块连续数据（磁盘、网卡、GP...

1. 为什么需要并行：三类并行层级CS61C 的核心立场是"把一台机器抽象出来给你看"。在"机器"这一层，性能提升几乎都来自并行——让硬件在同一时刻做更多事。并行按粒度从细到粗分成三类： 指令级并行（ILP, Instruction-Level Parallelism）：单条指令内部、或相邻指令之间重叠执行。我们前面讲过的流水线、乱序执行、转发（forwarding）都属于这一类。 数据级并行（DLP, Data-Level Parallelism）：同一份操作，作用在很多个数据点上。典型场景是"对 100 万个像素都加 10""把两个等长数组逐元素相加"。 线程级并行（TLP, Thread-Level Parallelism）：多核，每个核心跑不同的线程，甚至不同程序。 本篇聚焦 DLP，因为它最"便宜"：不需要多核、不需要改算法、不需要加锁，很多时候只把数据组织方式改一改，或者让编译器帮个忙，就能白捡数倍吞吐。 本质一句话：当同一件事要在大量数据上重复做时，就把"...

虚拟内存 一句话本质：虚拟内存是硬件（MMU）+ 操作系统共同提供的一块“每人独享整片地址空间”的幻觉——程序以为自己霸占了从 0 到 4GB/256TB 的全部内存，实际上物理内存被所有进程切片共享，地址翻译由 MMU 在每条指令取数时悄悄完成。 CS61C 站在机器/架构视角看虚拟内存：我们关心的是「一条 lw 指令里的地址是怎么变成内存条上某个字节的物理位置的」「为什么要分页」「TLB 为什么能让翻译几乎免费」。至于缺页时操作系统怎么换页、怎么选受害者页，那是 CS162 的主场（本文只在末尾点到为止并附对照）。 1. 为什么需要虚拟内存没有虚拟内存的裸机世界里，所有程序直接操作物理地址，会带来三个老大难： 隔离性为零：进程 A 写错一个指针就可能踩烂进程 B 的数据，甚至改掉内核。 地址空间碎片：程序加载时得去找一块足够大的连续物理内存，内存用久了就「东一块西一块」。 无法超配（overcommit）：物理内存只有 8GB，程序却想用 16GB？直接没门。 虚拟内存用一层地址抽象同时解决这三点： 每个进程拿到一个独立的虚拟地址空间（virtua...

上一篇我们让多条指令在流水线上重叠执行，把吞吐翻了几倍。但流水线有一个天敌：取指、访存要等内存。如果 CPU 每取一条指令、读一个变量都要干等内存几百个周期，流水线再深也救不回来。 这一篇往上抬一级视角，回答一个根本问题——为什么今天的计算机既能"内存很大"又能"访问很快"？ 答案是用层次结构（memory hierarchy）把"快而贵"和"慢而便宜"组合成一套用户看来又大又快的存储系统，而真正的魔法器件就是 Cache。 一句话定位：局部性是因，Cache 是果；命中是常态，缺失是代价。 1. 存储器层次：用金字塔换"又快又大"CPU 寄存器最快（亚纳秒、在芯片内），但容量只有几百字节；DRAM 主存便宜、能上 GB，但慢几十到上百倍；磁盘更便宜、能上 TB，但慢百万倍。如果只用一个层级，要么快得装不下，要么大得慢死。 寄存器 / L1 ~1ns 最贵 最少(KB) CPU Cache(L2...

前两篇我们把 C 翻译成了 RISC-V、把函数调用拆成了栈帧。但还有一个更底层的问题没回答：一条指令从"二进制"变成"动作"，在硬件里到底经历了什么？ 这一篇往下钻到门电路和时钟，再往上拉到流水线——看同一颗 CPU 是怎么靠"让多条指令重叠执行"把吞吐翻几倍的，以及翻倍的代价（冒险）。 一句话定位：组合逻辑管"算"，时序逻辑管"记"，流水线管"快"，冒险管"坑"。 1. 组合逻辑：没有记忆的电路组合逻辑（combinational logic）的定义是——输出只取决于当前输入，和过去发生过什么无关。给它同一组输入，永远得到同一组输出，它肚子里不存任何状态。 最小例子是半加器（half adder）：两个 1 比特相加。 123a ──┬── XOR ── sum │b ──┴── AND ── carry a b sum (a⊕b) carry (a·b) 0 0 0 0 0 1 1 0 1 0 1 0 1...

CPU 只有 32 个寄存器，但一段递归可以轻松嵌套一万层，每一层都有自己的一份局部变量、都记得该回到哪里去。这两件事摆在一起是有矛盾的：32 个格子，怎么装下一万层的现场？ 答案不在硬件里。RV32I 里没有一条叫「call」的指令，也没有任何一条指令知道「函数」是什么。函数是约定造出来的幻觉——一份编译器之间互相签署的合同，加一块叫做栈的内存。这一篇就把这份合同逐条拆开。 1. 一次函数调用要解决四件事先别看汇编，想想 C 里这一行发生了什么： 1int y = f(x) + 1; 拆成机器视角，有四个独立的问题需要各自解决： 问题 说白了 谁来解决 去哪儿 PC 得跳到 f 的第一条指令 jal 指令 怎么回来 f 结束时得知道跳回哪一条 返回地址寄存器 ra 参数怎么递 x 得让 f 看得见 ABI 约定：a0–a7 寄存器归谁 f 里也要用寄存器，会不会把我的值踩了 ABI 约定：caller/callee saved 前两个由硬件（指令）解决，后两个纯靠约定——硬件完全不管你有没有遵守。这就是为什么手写汇编最容易死在后两条上。 ...

上一课我们把 C 语言的指针和位运算拽到了门电路旁边。现在还有一道缝没填上：sum += a[i] 这么一行字，CPU 里那几十亿个门到底是"照着什么"动起来的？答案是指令——一串二进制码，每一条都对应硬件里一小段被点亮的通路。汇编就是这串二进制的人类可读写法。 这一篇只干一件事：把 RV32I 这套指令集讲透到"你能手写一个循环、并且知道每条指令在硬件里意味着什么"的程度。 1. 指令集是硬件与软件之间的合同CPU 不认识 C，也不认识 Java。它只认识一件事：从内存里取一个 32 位的数，按事先约定好的规则解码，然后驱动相应的电路。这份"事先约定好的规则"就是 ISA（Instruction Set Architecture，指令集架构）。 ISA 规定了三样东西，一样都不能少： ISA 规定什么 具体内容 为什么必须由 ISA 定 有哪些寄存器 RV32I：32 个 32 位通用寄存器 编译器要知道往哪儿放变量 有哪些指令 add / lw / beq …… 二进制码怎么解码是...

不管你平时写 Java 还是 C，这台计算机底下其实没有任何"对象"，只有一堆在 0 和 1 之间反复横跳的晶体管。CS61C 要做的，就是把"软件"一路拽回"硬件"的起点。这一篇干两件事：先用数字逻辑把"软件"接回"硬件"（门电路、加法器、补码），再系统回顾 C 语言里最容易踩的坑——指针、手动内存、位运算。 1. 什么是"位"：一切从开关开始计算机最底层没有整数、没有字符串，只有一个个能表示两种状态的元件——通电 / 断电，记为 1 / 0，这就是一个 bit（位）。把若干 bit 并排，就能表示更大的数：8 个 bit 叫 1 字节（byte），32 个 bit 是常见 int 的宽度。 单个 bit 太弱，于是我们用"门电路（gate）"把 bit 组合运算。门是接受若干 0/1 输入、输出一个 0/1 的小电路，由晶体管搭成。最基础的几种： AND &...

十篇走到最后。前面我们学了数组、链表、栈队列、树与平衡树、哈希、堆、图、并查集、排序——每一个都挂着一串 O(...)。可"复杂度"不是背结论，而是拿到一段代码或一道题，能亲手算出来、能选对数据结构。本篇把散落的工具收拢：怎么解递归式（主定理）、均摊分析回顾、以及一个"看到需求就选结构"的决策表。这是 CS61B 的收官，也是把前面九篇拧成肌肉记忆的一课。 一、实战：看到代码，算出复杂度1.1 循环套循环123for (int i = 0; i < n; i++) // n 次 for (int j = 0; j < n; j++) // 每次 n 次 sum += a[i] * b[j]; 外层 n、内层 n → O(n²)。 1.2 循环减半（二分、堆下沉）1for (int i = n; i > 0; i /= 2) process(i); // 每次规模 /2 i 走 n → n/2 → n/4 → … → 1，共 log₂ n 步 → O(log n)。 坑①：log...

前面几篇都在讲"怎么组织数据、怎么查找"。本篇补两个 CS61B 里极其常用、却容易被低估的工具：**并查集（Union-Find）**管"动态连通性"，三大 O(n log n) 排序管"把数据排好序"。它们一个藏在 Kruskal 最小生成树里，一个藏在 Arrays.sort 背后——看似简单，细节全是坑。 一、并查集：谁和谁是一伙的？一句话：并查集维护若干"不相交集合"，支持两个操作——find(x) 找 x 的祖先（代表），union(x,y) 把 x、y 所在集合合并。它回答的是"这两个元素连通吗"。 典型场景：逐步加边建网络，随时问"a 和 b 现在通不通"；或 Kruskal 算法里判断加一条边会不会成环。 1.1 朴素 vs 优化朴素实现 union 直接把一棵树挂到另一棵，最坏退化成链，find 变 O(n)。两个经典优化把它压到几乎 O(1)（反阿克曼函数 α(n)，实际常数级）： 按秩/大小合并（union by rank&...