算法观澜

算法 = 有限、确定、可行的指令序列，且必须终止。正确性是第一公民：对一切合法输入给出正确输出——大数溢出截断的"闪电法"再快也不是算法。时间与空间是第二、三把尺，二者常可互换：哈希表以空间换时间，归并排序用 O(n) 额外空间买 O(n log n) 的确定性——"时空权衡"是贯穿全部算法设计的母题。唯有正确性不可交易。衡量一个算法，永远三把尺一起拿出来。（CLRS Ch1）

形式定义：O(g) = { f(n) : ∃c,n₀>0，n≥n₀ 时 0 ≤ f(n) ≤ c·g(n) }——渐近上界；Ω(g) 把不等号反向——渐近下界；Θ(g) = O(g) ∩ Ω(g)——紧界。运算性质：常数因子与低阶项被吸收（100n²+n = Θ(n²)），且有对偶律 f=O(g) ⇔ g=Ω(f)。注意"f=O(g)"的等号是惯例滥用，应读作"f 属于 O(g)"——渐近记号描述的是函数集合的归属关系，不是等式。排序九函数的那把尺（1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!）值得背到条件反射。（CLRS Ch3）

同一个算法，复杂度是输入的函数：最坏情形给出"保证"（工程承诺的锚点），平均情形给出"期望"（必须声明输入分布假设），最好情形几乎没有工程意义。快排是最好的教材：已排序输入 + 固定 pivot 退化为 O(n²)，随机输入期望 O(n log n)。随机化 pivot 的深意：把"倒霉的输入"转化为"倒霉的随机数"——期望复杂度从此与输入分布无关，敌人无法再针对性投喂最坏数据。分析空间复杂度同理（递归深度即栈空间，快排最坏 O(n) 栈）。（CLRS Ch3 / Ch7）

分治递推 T(n) = aT(n/b) + f(n)：a 个子问题、规模 n/b、合并代价 f(n)。三种解法各有分工：代入法先猜后用数学归纳法验证（本章陷阱递推取 c≥2 证明闭合）；递归树逐层求和，几何级数的走向直接暴露主导项；Master 定理比较 f(n) 与分水岭 n^(log_b a)：f 小→叶主导 Θ(n^(log_b a))，相等→每层均摊 Θ(n^(log_b a)·log n)，f 大→根主导 Θ(f(n))（Case 3 还需正则条件 a·f(n/b) ≤ c·f(n)）。Strassen 矩阵乘把 a 从 8 压到 7，Θ(n^2.807) 就此打败朴素 n³——分治的艺术全在"怎么切、怎么合"。（CLRS Ch4）

排序谱系的取舍矩阵：插入/冒泡 O(n²) 但简单稳定；归并 O(n log n) 稳定、可外排，代价是 O(n) 空间；快排期望 O(n log n) 原地但不稳定；堆排 O(n log n) 原地但不稳定。比较排序下界：任何基于比较的排序对应一棵判定树，n! 种输入排列必须各占一片叶子 ⇒ 树高 ≥ log₂(n!)，Stirling 展开得 Θ(n log n)——这是信息论下界，与聪明无关。要更快只有跳出"两两比较"模型：计数排序、基数排序、桶排序利用键值的额外结构可达 O(n)，但它们不是通用排序。（CLRS Ch6–8）

哈希表把"比较"换成"计算地址"，期望 O(1)。冲突处理两大路线：链地址法（每格挂链表，平均查找 O(1+α)，α=n/m 为装载因子）与开放寻址（线性/二次/双重哈希探查，期望探查数 ≈ 1/(1−α)，α 必须 < 1）。平均 O(1) 的前提是全域哈希的均匀性假设——对手若能构造同哈希键（哈希洪水攻击），查找退化为 O(n)，这正是真实世界 DoS 的手段。摊还分析：表倍增下插入均摊 O(1)，因为 rehash 总代价是几何级数 m+2m+…+n < 2n；三种分析工具——聚合分析、记账法、势能法——是 CLRS Ch17 的三件套。（CLRS Ch11 / Ch17）

贪心成立需要两根支柱同时立住：①最优子结构（最优解包含子问题最优解）②贪心选择性质（存在包含贪心选择的最优解——局部最优"安全"）。活动选择（选最早结束，CLRS 16.1 原例 11 活动最优 4 个）与 Huffman 编码（合并最低频，可证前缀码最优）都满足②；0-1 背包满足①不满足②——选了重 6 值 12 就堵死两件重 5 值 10 的组合（12 vs 20）；而分数背包（可切割）却满足②，贪心反而正确。验证贪心的标准武器是交换论证（exchange argument）：证明任一最优解都能"换"进贪心选择而不变差——证明缺位时，贪心只是启发式。（CLRS Ch16）

DP 的两大适用条件：最优子结构（最优解由子问题最优解组装）+重叠子问题（子问题被反复求解，值得记忆）。实现两路线：自顶向下备忘录（递归+缓存）与自底向上填表（按拓扑序迭代）。0-1 背包递推 OPT(i,w) = max{ OPT(i-1,w), OPT(i-1,w-wᵢ)+vᵢ } 填出最优 20，复杂度 O(nW) 是伪多项式——W 按输入位长算是指数级。TSP 的 Held-Karp DP 状态为（已访问子集, 当前城市），2ⁿ·n 个状态：子问题确实重叠，但状态空间本身指数膨胀，记忆也救不了。DP 的能力边界 = 子问题 DAG 的规模。（CLRS Ch15）

BFS 与 DFS 同为 O(V+E)，是图算法的两大母结构。BFS（队列，按层推进）：天然给出无权图最短路径，还可做二分图判定、层序分析。DFS（栈/递归，深入回溯）：拓扑排序、连通/强连通分量、环检测的基石——发现时间 d 与完成时间 f 构成括号化区间（括号化定理），边的分类（树边/回边/前向边/横边）全部由此读出。选 BFS 还是 DFS，取决于你要"最近的答案"还是"最深的结构"。（CLRS Ch22）

Dijkstra：贪心 extract-min + 边松弛，堆实现 O((V+E) log V)。正确性论证的关键一步是"节点出队即封盘"——这依赖非负权假设；负权边可以让已封盘的距离变得更小，论证当场击穿，这正是注入负权边后 Dijkstra 给错答案的原因。Bellman-Ford：放弃贪心，对全部边做 V-1 轮松弛，O(VE) 换负权容忍；第 V 轮仍能松弛 ⇒ 存在负权环（本章"检测负权环"按钮即此原理）。选型口诀：非负单源 Dijkstra，负权单源 Bellman-Ford，全源 Floyd-Warshall O(V³)，稀疏图全源 Johnson。（CLRS Ch24）

P = 多项式时间可解；NP = 多项式时间可验证（给证书能核验）；NP 完全 = NP 中"最难"的一批——Cook-Levin 定理证明 SAT 是第一个 NP 完全问题，此后一切 NP 完全结论都靠多项式归约接力（SAT → 3-SAT → 团 → 顶点覆盖 → TSP…）。P=NP？千禧年难题，悬而未决——但多数研究者押 P≠NP。不可计算是更深的墙：停机问题不可判定，对角化构造 D(D) 让任何候选判定器 H 自指矛盾（Turing 1936），且由 Rice 定理，程序的任何非平凡语义性质都不可判定。三层边界收束本章：效率边界 Ω(n log n)（定理砌的）→ 复杂性边界 NP 完全（可能砌的）→ 可计算性边界停机（必然砌的）。下一章 ch06 硅基咒语：从算法的抽象世界回到机器——用硬件描述语言把逻辑钉进硅片。（CLRS Ch34 / Sipser Ch4/7）