算法设计

两个 $n$ 位数相乘，小学竖式要做 $n^{2}$ 次个位乘法。几千年来所有人都默认这就是乘法的代价，直到 1960 年 Kolmogorov 在研讨会上提出这个猜想，一周后 23 岁的学生 Karatsuba 就找到了更快的方法。好算法很少来自灵光一现，更多来自几种反复出现的套路：分治、随机化、贪心、动态规划，以及把问题看成图。下面按这几种套路依次走一遍。

前置：数据结构；渐近记号与递推见离散数学。

先学会数：复杂度分析

比较算法之前，要有一把尺子。我们数基本操作次数随输入规模 $n$ 的增长，用 $O$ 、 $Θ$ 记号忽略常数（定义见离散数学）。三个约定：

默认分析最坏情况：它给出对所有输入都成立的保证，不依赖对输入分布的猜测。
平均情况需要假设输入分布；期望复杂度则是算法自己掷硬币，对任何输入都成立（下面的快排）。
均摊是对一串操作的总代价求平均，动态数组的 append 就是例子（见数据结构）。

为什么要在乎增长速度而不是常数？因为规模一大，增长速度压倒一切。在 Python 里每秒大约能做 $1 0^{7}$ 次简单操作， $n = 1 0^{6}$ 时 $O (n lo g n)$ 是两秒， $O (n^{2})$ 是一天。

分治：拆开、递归、合并

分治的模板是：把问题拆成几个同类的小问题，递归解决，再合并答案。

归并排序是最干净的例子：拆成两半，分别排序，再用两个指针把两个有序数组合并，合并是 $O (n)$ 。运行时间满足

$T (n) = 2 T (n /2) + O (n)$

画递归树：第 $j$ 层有 $2^{j}$ 个子问题，每个大小 $n / 2^{j}$ ，这一层的合并总共 $O (n)$ ；一共 $lo g_{2} n$ 层，所以 $T (n) = O (n lo g n)$ 。

回到乘法。把两个 $n$ 位数各拆成高低两半， $x = a \cdot 1 0^{n /2} + b$ ， $y = c \cdot 1 0^{n /2} + d$ ，则

$x y = a c \cdot 1 0^{n} + (a d + b c) \cdot 1 0^{n /2} + b d$

直接做需要 4 个 $n /2$ 位乘法， $T (n) = 4 T (n /2) + O (n) = O (n^{2})$ ，没有进步。Karatsuba 的观察是 $a d + b c = (a + b) (c + d) - a c - b d$ ，所以只需要 3 次乘法：

$T (n) = 3 T (n /2) + O (n) = O (n^{l o g_{2} 3}) \approx O (n^{1.585})$

def karatsuba(x, y, counter):
    if x < 10 or y < 10:
        counter[0] += 1; return x * y
    m = max(len(str(x)), len(str(y))) // 2
    a, b = divmod(x, 10**m); c, d = divmod(y, 10**m)
    ac = karatsuba(a, c, counter); bd = karatsuba(b, d, counter)
    # 一次乘法换掉两次：(a+b)(c+d) - ac - bd = ad + bc
    mid = karatsuba(a + b, c + d, counter) - ac - bd
    return ac * 10**(2 * m) + mid * 10**m + bd
 
import random
random.seed(0)
for n in [8, 32, 128, 512]:
    x, y = random.randrange(10**(n-1), 10**n), random.randrange(10**(n-1), 10**n)
    cnt = [0]
    assert karatsuba(x, y, cnt) == x * y
    print(f"n={n:4d}  个位乘法次数={cnt[0]:7d}  竖式 n^2={n*n:7d}")

输出：

n=   8  个位乘法次数=     41  竖式 n^2=     64
n=  32  个位乘法次数=    361  竖式 n^2=   1024
n= 128  个位乘法次数=   3097  竖式 n^2=  16384
n= 512  个位乘法次数=  28675  竖式 n^2= 262144

$n$ 每翻 4 倍，竖式的次数翻 16 倍，Karatsuba 只翻约 9 倍（ $4^{1.585} \approx 9$ ）。同样的想法用在矩阵上就是 Strassen 算法： $2 \times 2$ 分块矩阵乘法用 7 次而不是 8 次子乘法，得到 $O (n^{2.81})$ 。

这类递推有一个统一的读法，主定理：对 $T (n) = a T (n / b) + O (n^{d})$ ，比较 $a$ 和 $b^{d}$ 。

情况	结果	含义
$a < b^{d}$	$O (n^{d})$	根部的合并工作占主导
$a = b^{d}$	$O (n^{d} lo g n)$	每层工作量相同，乘以层数
$a > b^{d}$	$O (n^{l o g_{b} a})$	叶子的数量占主导

直觉是：每往下一层，子问题数量乘 $a$ （工作量变多），每个子问题的工作量除以 $b^{d}$ （变少），谁赢决定了总量集中在树的哪一端。归并排序 $a = 2, b = 2, d = 1$ ，属于第二种；Karatsuba $a = 3, b = 2, d = 1$ ，属于第三种；二分查找 $a = 1, b = 2, d = 0$ ，第二种， $O (lo g n)$ 。

停一下，检查理解单选

某分治算法把问题拆成 4 个规模为 n/2 的子问题，合并代价是 O(n^2)。它的运行时间是？

O(n^2)O(n^2 log n)O(n^4)O(n log n)

排序的下界：有些事做不到更快

归并排序是 $O (n lo g n)$ 。能不能更快？对基于比较的排序，答案是不能，而且可以证明。

任何比较排序都可以画成一棵决策树：每个内部节点是一次比较 ” $a_{i} < a_{j}$ ?”，根据结果走向左或右，叶子是最终输出的排列。 $n$ 个元素有 $n!$ 种排列，每种都必须出现在某个叶子上，否则算法会对某个输入输出错误。高度为 $h$ 的二叉树最多 $2^{h}$ 个叶子，所以

$h \geq lo g_{2} (n!) = Θ (n lo g n)$

最坏情况下的比较次数就是树高。任何比较排序在最坏情况下都需要 $Ω (n lo g n)$ 次比较，这是关于问题本身而不是某个算法的结论。

下界只约束”只能比较”的算法。如果键是范围不大的整数，计数排序数一数每个值出现几次就能 $O (n + k)$ 排序；基数排序按位做多轮计数排序。它们绕过了下界，因为它们用键的值做数组下标，获得的信息不止一次比较的一比特。

import math, random
from functools import cmp_to_key
def count_comparisons(arr):
    cnt = [0]
    def cmp(a, b):
        cnt[0] += 1; return (a > b) - (a < b)
    sorted(arr, key=cmp_to_key(cmp))  # CPython 的 Timsort
    return cnt[0]
 
random.seed(0)
for n in [10, 100, 1000, 10000]:
    arr = random.sample(range(n * 10), n)
    lb = math.lgamma(n + 1) / math.log(2)  # log2(n!)
    print(f"n={n:5d}  Timsort 比较次数={count_comparisons(arr):7d}  下界 log2(n!)={lb:9.0f}")
print("已排序输入 n=10000:", count_comparisons(list(range(10000))))

输出：

n=   10  Timsort 比较次数=     25  下界 log2(n!)=       22
n=  100  Timsort 比较次数=    529  下界 log2(n!)=      525
n= 1000  Timsort 比较次数=   8617  下界 log2(n!)=     8529
n=10000  Timsort 比较次数= 119749  下界 log2(n!)=   118458
已排序输入 n=10000: 9999

Timsort 在随机输入上的比较次数只比信息论下界多约 1%。最后一行说明下界是最坏情况的：Timsort 会识别已经有序的片段，对排好序的输入只需 $n - 1$ 次比较。

随机化：让坏输入不存在

快速排序的思路和归并排序互补：先选一个枢轴（pivot），把比它小的放左边、大的放右边（这一步 $O (n)$ ），再递归排两边，不需要合并。如果枢轴每次都恰好是中位数， $T (n) = 2 T (n /2) + O (n) = O (n lo g n)$ ；如果每次都是最小值（比如对已排序数组总选第一个元素）， $T (n) = T (n - 1) + O (n) = O (n^{2})$ 。

固定的枢轴规则总会被某种输入打败。解决办法是随机选择枢轴。这时不存在”坏输入”，只存在”坏运气”，而坏运气的概率极小。期望比较次数可以用指示变量算出来：排序后第 $i$ 小和第 $j$ 小的元素被比较，当且仅当它们之间的 $j - i + 1$ 个元素里，第一个被选为枢轴的是它俩之一，概率 $\frac{2}{j - i + 1}$ 。用期望的线性性（见概率论）对所有对求和：

$E [比较次数] = \sum_{i < j} \frac{2}{j - i + 1} \leq 2 n \sum_{k = 2}^{n} \frac{1}{k} \approx 2 n ln n \approx 1.39 n lo g_{2} n$

import random, sys
sys.setrecursionlimit(20000)
def quicksort(a, choose, cnt):
    if len(a) <= 1: return a
    p = choose(a)
    cnt[0] += len(a) - 1  # 划分时其余每个元素都和枢轴比一次
    return (quicksort([x for x in a if x < p], choose, cnt) + [p] +
            quicksort([x for x in a if x > p], choose, cnt))
 
n = 3000
for name, choose in [("取第一个", lambda a: a[0]), ("随机", random.choice)]:
    for label, data in [("随机输入", random.sample(range(n), n)), ("已排序输入", list(range(n)))]:
        random.seed(1); cnt = [0]
        quicksort(data, choose, cnt)
        print(f"{name:4s} {label:5s} 比较次数={cnt[0]:8d}")
import math; print("2 n ln n ≈", round(2 * n * math.log(n)))

输出：

取第一个 随机输入  比较次数=   37551
取第一个 已排序输入 比较次数= 4498500
随机   随机输入  比较次数=   37511
随机   已排序输入 比较次数=   38914
2 n ln n ≈ 48038

取第一个元素做枢轴时，已排序输入让比较次数暴涨到约 $n^{2} /2$ ；随机枢轴对两种输入表现一样，都在 3.8 万左右。它比 $2 n ln n \approx 4.8$ 万略低，因为 $2 n ln n$ 只是上界估计，精确的期望约为 $2 n ln n - 2.85 n$ 。

同样的划分思想解决选择问题：找第 $k$ 小的元素不需要排序。划分后只递归进 $k$ 所在的那一边，期望 $T (n) = T (n /2) + O (n) = O (n)$ （快速选择）。还有一个确定性的 $O (n)$ 算法（中位数的中位数），选枢轴时先把元素五个一组取中位数，再递归取这些中位数的中位数，保证枢轴足够居中，理论上漂亮，实践中常数较大。

停一下，检查理解多选

关于随机化快速排序，哪些说法正确？

对任何固定的输入，期望运行时间都是 O(n log n)它的最坏情况运行时间是 O(n log n)期望是对算法内部的随机选择取的，不需要假设输入随机输入已经排好序时，它会退化到 O(n^2)

图算法：把问题变成图

大量问题一旦建模成图，就能套用现成的算法。图的表示（邻接表）见数据结构，下面的复杂度都基于邻接表。

BFS（广度优先搜索）从起点一层一层往外扩，用队列实现， $O (V + E)$ 。它天然给出无权图的最短路径：第一次到达某个顶点时经过的边数就是最短距离。DFS（深度优先搜索）一条路走到底再回溯，用栈或递归实现，也是 $O (V + E)$ 。DFS 的价值在于它记录的完成时间：在有向无环图上，按完成时间倒序排列就是一个拓扑序，这是调度有依赖关系的任务的标准做法（构建系统、反向传播的计算图）。在 DFS 的基础上再做一次反向图上的 DFS，还能在线性时间内找出强连通分量（Kosaraju 算法）。

带权最短路。边有长度时，BFS 不再正确，因为边数少的路不一定短。Dijkstra 算法的想法是：维护每个顶点的当前最短距离估计，每次从未确定的顶点里取出估计最小的那个，宣布它已确定，再用它去更新邻居（松弛）。为什么取出时就能确定？因为边权非负，任何经过其他未确定顶点的路径都不会更短。用二叉堆实现， $O ((V + E) lo g V)$ 。

import heapq
def dijkstra(adj, s):
    dist = {s: 0}; pq = [(0, s)]; done = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in done: continue  # 同一顶点可能多次入堆，只认第一次弹出
        done.add(u)
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w; heapq.heappush(pq, (d + w, v))
    return dist
 
adj = {"A": [("B", 4), ("C", 1)], "C": [("B", 2), ("D", 5)],
       "B": [("D", 1)], "D": []}
print(dijkstra(adj, "A"))

输出：

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

A 到 B 直接走是 4，绕道 C 是 3；到 D 的最短路 A→C→B→D 是 4。

Dijkstra 依赖”边权非负”。有负权边时（比如汇率套利问题，取对数后变成负权），要用 Bellman-Ford：对所有边重复松弛 $V - 1$ 轮， $O (V E)$ 。为什么 $V - 1$ 轮够？因为最短路最多有 $V - 1$ 条边，第 $i$ 轮之后，所有”最多 $i$ 条边”的最短路都已正确。如果第 $V$ 轮还能松弛，说明存在负环，最短路无定义。这个”按边数逐轮推进”的结构，其实已经是动态规划了。

最小生成树（MST）：用最小总权重的边把所有顶点连起来。两个贪心算法都正确：Prim 从一个顶点出发，每次加入连接”已选部分”和”未选部分”的最便宜的边（用堆）；Kruskal 把所有边从小到大排序，依次加入，跳过会形成环的边（用并查集判断）。两者都是 $O (E lo g V)$ 。它们正确的共同原因是割性质：对任何把顶点分成两部分的切割，跨越切割的最便宜的边一定属于某棵 MST。

停一下，检查理解单选

一张有向图里有负权边但没有负环。用 Dijkstra 求单源最短路会怎样？

一定正确，因为没有负环最短路就有定义可能出错，因为一个顶点被"确定"后，之后可能经由负权边找到更短的路一定死循环一定正确，只是变慢

动态规划：记住子问题的答案

有些问题能拆成子问题，但子问题之间大量重叠。斐波那契的朴素递归 fib(n) = fib(n-1) + fib(n-2) 会把 fib(n-2) 算两遍、fib(n-3) 算三遍……，总次数指数增长。把每个子问题的答案存起来，每个只算一次，就是动态规划（DP）。记忆化递归和自底向上填表是同一件事的两种写法（记忆化见高阶函数与递归）。

DP 的难点不在写代码，而在定义子问题。CS161 的套路是问三个问题：

最优解的最后一步是什么？
去掉最后一步，剩下的是不是一个同类的更小问题（最优子结构）？
一共有多少个不同的子问题，每个要花多少时间合并？复杂度 = 子问题数 × 每个的代价。

0/1 背包： $n$ 件物品，各有重量 $w_{i}$ 和价值 $v_{i}$ ，背包容量 $W$ ，选哪些使总价值最大？问最后一件物品 $i$ 放不放：不放，就是”前 $i - 1$ 件、容量 $W$ “的子问题；放，就是”前 $i - 1$ 件、容量 $W - w_{i}$ “再加 $v_{i}$ 。

$K (i, c) = max (K (i - 1, c), K (i - 1, c - w_{i}) + v_{i})$

子问题 $(n + 1) (W + 1)$ 个，每个 $O (1)$ ，总共 $O (nW)$ 。

from itertools import combinations
w = [2, 3, 4, 5]; v = [3, 4, 5, 6]; W = 5
n = len(w)
K = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for c in range(W + 1):
        K[i][c] = K[i - 1][c]
        if w[i - 1] <= c:
            K[i][c] = max(K[i][c], K[i - 1][c - w[i - 1]] + v[i - 1])
for row in K: print(row)
# 暴力枚举所有子集交叉验证
best = max(sum(v[i] for i in s) for r in range(n + 1) for s in combinations(range(n), r)
           if sum(w[i] for i in s) <= W)
print("DP:", K[n][W], " 暴力:", best)

输出：

[0, 0, 0, 0, 0, 0]
[0, 0, 3, 3, 3, 3]
[0, 0, 3, 4, 4, 7]
[0, 0, 3, 4, 5, 7]
[0, 0, 3, 4, 5, 7]
DP: 7  暴力: 7

最优是选重量 2 和 3 的两件，价值 7。注意 $O (nW)$ 看起来是多项式，但 $W$ 是一个数值，写下它只需要 $lo g W$ 位，所以这是伪多项式时间。背包问题是 NP 完全的，这并不矛盾。

编辑距离是另一个经典：把字符串 $s$ 变成 $t$ 最少需要几次插入、删除、替换？看两串的最后一个字符：如果相同，问题化为两串各去掉末字符；否则三种操作各对应一个更小的子问题，取最小加 1。 $O (mn)$ 个子问题，这是 diff、拼写纠错、DNA 比对的基础。前面的 Bellman-Ford 也是 DP，子问题是”最多用 $i$ 条边到达 $v$ 的最短距离”。

停一下，检查理解单选

对长度为 m 和 n 的两个字符串求编辑距离，标准 DP 的时间复杂度是？

O(m + n)，因为每个字符只看一次O(mn)，因为子问题是两串所有前缀的组合，每个 O(1)O(2^(m+n))，因为每一步都有三种选择O((m + n) log(m + n))

贪心：每一步都选眼前最好的

DP 要考虑最后一步的所有选择。如果能证明某个局部最优的选择一定能扩展成全局最优，就不用比较了，直接选它，这就是贪心。它通常更快更简单，但正确性必须证明，直觉经常出错。

活动选择：一堆活动各有开始和结束时间，一个会议室，最多能安排多少个不冲突的活动？候选贪心规则有好几种：最短的优先、最早开始的优先、冲突最少的优先，它们都有反例。正确的是最早结束的优先。证明用交换论证：取任意一个最优解，把其中最早结束的活动换成全局最早结束的那个，不会和后面的活动冲突（它结束得更早），活动数不变，所以存在一个包含贪心选择的最优解；然后对剩下的问题归纳。

from itertools import combinations
def greedy(acts, key):
    chosen = []
    for a in sorted(acts, key=key):
        # 和已选的每个活动都不重叠才收下
        if all(a[1] <= b[0] or b[1] <= a[0] for b in chosen): chosen.append(a)
    return chosen
def optimum(acts):
    ok = lambda sub: all(x[1] <= y[0] for x, y in zip(sorted(sub), sorted(sub)[1:]))
    return max(r for r in range(len(acts) + 1) for sub in combinations(acts, r) if ok(sub))
 
rules = {"最早结束": lambda a: a[1], "最短": lambda a: a[1] - a[0], "最早开始": lambda a: a[0]}
cases = {"短活动横跨两个长活动": [(0, 5), (4, 7), (6, 11)],
         "长活动最早开始": [(0, 10), (1, 2), (3, 4), (5, 6)]}
for name, acts in cases.items():
    res = {r: len(greedy(acts, k)) for r, k in rules.items()}
    print(name, res, "最优:", optimum(acts))

输出：

短活动横跨两个长活动 {'最早结束': 2, '最短': 1, '最早开始': 2} 最优: 2
长活动最早开始 {'最早结束': 3, '最短': 3, '最早开始': 1} 最优: 3

第一组里”最短优先”选中中间的短活动，一下挡掉两边；第二组里”最早开始优先”被一个早开始的长活动拖累。只有最早结束优先在两组都拿到最优。

再比如找零：用面值 25、10、5、1 的硬币凑出某个金额，每次拿不超过余额的最大面值，结果总是最少枚数。但换成面值 1、3、4 凑 6，贪心拿 4+1+1 是三枚，最优是 3+3 两枚。贪心对的时候是因为问题结构特殊，前面的 MST（割性质）、Dijkstra（非负权）、Huffman 编码都有各自的交换论证。拿不准时，用 DP 或者用暴力在小输入上对拍。

停一下，检查理解单选

硬币面值为 1、3、4，要凑出 6 且枚数最少。下面哪个说法正确？

每次拿最大面值的贪心得到最优解 2 枚贪心得到 3 枚（4+1+1），最优是 2 枚（3+3），应该用 DP这个问题没有最优子结构，DP 也不适用贪心和 DP 都得到 3 枚

当找不到快算法：NP 完全

学完这些套路，会遇到一些问题怎么都套不上：旅行商（访问所有城市的最短回路）、图着色、布尔可满足性 SAT、背包（以输入位数衡量）。它们有一个共同点：给出一个解，验证它很容易；但找到一个解，没有人知道多项式算法。

P 是能在多项式时间内求解的问题，NP 是解能在多项式时间内验证的问题。归约是这里的核心工具：如果问题 A 能在多项式时间内转化为问题 B，那么 B 至少和 A 一样难。NP 完全问题是 NP 中最难的一批，任何 NP 问题都能归约到它们。所以只要其中一个有多项式算法，所有 NP 问题都有，即 P = NP。这是计算机科学最著名的未解问题，普遍相信 P ≠ NP。

识别出一个问题是 NP 完全的，并不意味着放弃，而是换一个目标：规模小就用指数算法加剪枝；接受近似解（MST 能给出度量 TSP 的 2 倍近似）；用启发式与求解器（现代 SAT 求解器能处理数百万变量的工业实例）；或者利用实际输入的特殊结构（背包的 $W$ 不大时，伪多项式 DP 完全够用）。

记住这三件事

分治的代价由递归树决定，主定理比较”子问题增多”和”每个变小”谁更快；比较排序有 $Ω (n lo g n)$ 的下界。
随机化让坏输入消失，期望用线性性分析；图问题先选对模型：BFS 求无权最短路，Dijkstra 要非负权，MST 靠割性质。
子问题重叠就用 DP，复杂度 = 子问题数 × 每个的代价；贪心必须有交换论证，否则用 DP 或对拍检查。

CS 与 LLM 学习知识库

探索

算法设计

先学会数：复杂度分析

分治：拆开、递归、合并

排序的下界：有些事做不到更快

随机化：让坏输入不存在

图算法：把问题变成图

动态规划：记住子问题的答案

贪心：每一步都选眼前最好的

当找不到快算法：NP 完全

记住这三件事

延伸阅读

目录

反向链接