算法与AI · 模块三 · 算法相关知识

3.1 复杂度大 O

Big-O · 数据涨 1000 倍，你的程序慢多少倍？

想是什么

大 O 描述算法随数据量 n 增长的"变慢速度"，只看最高阶项，忽略常数。从快到慢：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

n=100 万时：O(n²)=10¹² 次操作（跑一年）；O(n log n)≈2×10⁷ 次（一秒）。选错算法，差的不是一点半点，是生死。

例：100 万条数据排序，为什么必须选 O(n log n)？

冒泡 O(n²)=10¹² 次，快排 O(n log n)≈2×10⁷ 次。

解：假设每秒能算 10⁸ 次，冒泡要 10000 秒≈3 小时；快排 0.2 秒。这就是大 O 的意义——决定你是喝杯咖啡等结果，还是下班回来还在跑。

记

小结

① 大 O 只看最高阶。② 背熟排序 O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)。③ 写代码前先估 n，别让 O(n²) 撞 O(百万)。

3.2 排序算法

Sorting · 冒泡 / 快排 / 归并 / 插入

想四种主力排序

冒泡：相邻两两比，大的往后冒。简单但慢 O(n²)。

快排：选基准 pivot，比它小的扔左、大的扔右，递归排两边。平均 O(n log n)，最坏 O(n²)（基准选烂）。原地排序，常数小。

归并：分治：先拆成两半各自排好，再合并。稳定 O(n log n)，但要额外 O(n) 空间。

插入：像打扑克牌，每张牌插到前面已排好序列的正确位置。对近乎有序的数据极快 O(n)。

表 3-1 排序算法对比
算法	平均	最坏	空间	稳定
冒泡	O(n²)	O(n²)	O(1)	是
快排	O(n log n)	O(n²)	O(log n)	否
归并	O(n log n)	O(n log n)	O(n)	是
插入	O(n²)	O(n²)	O(1)	是

记

小结

① 通用选快排（平均最快）；要稳定选归并；近乎有序选插入。② "稳定"=相等元素相对顺序不变。③ Python sorted() 用的是 Timsort（归并+插入混合）。

3.3 二分查找

Binary Search · 查字典不用从第一页翻

想是什么

在有序数组里，每次猜中间，小了右半、大了左半。n 个数最多 log₂n 次。100 万个数只要 20 次。

前提铁律：必须有序。无序就先排序（O(n log n)），但一次排完可查很多次。

例：在 [1,3,5,7,9,11,13] 找 7

下标 0~6。

解：mid=3，a[3]=7 命中。变种：找"第一个 ≥ 7"、"最后一个 < 7"，改一下收缩方向即可。

防坑

坑：mid = (low+high)/2 在大数时溢出。为什么错？low+high 可能超整数范围。正解：mid = low + (high−low)/2。另外注意死循环：收缩时别把 mid 留在区间里。

记

小结

① 有序 + 每次砍一半 = O(log n)。② 经典应用：通讯录、数据库索引、猜数字。③ 注意 mid 计算和边界收敛。

3.4 递归与分治

Recursion & Divide-and-Conquer · 俄罗斯套娃

想是什么

递归：函数自己调用自己，必须有"出口"（base case）。分治三步：分（拆小）→ 治（解最小子问题）→ 合（拼结果）。

归并排序、快排、二叉树遍历、汉诺塔都是分治。

例：汉诺塔 n 个盘子移到 B，几步？

三根柱，大盘不能压小盘。

解：先把上面 n−1 个移到 C（递归），再把最大盘移到 B，再把 n−1 个从 C 移到 B。步数 T(n)=2T(n−1)+1，得 T(n)=2ⁿ−1。n=64 时搬完要 5800 亿年——这就是 O(2ⁿ)。

防坑

坑：递归太深栈溢出。为什么错？每次调用压一层栈，Python 默认上限 1000 层。正解：能迭代就迭代；必须递归就加 sys.setrecursionlimit 或改尾递归。

记

小结

① 递归=自己调自己，必须有 base case。② 分治=分→治→合。③ 警惕栈溢出和重复子问题（后者该用 DP）。

3.5 动态规划

Dynamic Programming · 记住答案不重复算

想是什么

分治拆出的子问题大量重复，递归算一遍又一遍，慢死。DP 的招：把子问题的答案存进表，下次查表不重算。

四步：① 定义状态 dp[i]；② 写转移方程 dp[i]=...；③ 初始化 base；④ 定遍历顺序。

例：爬楼梯，一次跨 1 或 2 阶，到第 n 阶几种走法？

n=1→1，n=2→2（1+1 或 2）。

思路：到第 n 阶，要么从 n−1 跨 1 步，要么从 n−2 跨 2 步。

解：dp[n] = dp[n−1] + dp[n−2]。dp[1]=1, dp[2]=2。dp[3]=3, dp[4]=5, dp[5]=8……这就是斐波那契。递归会重复算 O(2ⁿ)，DP 填表 O(n)。

经典 DP

背包问题、最长递增子序列、编辑距离、股票买卖。

技术里

DNA 序列比对、语音识别、Word 的拼写纠错。

记

小结

① DP=递归+备忘录。② 四步：状态→转移→初始化→遍历。③ 重叠子问题是 DP 的入场券。

3.6 贪心算法

Greedy · 走一步看一步，每步选当下最优

想是什么

贪心不回头：每步选当前看起来最好的，不保证全局最优，但在某些问题上恰好最优。

判断能不能贪心：局部最优叠加是否=全局最优？是→贪心；否→DP。

例：找零钱，面额 1,5,10,25，凑 36 分最少几枚？

贪心：每次拿最大不超过剩余的面额。

解：25 余 11，10 余 1，1。共 3 枚（25+10+1）。但若面额是 1,3,4，凑 6：贪心给 4+1+1=3 枚，最优是 3+3=2 枚。所以贪心不是万能的，得先验证。

经典

活动选择（不冲突活动最多排几场）、霍夫曼编码。

技术里

数据压缩、任务调度、近似算法。

记

小结

① 贪心=局部最优，简单快但不一定对。② 必须先证明贪心选择性质。③ 不满足就别硬上，转 DP。

3.7 图算法

Graph Algorithms · BFS / DFS / Dijkstra / MST

想五大件

BFS（广度优先）：一层一层扩，用队列。无权图最短路径就是它。

DFS（深度优先）：一条路走到黑再回头，用栈/递归。拓扑排序、连通分量用它。

Dijkstra：有权图单源最短路径，贪心+优先队列，O((V+E) log V)。不能有负权边。

Floyd：多源最短路径，O(V³)，小图好用。

最小生成树（MST）：Prim / Kruskal，连起所有节点总边权最小。Kruskal 配合并查集。

例：地铁图从家到公司几站？为什么 BFS 给最短？

边权都是 1（一站算一步）。

解：BFS 按"站数"一层层扩，第一次到达公司时，层数就是最少站数。无权图 BFS 天然给最短路。若边权不同（公交/地铁/步行时间不一），换 Dijkstra。

生活里

地图导航、社交网络"你和马云隔几个人"。

技术里

网络布线（MST）、课程依赖（拓扑排序）、路由协议。

记

小结

① 无权最短路 BFS，有权最短路 Dijkstra。② 连通分量/拓扑 DFS。③ 布线最小 MST（Prim/Kruskal）。

3.8 字符串基础

String · 匹配、Trie、回文

想三件套

字符串匹配：在长串里找模式串。暴力 O(nm)；KMP 入门 O(n+m)，靠"失败函数"避免回头。

Trie 前缀树：把所有词按字符挂成树。搜"app" 直接到 app 节点，O(词长)。搜索框自动补全的底层。

回文：正反读一样，如"上海自来水来自海上"。双指针从两头往中间比 O(n)。

例：判断 "abcba" 是不是回文

两端指针。

解：左 a 右 a 等；左 b 右 b 等；中间 c 单独。全过，是回文。若 "abca"：左 a 右 a 等，左 b 右 c 不等，不是。

记

小结

① 匹配先想 KMP；自动补全用 Trie；回文双指针。② 这些是 NLP 的前菜——大模型处理文本前先在字符级打过交道。

3.9 动态规划进阶：状压 / 树形 / 数位

Advanced DP · 状态压缩、树上 DP、逐位 DP

想引子与大白话

引子：10 个城市跑一趟最短路线，全排列是 10! = 362 万种。但用 DP 记住"去过哪些城市"，能压到 2¹⁰ × 10 ≈ 1 万种。这就是状态压缩 DP——把"子集"塞进一个二进制数。

① 状压 DP：子集信息压进整数 bitmask。经典代表旅行商 TSP：dp[mask][j] = 已访问集合 mask、当前在城市 j 的最短距离。转移：dp[mask][j] = min over k in mask of dp[mask\{j}][k] + dist(k,j)。O(2ⁿn²)。

② 树形 DP：在树上递归，dp[u] 由子节点 dp[v] 合并。例：树的最大独立集 dp[u][0/1]（选/不选 u）：选 u 则不能选子节点；不选 u 则子节点可选可不选取 max。

③ 数位 DP：逐位统计 [0, N] 里满足条件的数。例：1 到 100 万有多少个不含数字 4 的数？记忆化搜索 dfs(pos, tight) 逐位填。

例：n=10 个城市，TSP 用状压 DP 要多少状态？

mask 有 2ⁿ 种，当前城市 n 种。

思路：状态数 = 2¹⁰ × 10 = 10240。

解：每个状态转移枚举上一个城市 k，O(n)。总时间 O(2ⁿn²) = 1024×100 ≈ 10 万。对比全排列 10! = 362 万，快 36 倍。n=20 时 2²⁰×20² ≈ 4 亿还能跑；n=30 就爆了——这也是为什么 TSP 是 NPC。

// TSP 状压 DP 核心（Python 风格伪代码）
INF = float('inf')
dp = [[INF]*n for _ in range(1<<n)]
dp[1][0] = 0                          # 只访问过城市 0，当前在 0，距离 0
for mask in range(1<<n):           # 枚举所有"去过哪些城市"的子集
    for j in range(n):
        if not (mask >> j) & 1: continue   # j 不在集合里，跳过
        for k in range(n):
            if k == j or not (mask >> k) & 1: continue
            dp[mask][j] = min(dp[mask][j], dp[mask^(1<<j)][k] + dist[k][j])
ans = min(dp[(1<<n)-1][j] for j in range(n))

经典

TSP 物流配送、二进制枚举子集；树上最大独立集、树直径；数位统计题。

判断

状态里有"选/不选若干个元素"→ 状压；在树上父子递推 → 树形；统计 1~n 数字 → 数位。

防坑

坑：状压 DP 把 n 估大。bitmask 是 2ⁿ，n=20 还能跑，n=25 就 3300 万状态了，n=30 直接爆内存。看到 n≤20 才往状压想；n 上百的 TSP 只能用近似算法（见 3.12）。

练一练

基础n=12 个城市，状压 TSP 的状态数约多少？

看答案

2¹² × 12 = 49152 个状态，时间 O(2¹²·12²) ≈ 70 万，轻松跑。

进阶树的最大独立集，选了节点 u 还能选它的孙子节点吗？

看答案

能。独立集只要求"相邻节点不同时选"，祖孙不相邻。dp[u][选] = Σ dp[v][不选]；dp[u][不选] = Σ max(dp[v][选], dp[v][不选])。

自评反馈：答对了继续；状压/树形 DP 的状态定义，回看动态规划那一节。

记

小结

① 状压 DP 用 bitmask 表子集，TSP O(2ⁿn²)，n≤20 可上。② 树形 DP 沿父子递归合并。③ 数位 DP 逐位记忆化统计。

3.10 字符串匹配进阶：KMP / Rabin-Karp / AC 自动机

KMP, Rabin-Karp, Aho-Corasick · 不回头地找模式串

想引子与大白话

引子：在 100MB 日志里搜 "ERROR"。暴力法每个位置都比 5 个字符 O(nm)，太慢。KMP 的绝招是：打错字了不从头来，而是回到"已经匹配过的最长前缀"继续——文本指针绝不回退。

① KMP：预处理模式串 P，算 next 数组（每个前缀的最长相等真前缀=真后缀长度）。匹配时 j 指向 P 的位置，失配就让 j = next[j]，文本指针 i 不动。O(n+m)。

② Rabin-Karp：把模式串哈希成一个数，文本滑动窗口滚动哈希——滑过一格，新哈希 = (旧哈希 − 离开的高位×基数) × 基数 + 新进来的低位。哈希相等再逐字符确认（防爆哈希碰撞）。平均 O(n+m)。

③ AC 自动机：多模式匹配。把所有模式建 Trie，再加失配指针 fail（类似 KMP 的 next）。扫一遍文本，同时找出所有模式串出现位置。敏感词过滤标配。

例：模式串 P="ababaca"，next 数组是什么？

next[j] = P[0..j−1] 的最长真前缀=真后缀长度。

思路：逐前缀算。P[0..3]="abab"，最长公共前后缀是 "ab"，长 2。

解：next = [−1, 0, 0, 1, 2, 3, 0]（下标 0..6）。失配时 j 跳到 next[j]，i 不回退——这就是"不傻乎乎回溯"的精髓。

// KMP 求 next 数组 + 匹配（C 风格伪代码）
void build_next(string p, int next[]) {
    next[0] = -1;
    for (int j = 1, k = -1; j < p.size(); j++) {
        while (k >= 0 && p[j] != p[k+1]) k = next[k]; // 失配回退
        if (p[j] == p[k+1]) k++;
        next[j] = k;
    }
}
int kmp(string text, string p, int next[]) {
    for (int i = 0, j = -1; i < text.size(); i++) {
        while (j >= 0 && text[i] != p[j+1]) j = next[j]; // i 不动，j 回退
        if (text[i] == p[j+1]) j++;
        if (j+1 == p.size()) return i-j;   // 命中位置
    }
    return -1;
}

技术里

编辑器/grep 查找用 KMP；敏感词过滤、拼写检查用 AC 自动机；Git diff、DNA 比对本质是字符串匹配。

选型

单模式串→KMP；多模式串→AC 自动机；需要同时算哈希指纹→Rabin-Karp。

防坑

坑：next 数组边界写错。next[0] 一般取 −1（哨兵），构建和匹配时"先 while 回退、再比较、再 j++"的顺序不能乱。另外 Rabin-Karp 别忘记模大质数——不然哈希值爆炸；且哈希相等后必须逐字符确认，防碰撞。

练一练

基础KMP 为什么文本指针 i 不回退？

看答案

已匹配部分的后缀等于模式串前缀（next 数组保证的），这部分字符不需要重新比较，直接跳过。所以总 O(n)。

进阶为什么多模式匹配要用 AC 自动机而不是对每个模式跑一次 KMP？

看答案

跑 k 次 KMP 是 O(k·n)；AC 自动机把 k 个模式建成一张 Trie+fail，一次扫文本 O(n + 命中数)，k 个模式只扫一遍。

自评反馈：答对了继续；KMP 的 next 数组怎么来的，回看字符串匹配那一节。

记

小结

① KMP O(n+m)，靠 next 数组失配回退不回头。② Rabin-Karp 滚动哈希平均 O(n+m)。③ AC 自动机=Trie+fail 指针，多模式一次扫。

3.11 计算几何：点积、叉积与凸包

Computational Geometry · 用向量算几何

想引子与大白话

引子：平面上 100 个点，求最小的凸多边形把它们全围起来——手画容易，让计算机怎么判"左转还是右转"？靠叉积。

点积 a·b = aₓbₓ + a_y b_y：判断夹角锐角(>0)还是钝角(<0)，也用来算投影。

叉积（二维）cross(a,b) = aₓb_y − a_y bₓ：符号决定方向。>0 表示 b 在 a 的逆时针（左）侧，<0 顺时针（右）侧，=0 共线。绝对值 = 两向量张成的平行四边形面积（三角形面积是它的一半）。

凸包（Graham 扫描）：找 y 最小的点 O 作起点，其余点按极角排序，逐点入栈；新点让栈顶两点形成右转就弹出栈顶，保持栈内始终左转。O(n log n)（排序主导）。

例：O=(0,0)，A=(1,0)，B=(1,1)，B 在 OA 哪侧？

算 cross(O,A,B)。

思路：向量 OA=(1,0)，OB=(1,1)。cross = 1×1 − 0×1 = 1。

解：cross = 1 > 0，B 在 OA 左侧（逆时针）。Graham 扫描遇到左转就入栈，遇到右转就弹出栈顶——保持凸性。

// 叉积判方向 / Graham 凸包核心（Python 风格）
def cross(o, a, b):                       # (a-o) × (b-o)
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

pts.sort(key=lambda p: p[1])           # 找最下面的点作起点
o = pts[0]
pts.sort(key=lambda p: math.atan2(p[1]-o[1], p[0]-o[0]))  # 按极角排
stack = []
for p in pts:
    while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
        stack.pop()                        # 右转/共线就弹栈顶
    stack.append(p)
# stack 里就是凸包顶点

技术里

游戏碰撞检测、地图导航最短路径、图形学裁剪、机器人运动规划，全靠叉积判转向。

其他

线段相交判断：用两次叉积（两线段端点互相在对方两侧）；最近点对用分治 O(n log n)。

防坑

坑：浮点比较别直接 == 0。叉积算出来是浮点，判共线要用 |cross| < eps（eps 如 1e-9）。另外凸包排序的起点必须选"最下最左"的点，否则极角排序会乱。

练一练

基础cross(a,b) < 0 表示 b 在 a 的哪一侧？

看答案

<0 表示顺时针方向，即右侧。=0 共线。

进阶三角形 ABC 的面积怎么用叉积算？

看答案

面积 = |cross(B−A, C−A)| / 2，即平行四边形面积取一半。

自评反馈：答对了继续；叉积正负判断方向，回看计算几何那一节。

记

小结

① 叉积符号判左右、绝对值算面积。② Graham 扫描 O(n log n) 求凸包，左转入栈、右转弹出。③ 浮点判共线用 eps。

3.12 随机算法与近似算法

Randomized & Approximation · 赌一把但有保证

想引子与大白话

引子：n=1000 的 TSP 求最优解要算到宇宙热寂。别求最优了，求个"最多比最优差 50%"的近似解，多项式时间内搞定。这就是近似算法。

① 蒙特卡洛（Monte Carlo）：可能出错，但错误概率可控。例：Miller-Rabin 素性测试——多测几轮，错误概率降到可忽略。

② 拉斯维加斯（Las Vegas）：一定对，但期望时间快。例：随机化快排、随机选 pivot 的快速选择。

③ 近似算法：对 NP-hard 问题求 c-近似解（解 ≤ c·OPT）。例：顶点覆盖贪心选边得 2-近似；TSP 用 MST 加倍边得 2-近似。

例：随机选 pivot 的快排，期望比较次数？

算每对元素被比较的概率。

思路：元素 i,j 会比较，当且仅当它们中间区间里先被选为 pivot 的那个是 i 或 j。

解：概率 = 2/(j−i+1)。总期望 = Σ_{i<j} 2/(j−i+1) = O(n log n)。最坏 O(n²) 但概率极低可忽略。这就是"赌一把但期望稳"。

技术里

RSA 加密前测素数用 Miller-Rabin；大系统抽样、π 估值用蒙特卡洛；物流调度求次优路线用近似算法。

记忆

蒙特卡洛=错但可控概率；拉斯维加斯=对但期望快。别记反。

防坑

坑：把近似解当最优解用。近似算法只保证"性能比 c"，不保证最优。2-近似意思是"不会比最优差一倍"，但你不知道最优是多少，也不知道自己落在哪。工程上够用就行，别吹成最优。

练一练

基础快速选择（找第 k 小）期望多少？

看答案

随机选 pivot，期望 O(n)（每次期望砍掉一半元素，n + n/2 + n/4 + ... = 2n）。

进阶为什么说"蒙特卡洛可能错，拉斯维加斯一定对"？

看答案

蒙特卡洛：运行时间固定，答案可能错（如素性测试误判合数为素）。拉斯维加斯：答案必对，但运行时间随机（如随机快排偶发变慢）。两者都是"用随机换保证"。

自评反馈：答对了继续；随机算法的期望复杂度，回看随机/近似那一节。

记

小结

① 蒙特卡洛错但概率可控；拉斯维加斯对但期望快。② NP-hard 问题求 c-近似，顶点覆盖贪心 2-近似。③ 随机快排期望 O(n log n)。

3.13 P / NP / NPC / NP-hard：计算的难易地图

Complexity Classes · 千禧年百万美元难题

想引子与大白话

引子：为什么排序能 O(n log n) 秒解，而 n=20 的 TSP 就算不动？不是你笨，是问题本身分难易。这就是 P vs NP——悬赏 100 万美元的未解之谜。

P 类：多项式时间内能解的问题。排序、最短路径、二分查找。

NP 类：多项式时间内能验证答案的问题。给你一组布尔赋值验证 SAT 真假，快；但找这组赋值，慢。

NP-complete（NPC）：NP 里最难的。所有 NP 问题都能多项式时间归约到它。Cook-Levin 定理：SAT 是第一个 NPC 问题。

NP-hard：至少和 NPC 一样难，不一定在 NP 里。例：TSP 求最优路径（验证"这是最优"也要 O(n!)）。

例：TSP、背包、SAT、最短路径，哪些是 NPC？

回忆 NPC 清单。

思路：已知 NPC：SAT、3-SAT、TSP 判定版、0-1 背包、顶点覆盖、团、哈密顿回路、子集和。

解：TSP 判定版（是否存在 < k 的路线）、0-1 背包、SAT 都是 NPC；最短路径（Dijkstra）是 P。NPC 问题目前没有已知多项式算法。

为什么关心

如果 P=NP 成立，RSA 等公钥密码全崩、NPC 问题秒解、AI 规划变平凡——所以大家默认 P≠NP 押注。

常见 NPC

SAT / 3-SAT / 顶点覆盖 / 哈密顿回路 / 子集和 / 背包判定版。遇到这些别硬求最优，靠近似。

防坑

坑：把 NP 理解成"非多项式时间可解"。错！NP = Nondeterministic Polynomial（非确定性多项式可验证），不是 "No Polynomial"。P ⊆ NP，P=NP 至今未解。另外"NP-hard 一定是 NPC"也错——NP-hard 可能不在 NP 里（验证都慢）。

练一练

基础P 和 NP 谁包含谁？

看答案

P ⊆ NP：能多项式时间解的，当然也能多项式时间验证。P=NP 是否成立就是那个百万美元问题。

进阶顶点覆盖判定版（是否存在 ≤ k 个顶点覆盖所有边）为什么是 NPC？

看答案

它在 NP 里（给你 k 个点，多项式时间验证是否覆盖所有边）；且已知能从 3-SAT 多项式归约到它，所以它是 NPC。

自评反馈：答对了继续；P/NP/NPC 的包含关系，回看复杂度类那一节。

记

小结

① P=快解；NP=快验证；NPC=NP 里最难；NP-hard ≥ NPC。② P vs NP 悬赏百万，默认 P≠NP。③ NPC 问题求近似解，别硬刚最优。

3.14 图算法进阶：拓扑排序 / 强连通分量 / 二分图 / 网络流

Topo Sort / SCC / Bipartite / Max-Flow · 图论的进阶四件套

想引子与大白话

引子：选课要先修先修课、找两个集合间最大配对数、算水管网络最大流量——这些都不是"最短路"能搞定的，需要图论的进阶武器。

① 拓扑排序（Topological Sort）：对有向无环图（DAG）排出一个"所有边都从左指右"的顺序。Kahn 算法：反复挑入度为 0 的点输出、删掉它的出边。排不出来=有环。课程依赖、编译依赖、任务调度。O(V+E)。

② 强连通分量（SCC）：有向图里"两两互相可达"的最大子图。Tarjan 用 DFS 时间戳+low 值，一次遍历 O(V+E) 切出所有 SCC。缩点后整个图变成 DAG。社交网络圈子、电商"团伙"识别。

③ 二分图匹配（匈牙利算法）：图能染成黑白两色且边总跨色，就是二分图。求"男生×女生"最大配对数：匈牙利 DFS 找增广路 O(VE)。任务分配、相亲、调度。

④ 最大流 / 最小割：源点 s 到汇点 t，每条边有容量，求最多能流多少。Ford-Fulkerson / Dinic 算法。最大流 = 最小割（Max-Flow Min-Cut 定理）——切断多少流量就断了网络。网络路由、图像分割、二分图匹配（它就是最大流的特例）。

例：3 门课依赖 A→C、B→C，拓扑序怎么排？

A、B 都指向 C。

解：A、B 入度都是 0，先输出 A（或 B），删 A→C；再输出 B，删 B→C；最后 C 入度变 0 输出。拓扑序 A,B,C 或 B,A,C。若有 A→B、B→C、C→A，入度永远不为 0，排不出来——有环。

// Kahn 拓扑排序核心（Python 风格伪代码）
from collections import deque
indeg = [0]*n
for u,v in edges: indeg[v] += 1      # 统计入度
q = deque([i for i in range(n) if indeg[i]==0])
order = []
while q:
    u = q.popleft(); order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v]==0: q.append(v)
if len(order) < n: print("有环，无法拓扑排序")

技术里

拓扑排序=编译依赖/课程安排；SCC=朋友圈/电商团伙；二分图匹配=招聘分配；最大流=运力/图像分割。

判断

有先后依赖且无环→拓扑；要找互达圈子→SCC；两类资源配对→二分图；求流量/切断→最大流最小割。

防坑

坑：把拓扑排序用到有环图。Kahn 跑完 order 长度 < n 就是有环，别强输出。另外最大流的边要建反向边（残量网络），否则没法"反悔"增广；Dinic 用当前弧优化+分层图才能在大图上跑快。二分图匹配本质就是源点连左部、右部连汇点的最大流。

练一练

基础Kahn 算法跑完输出的节点数比总节点少，说明什么？

看答案

说明图里有环——环上的点入度永远减不到 0，进不了队列。DAG 才能拓扑排序。

进阶最大流最小割定理说的"割"是什么意思？

看答案

割=把点集切成含 s 和含 t 两半，割的容量=从 s 侧指向 t 侧的边容量和。最大流等于最小割——你最多送多少流，就等价于切断多少条边能让 s 和 t 断联。

自评反馈：答对了继续；拓扑判环、最大流=最小割哪条还卡，回看这一节。

记

小结

① 拓扑排序=剥入度，剥不净=有环。② SCC 把有向图缩成 DAG。③ 二分图匹配=找增广路。④ 最大流=最小割，残量网络建反向边。

3.15 字符串进阶：Manacher 回文 / 后缀数组 / BM

Manacher / Suffix Array / Boyer-Moore · 回文与多模式的进阶武器

想引子与大白话

引子：找最长回文子串、词典里所有以某串开头的词、在正文里飞快找一个词——暴力法 O(n²) 太慢，这三件武器把它们压到 O(n) 或 O(n log n)。

① Manacher（马拉车）：在 O(n) 内找最长回文子串。核心：利用已经算出的回文半径，借助"对称性"直接从对称位置继承半径，只在最右端外才扩展。比中心扩展 O(n²) 快一个量级。经典题"最长回文子串"的最优解。

② 后缀数组（SA）：把字符串所有后缀排个序，得到 SA（第 k 小的后缀起始位置）和 rank。用途：最长公共子串（两个串拼起来求 SA，相邻后缀 LCP 最大）、重复子串数量、压缩。DC3 / 倍增法 O(n log n)。

③ Boyer-Moore（BM）：匹配时模式串从右往左比。遇到坏字符就按"坏字符规则"直接跳一大段（跳到该字符在模式串上次出现的位置），好后缀再加速。实际比 KMP 还快，grep 底层就用它。

例：文本 "abacabad" 找最长回文子串

中心扩展法要 O(n²)，Manacher O(n)。

解："abacaba" 就是以中心 c 对称的回文，长 7。Manacher 用已算过的回文半径，直接知道中心 c 两侧对称，不用重新往外试。关键技巧：插入 '#' 把奇偶长度统一（如 a#b#a#c#a#b#a#d），就不用分奇偶中心讨论。

技术里

Manacher 解最长回文子串题；后缀数组做文本压缩/重复检测；BM 是 grep 的快搜引擎。

和 AI 关系

这些是字符级基本功。NLP 早期（拼写检查、DNA 比对）大量用；大模型时代退居幕后，但面试仍考。

记

小结

① Manacher O(n) 找最长回文，插 # 统一奇偶。② 后缀数组排所有后缀，LCP 求最长公共子串。③ BM 从右往左比，坏字符跳着搜，实战比 KMP 快。

3.16 数论算法：GCD / 素数筛 / 快速幂 / 模逆元

Number Theory · 密码学和哈希的数学底子

想四件套

① 欧几里得 GCD：gcd(a,b) = gcd(b, a mod b)，直到 b=0。求最大公约数，O(log min(a,b))。LCM = a·b / gcd(a,b)。RSA、分数约分、哈希桶大小都用它。

② 素数筛：埃氏筛 O(n log log n)——从 2 开始，把每个素数的倍数划掉。欧拉筛 O(n)——每个合数只被最小素因子划一次，避免重复。判 1e7 内素数必备。

③ 快速幂：算 aⁿ mod m。普通乘 O(n)，快速幂把 n 拆二进制：aⁿ = (a^n/2)²，遇奇数再乘一个 a。O(log n)。RSA 解密、Diffie-Hellman 全靠它。

④ 模逆元：求 x 使得 a·x ≡ 1 (mod m)。a 和 m 互素时存在，用扩展欧几里得 O(log m)。模运算下的"除法"就是乘逆元。

// 快速幂：a^n mod m（Python 风格伪代码）
def qpow(a, n, m):
    res = 1
    a = a % m
    while n > 0:
        if n & 1: res = res * a % m   # n 是奇数，乘一个 a
        a = a * a % m               # 平方
        n >>= 1                     # n 折半
    return res
# 例：qpow(2, 10, 1000) = 24；2^10=1024，模 1000 = 24

例：gcd(48, 18) = ?

辗转相除。

解：gcd(48,18) = gcd(18, 48 mod 18=12) = gcd(12, 18 mod 12=6) = gcd(6, 0) = 6。LCM = 48×18/6 = 144。只要几步就出答案，远快于枚举公因数。

密码学

RSA=大素数分解+快速幂+模逆元；Diffie-Hellman 密钥交换；区块链椭圆曲线签名。

工程里

哈希取模用素数桶；随机数生成；欧几里得约分；筛法做素数表。

防坑

坑：快速幂忘记每次取模。aⁿ 直接算会爆整数——每步都要 % m。另外埃氏筛会重复划（6 被 2 和 3 各划一次），大数据量换欧拉筛。模逆元只在 gcd(a,m)=1 时存在，别乱用。

练一练

基础快速幂算 3¹³ mod 7，比 13 次连乘快多少？

看答案

13 次 vs log₂13≈4 次乘法。13 的二进制 1101，3¹³ = (3⁸)(3⁴)(3¹)，平方三次+乘三次，共 O(log n) 步。

进阶为什么 RSA 安全靠的是大素数难分解，而不是快速幂？

看答案

快速幂 O(log n) 是"易"；但分解两个 2048 位大素数的乘积是"难"（没多项式算法）。公钥加密易、私钥破解难，这个不对称性就是密码学的根基。

自评反馈：答对了继续；快速幂每步取模、模逆元前提，哪条还绕就回看。

记

小结

① GCD 辗转相除 O(log n)。② 埃氏筛 O(n log log n)，欧拉筛 O(n)。③ 快速幂拆二进制 O(log n)，密码学基石。④ 模逆元=模下除法，需互素。

3.17 排序全家桶补全：堆 / 计数 / 桶 / 基数 + 稳定性

Heap / Counting / Bucket / Radix Sort · 3.2 没讲全的那几种

想引子与大白话

引子：3.2 讲了四种主力，但面试和实战还剩四种：要求 O(n log n) 最坏保证用堆排序；数据范围小用计数/桶/基数这些"非比较"排序能冲到 O(n)。

① 堆排序：先把数组建成大顶堆（O(n)），然后反复把堆顶最大值换到末尾、堆大小减一、下沉调整。最坏也是 O(n log n)，原地、不稳定。不递归、无最坏退化，是快排的备胎。

② 计数排序：数据是 0~k 的整数。开一个长度 k+1 的计数数组，统计每个数出现几次，再从小到大前缀铺开。O(n+k)，k 远小于 n 时线性。

③ 桶排序：把数据分到若干桶（如 0~1 的数按十分位分 10 个桶），桶内各自排序，再按桶序拼起来。数据均匀分布时接近 O(n)。

④ 基数排序：按低位→高位，每一位用计数排序排一遍（LSD）。排序身份证号、银行卡号这种定长串。O(d·(n+k))，d 是位数。

表 3-2 全部排序算法对比（含 3.2 的四种）
算法	平均	最坏	空间	稳定	场景
快排	O(n log n)	O(n²)	O(log n)	否	通用主力
归并	O(n log n)	O(n log n)	O(n)	是	要稳定
堆排	O(n log n)	O(n log n)	O(1)	否	无最坏退化
计数	O(n+k)	O(n+k)	O(k)	是	范围小的整数
桶排	O(n+k)	O(n²)	O(n)	视桶内	均匀分布
基数	O(d(n+k))	O(d(n+k))	O(n+k)	是	定长整数串

例：对 100 万学生的高考分数（0~750）排序，最快用哪种？

n=1e6，k=751。

解：计数排序 O(n+k) ≈ 100 万次，比 O(n log n)≈2000 万次快 20 倍。开一个长度 751 的数组，count[分]++，再顺序输出。非比较排序一旦 k 小，就是作弊般的快。

稳定性

稳定=相等元素相对顺序不变。排序多人多关键字（先按成绩、再按姓名）时，第二步要用稳定排序才保留第一步结果。归并/插入/计数/基数稳；快排/堆排不稳。

选型口诀

通用快排；要稳定归并；整数范围小计数；定长串基数；怕最坏退化堆排。Python Timsort=归并+插入混合。

记

小结

① 堆排最坏 O(n log n) 原地。② 计数/桶/基数是非比较排序，数据范围小时 O(n)。③ 稳定性=相等元素相对序不变，多关键字排序关键。