# 附录 a 公式速查表


> 本附录按篇章索引全书的核心公式与结论。每条给出**成立条件**——这是最重要的一列，因为考试干扰项几乎都建立在"条件被悄悄改变"之上。

---

## A.1 线性代数

### A.1.1 矩阵运算

| 公式 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `(AB)C = A(BC)` | 恒成立 | 结合律，唯一可以放心用的运算律 | 1.1 |
| `A(B + C) = AB + AC` | 恒成立 | 分配律 | 1.1 |
| `AB ≠ BA` | 一般不成立 | 顺序敏感；由此 `(A+B)² ≠ A² + 2AB + B²` | 1.1 |
| `(AB)ᵀ = BᵀAᵀ` | 恒成立 | 转置必须**反序** | 1.1 |
| `(A + B)² = A² + AB + BA + B²` | 恒成立 | 中间两项在不可交换时消不掉 | 1.1 |
| `tr(AB) = tr(BA)` | 形状相容时 | 迹的轮换性 | 3.1 |
| `det(AB) = det(A)det(B)` | A、B 同阶 | 行列式的乘性 | 3.1 |

### A.1.2 秩、子空间与可逆性

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `r(A) = r(Aᵀ)` | 恒成立 | 行秩 = 列秩 | 1.4 |
| `dim N(A) + r(A) = n` | `A ∈ R^(m×n)`，**n 为列数** | 秩-零化度定理；求零空间维数 | 1.5 |
| `dim Col(A) + dim N(Aᵀ) = m` | `A ∈ R^(m×n)` | 行空间的补 | 1.4 |
| `N(A) ⊥ Col(Aᵀ)`、`N(Aᵀ) ⊥ Col(A)` | 恒成立 | 四个基本子空间的正交补关系 | 1.4 |
| `r(A) ≤ min(m, n)` | 恒成立 | 秩的上界；增大行数不一定增秩 | 1.5 |
| A 可逆 ⟺ 方阵且 `r(A) = n` ⟺ `det(A) ≠ 0` ⟺ 列向量线性无关 ⟺ `Ax = 0` 只有零解 | A 为 n 阶方阵 | 可逆性判断 | 1.6 |
| `dim N(A) = n − r(A)` | 同上 | **用列数减，不是行数** | 1.5 |

### A.1.3 内积、范数与相似度

| 公式 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `xᵀy = Σ_i x_i y_i` | 同维向量 | 内积定义 | 2.1 |
| `(xᵀy)² ≤ ‖x‖²‖y‖²` | 恒成立 | 柯西-施瓦茨不等式 | 2.1 |
| `‖x‖₂ = √(xᵀx)` | 恒成立 | L2 范数 | 2.2 |
| `‖x‖₁ = Σ_i \|x_i\|` | 恒成立 | 曼哈顿距离 / L1 | 2.2 |
| `cosθ = xᵀy / (‖x‖‖y‖)` | 非零向量 | 余弦相似度 | 2.2 |
| `‖u − v‖² = ‖u‖² + ‖v‖² − 2uᵀv` | 恒成立 | 距离与内积的桥梁 | 2.2 |
| **`‖u − v‖² = 2 − 2cosθ`** | **u、v 均为单位向量** | 距离↔余弦换算；向量检索等价性 | 2.2 |
| `‖x‖ ≤ ‖x‖₁ ≤ √n‖x‖` | n 维 | 范数等价性 | 2.2 |
| `d_M(x,y) = √((x−y)ᵀΣ⁻¹(x−y))` | Σ 正定 | 马氏距离 | 2.2 |
| `J(A,B) = \|A∩B\| / \|A∪B\|` | 集合 | Jaccard 相似度 | 2.2 |

### A.1.4 投影与正交化

| 公式 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `P = A(AᵀA)⁻¹Aᵀ` | A 列满秩 | 到 `Col(A)` 的正交投影矩阵 | 2.3 |
| `P² = P`、`Pᵀ = P` | 同上 | 投影矩阵的幂等与对称性 | 2.3 |
| `w = (AᵀA)⁻¹Aᵀy` | 列满秩 | 最小二乘正规方程 | 2.3 |
| `H = I − 2vvᵀ` | `‖v‖ = 1` | Householder 反射 | 2.4 |
| `Hᵀ = H`、`H² = I`、`det(H) = −1` | 同上 | 对称、正交、自逆、行列式为 −1 | 2.4 |

### A.1.5 特征分解与 SVD

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `Av = λv` | 方阵 | 特征方程定义 | 3.1 |
| `Σλ_i = tr(A)`、`Πλ_i = det(A)` | 方阵 | 快速校验特征值 | 3.1 |
| `A = QΛQᵀ` | A 实对称 | 谱定理：正交对角化 | 3.2 |
| `xᵀAx > 0, ∀x ≠ 0` | A 对称 | 正定判据（等价于全部特征值 > 0） | 3.3 |
| `A = UΣVᵀ` | 任意实矩阵 | 奇异值分解 | 3.4 |
| `σ_i = √λ_i(AᵀA)` | 恒成立 | 奇异值与特征值的关系 | 3.4 |
| `A_k = Σ_{i=1}^{k} σ_i u_i v_iᵀ` | 取前 k 大奇异值 | 最优秩-k 近似（Eckart-Young） | 3.5 |
| 存储量 `r(m + n + 1)` vs 原 `mn` | 截断秩 r | SVD 压缩率计算 | 3.5 |
| 压缩后占比 `= r(m+n+1)/(mn)` | 同上 | 例题：1000×800、r=50 → 减少 88.74% | 3.5 |
| `Σ = (1/(n−1))(A−Ā)ᵀ(A−Ā)`，形状 `d×d` | `A ∈ R^(n×d)` | 协方差矩阵维度由**特征数 d** 决定 | 3.6 |

---

## A.2 概率、统计与信息论

| 公式 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `P(A\|B) = P(A∩B) / P(B)` | `P(B) > 0` | 条件概率 | 4.1 |
| `P(D) = Σ_i P(D\|B_i)P(B_i)` | `{B_i}` 为完备事件组 | 全概率公式 | 4.2 |
| `P(B\|D) = P(D\|B)P(B) / P(D)` | `P(D) > 0` | 贝叶斯公式 | 4.2 |
| `E[X] = Σ x_i p_i` 或 `∫ x f(x)dx` | — | 期望 | 4.4 |
| `Var(X) = E[X²] − (E[X])²` | 恒成立 | 方差快捷公式（注意数值不稳定，见 5.3） | 4.4 |
| `Var(aX + b) = a²Var(X)` | 恒成立 | **平移不改变方差**（位置量 vs 离散量的判据） | 4.6 |
| `E[X + Y] = E[X] + E[Y]` | 恒成立 | 期望的线性性（不要求独立） | 4.4 |
| `Var(X + Y) = Var(X) + Var(Y) + 2Cov(X,Y)` | 恒成立 | 独立时协方差为 0 | 4.4 |
| `E[X] = E[E[X\|Y]]` | 恒成立 | 全期望公式 | 4.4 |
| `Var(X) = E[Var(X\|Y)] + Var(E[X\|Y])` | 恒成立 | 全方差公式 | 4.4 |
| `P(X ≥ a) ≤ E[X]/a` | `X ≥ 0` | 马尔可夫不等式 | 4.4 |
| `P(\|X−μ\| ≥ kσ) ≤ 1/k²` | 有限方差 | 切比雪夫不等式 | 4.4 |
| `E[φ(X)] ≥ φ(E[X])` | φ 凸 | 詹森不等式 | 4.4 |
| `X̄ → μ` (a.s.) | i.i.d.、有限期望 | 大数定律 | 4.5 |
| `√n(X̄ − μ)/σ → N(0,1)` | i.i.d.、有限方差 | 中心极限定理 | 4.5 |
| `θ̂_MLE = argmax_θ P(X\|θ) = argmax_θ ℓ(θ)` | — | 最大似然估计 | 4.7 |
| `θ̂_MAP = argmax_θ P(X\|θ)P(θ)` | 需先验 | 最大后验（向先验收缩） | 4.7 |
| 伯努利 MLE `p̂ = k/n` | n 次试验 k 次成功 | 样本频率 | 4.7 |
| `H(X) = −Σ p log p` | — | 信息熵 | 4.8 |
| `H(p,q) = −Σ p log q` | — | 交叉熵 | 4.8 |
| `KL(p‖q) = Σ p log(p/q) ≥ 0` | 恒成立，**不对称** | KL 散度（吉布斯不等式） | 4.8 |
| `H(p,q) = H(p) + KL(p‖q)` | 恒成立 | 交叉熵 = 熵 + KL | 4.8 |
| **最小化交叉熵 ⟺ 最小化 KL ⟺ 最大化似然** | 经验分布固定 | 损失函数的统一解释 | 4.8 |
| `I(X;Y) = H(X) − H(X\|Y)` | — | 互信息 | 4.8 |
| `PPL = exp(平均负对数似然)` | — | 困惑度 | 4.8 / 16.1 |

---

## A.3 数值计算

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| Softmax 稳定化：`softmax(x)_i = e^(x_i − max x) / Σ_j e^(x_j − max x)` | 恒等变换（分子分母同乘 `e^(−max x)`） | 防上溢的唯一等价手段 | 5.3 |
| 两遍法方差：`Var = (1/n)Σ(x_i − μ)²` | 先算 μ 再算偏差 | 大均值小方差时唯一可靠 | 5.3 |
| 前缀和方差：`Σx²/n − μ²`，需截断负值 | 需 `Σx²` 前缀和 | O(1) 窗口统计量 | 5.3 / 23.2 |
| `e^x` 上溢阈值：FP64 ≈ 709、FP32 ≈ 88 | — | 为什么 FP64 不能解决溢出 | 5.1 |
| 机器 epsilon：FP32 ≈ 1.19e−7、FP64 ≈ 2.22e−16 | — | 浮点比较容差的依据 | 5.1 |
| 插值多项式存在唯一性 | n+1 个**互异**节点、次数 ≤ n | 唯一性保证 | 5.4 |
| `L(x) = Σ_i y_i ℓ_i(x)`，`ℓ_i(x) = Π_{j≠i}(x−x_j)/(x_i−x_j)` | 互异节点 | Lagrange 插值 | 5.4 |
| Newton 差商形式 `N(x) = f[x_0] + f[x_0,x_1](x−x_0) + …` | 互异节点 | **动态加点只需再算一阶差商** | 5.4 |
| `cost = ‖Ax − b‖²` 的凸性 | 恒成立 | 最小二乘是凸问题 | 5.4 |
| Jacobi 迭代矩阵 `−D⁻¹(L + U)` | `A = D + L + U` | 全用旧值 | 5.5 |
| **Gauss-Seidel 迭代矩阵 `−(D + L)⁻¹U`** | 同上 | 新值立即生效 | 5.5 |
| 迭代收敛 ⟺ `ρ(迭代矩阵) < 1` | — | 收敛性判据 | 5.5 |
| 严格对角占优 ⟹ GS/Jacobi 收敛 | `\|a_ii\| > Σ_{j≠i}\|a_ij\|` | 常用充分条件 | 5.5 |
| `cond(A) = ‖A‖‖A⁻¹‖ = σ_max/σ_min` | A 可逆 | 条件数，衡量病态程度 | 5.6 |
| 浮点相等判断：`\|a − b\| < EPS` | EPS 取 1e−9 | 建议 EPS ≫ 累加噪声且 ≪ 真实间隙 | 5.6 / 26.1 |

---

## A.4 优化

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| 凸函数一阶判据：`f(y) ≥ f(x) + ∇f(x)ᵀ(y−x)` | f 可微且凸 | 切线是全局下界 | 6.1 |
| 凸函数二阶判据：`∇²f(x) ⪰ 0` | f 二阶可微 | Hessian 半正定 | 6.1 |
| 凸优化中局部最优 = 全局最优 | 目标凸、可行域凸 | 凸性的价值 | 6.1 |
| `w ← w − η∇L(w)` | — | 梯度下降 | 6.2 |
| `E[∇L_B(w)] = ∇L(w)` | 均匀采样 mini-batch | SGD 是无偏估计 | 6.2 |
| `v_t = βv_{t−1} + (1−β)g_t`；`w ← w − ηv_t` | — | 动量 | 6.3 |
| `m_t = β₁m_{t−1} + (1−β₁)g_t`，`v_t = β₂v_{t−1} + (1−β₂)g_t²` | — | Adam 一阶/二阶矩 | 6.3 |
| 偏差校正 `m̂_t = m_t/(1−β₁ᵗ)`、`v̂_t = v_t/(1−β₂ᵗ)` | 初值为 0 | **无校正则前期步长严重偏小** | 6.3 |
| `w ← w − η m̂_t/(√v̂_t + ε)` | 默认 β₁=0.9、β₂=0.999 | Adam 更新式 | 6.3 |
| AdamW：`w ← w − η(m̂/(√v̂+ε) + λw)` | 权重衰减与自适应项**解耦** | 正确的 L2 实现 | 6.3 |
| `Σ_t η_t = ∞` 且 `Σ_t η_t² < ∞` | — | Robbins-Monro 严格收敛条件 | 6.5 |
| `Σ_t η_t = ∞` 且 `η_t → 0` 不要求平方可和 | — | 凸函数下更弱条件 | 6.5 |
| `L(w,α,β) = f(w) + Σα_i g_i(w) + Σβ_j h_j(w)` | — | 拉格朗日函数 | 6.6 |
| KKT：`∇f + Σα_i∇g_i + Σβ_j∇h_j = 0`；`α_i g_i = 0`；`α_i ≥ 0` | 约束规范成立 | 约束最优的必要条件 | 6.6 |

---

## A.5 机器学习

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| 泛化误差 = 偏差² + 方差 + 不可约噪声 | 平方损失 | 偏差-方差分解 | 7.3 |
| `Accuracy = (TP+TN)/(TP+TN+FP+FN)` | — | 类别不平衡时失真 | 7.6 |
| `Precision = TP/(TP+FP)` | — | 惩罚**误报** | 7.6 |
| **`Recall = TP/(TP+FN)`** | — | 惩罚**漏检** | 7.6 |
| `F1 = 2PR/(P+R)` | — | P、R 的调和平均 | 7.6 |
| AUC = 随机取一正一负、得分正 > 负的概率 | — | 与阈值无关的排序质量 | 7.6 |
| `MSE = (1/n)Σ(y_i − ŷ_i)²`、`MAE = (1/n)Σ\|y_i − ŷ_i\|` | 回归指标 | **不用于分类评价** | 7.6 |
| `R² = 1 − SSE/SST` | — | 回归拟合优度 | 7.6 |
| L2：`J = L + λ‖w‖²` | 高斯先验 | 岭回归，权重收缩但不为 0 | 8.2 |
| L1：`J = L + λ‖w‖₁` | 拉普拉斯先验 | Lasso，**产生稀疏解** | 8.2 |
| 早停 ≈ 限制 `‖w − w_0‖` | 小学习率下 | 与 L2 正则同源 | 8.3 |
| `ŷ = wᵀx + b`；`w = (XᵀX)⁻¹Xᵀy` | 列满秩 | 线性回归 / 正规方程 | 9.1 |
| `σ(z) = 1/(1+e^(−z))`，`σ′(z) = σ(z)(1−σ(z))` | — | Sigmoid | 9.2 |
| `L_CE = −[y ln p + (1−y)ln(1−p)]` | — | 交叉熵；**关于 w 凸** | 9.2 |
| `∂L_CE/∂w = (σ(z) − y)x` | Sigmoid + 交叉熵 | σ′ 被约掉，梯度不饱和 | 9.2 |
| `L_MSE = (σ(z) − y)²` 含 `σ′(z)` 因子 | — | **非凸 + 饱和区梯度消失** | 9.2 |
| `softmax(z)_i = e^(z_i)/Σ_j e^(z_j)` | — | 多分类输出；平移不变 | 9.3 |
| 指数族 `p(y\|η) = h(y)exp(ηᵀT(y) − A(η))` | — | GLM 的分布假设 | 9.4 |
| AdaGrad：`η_i,t = η/√(Σ_{s≤t} g_i,s² + ε)` | — | 稀疏特征获得更大有效步长 | 9.5 |
| K-Means 目标 `J = Σ_k Σ_{x∈C_k} ‖x − μ_k‖²` | — | SSE/Inertia，单调不增 | 10.1 |
| single-linkage `d(A,B) = min_{a∈A,b∈B} d(a,b)` | — | 最近点；易链式效应 | 10.2 |
| complete-linkage `d(A,B) = max d(a,b)` | — | 最远点；紧凑球形 | 10.2 |
| average-linkage `d(A,B) = 平均值` | — | 折中 | 10.2 |
| centroid-linkage：两簇中心距离 | — | 计算最省 | 10.2 |
| DBSCAN 核心点：`\|N_ε(p)\| ≥ minPts` | 邻域含自身 | 密度聚类第一判据 | 10.3 |
| 密度相连：存在核心点 `o` 使 p、q 都密度可达于 o | 传递链上全为核心点 | 簇定义；等价于连通分量 | 10.3 |
| k-medoids 代价 `cost(C,c) = Σ_{i∈C} u_i·d(x_i, x_c)` | c 必须是真实样本 | 中心受限于样本点 | 10.4 |
| GMM 密度 `p(x) = Σ_k π_k N(x\|μ_k, Σ_k)` | `Σπ_k = 1` | 软聚类 | 10.5 |
| EM：`Q(θ\|θ^(t)) = E_{Z\|X,θ^(t)}[log P(X,Z\|θ)]` | — | E 步求期望、M 步最大化 | 10.5 |
| PCA：`max_w wᵀΣw` s.t. `‖w‖ = 1` ⟹ w 为 Σ 最大特征向量 | 中心化数据 | 方差最大化视角 | 11.1 |
| PCA 累计贡献率 `Σ_{i≤k}λ_i / Σ_iλ_i` | λ 为协方差矩阵特征值 | 选主成分个数（85%/95%） | 11.1 |
| LDA 广义瑞利商 `J(w) = (wᵀS_B w)/(wᵀS_W w)` | 需类别标签 | 类间大 / 类内小 | 11.2 |
| LDA 降维维数上限 `C − 1` | C 为类别数 | 二分类只能降到 1 维 | 11.2 |

---

## A.6 深度学习

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| `ReLU(x) = max(0, x)`；导数 `1` 或 `0` | — | 缓解梯度消失；可能 Dead ReLU | 12.2 |
| `GELU(x) = x·Φ(x)` | Φ 为标准正态 CDF | Transformer 常用 | 12.2 |
| 链式法则 `∂L/∂w = (∂L/∂y)(∂y/∂w)` | — | 反向传播基础；**别漏内层因子** | 12.5 |
| 反向传播：`δ^(l) = (W^(l+1)ᵀδ^(l+1)) ⊙ f′(z^(l))` | — | 误差反向传递 | 12.5 |
| `∂L/∂W^(l) = δ^(l) (a^(l−1))ᵀ` | — | 权重梯度 = 误差 × 输入 | 12.5 |
| 参数量（单层）`= (d_in + 1) × d_out` | 含偏置 | 模型规模估算 | 12.1 |
| Xavier：`Var(W) = 2/(n_in + n_out)` | 线性/ tanh 激活 | 保持激活方差 | 13.1 |
| He：`Var(W) = 2/n_in` | ReLU 激活 | 补偿 ReLU 砍掉一半 | 13.1 |
| BatchNorm：`ŷ = γ(x−μ_B)/√(σ_B²+ε) + β` | 训练用批统计、推理用滑动平均 | 逐通道归一化 | 13.2 |
| LayerNorm：对**单样本的特征维**归一化 | 与 batch 无关 | NLP/Transformer 首选 | 13.2 |
| RMSNorm：`ŷ = x/√(mean(x²)+ε) · γ` | 去掉均值中心化 | 更省算力，大模型常用 | 13.2 |
| 残差 `y = x + F(x)`，梯度 `∂y/∂x = I + ∂F/∂x` | — | 恒等项保证梯度不消失 | 13.3 |
| 单 token KV Cache（FP16）`= 2 × L × h × 2` 字节 | 单头（h 为隐藏维） | 显存估算 | 19.3 |
| 注意力分数 `S = QKᵀ`，形状 `[B,H,N,N]` | — | 行数 = query 数 | 15.2 |
| 缩放点积注意力 `Attention(Q,K,V) = softmax(QKᵀ/√d_k)V` | — | 缩放因子的方差推导见 15.2 | 15.2 |
| 为什么除以 `√d_k`：内积方差 `≈ d_k·σ²` | 各分量独立同分布 | 不缩放则 softmax 饱和 | 15.2 |
| 维度账本：`d_k = d_model / H` | 多头 | 拼接后回到 `d_model` | 15.3 |
| 注意力复杂度 `O(N²d)`；显存 `O(N²)` | 全注意力 | 稀疏注意力的动机 | 15.6 |

---

## A.7 大模型与推理工程

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| 自回归分解 `P(x) = Π_t P(x_t \| x_<t)` | — | 语言模型目标 | 16.1 |
| PPO clip 目标 `min(r_t Â_t, clip(r_t,1−ε,1+ε)Â_t)` | — | 限制策略更新幅度 | 16.3 |
| RLHF 目标 `max E[r_φ] − β·KL(π_θ‖π_ref)` | — | 奖励最大化 + 防跑偏 | 16.3 |
| GRPO 组内优势 `Â_i = (r_i − mean(r)) / std(r)` | 同一 prompt 采样一组 | **替代 critic** | 16.3 |
| 重要性采样比率 `r_t(θ) = π_θ(o_t\|·) / π_old(o_t\|·)` | — | off-policy 修正 | 16.3 |
| GSPO 序列级比率 `r(θ) = π_θ(o\|·)/π_old(o\|·)` | 整条序列 | **降低长序列方差** | 16.3 |
| DPO 损失 `−log σ(β log(π_θ(y_w)/π_ref(y_w)) − β log(π_θ(y_l)/π_ref(y_l)))` | 成对偏好数据 | 无需奖励模型与 RL 循环 | 16.4 |
| chunk 数 `= 1 + ⌈(T − C)/(C − O)⌉` | `T > C`，T 为总 token 数 | 带重叠切分 | 17.2 |
| 字符→token：中文字符 `≈ 0.7 token/字` | 经验比例 | 上下文长度估算 | 17.2 |
| 归一化后内积 ≡ 余弦相似度 | `‖x‖ = ‖y‖ = 1` | 向量库检索等价性 | 17.3 |
| 温度采样 `p_i ∝ exp(z_i/T)` | — | T↓ 更确定、T↑ 更随机 | 18.2 |
| Top-P 核集合：最小的 S 使 `Σ_{i∈S} p_i ≥ p` | 概率降序 | 自适应候选集 | 18.3 |
| 核内重归一化 `P(A) = p_A / Σ_{i∈S} p_i` | — | 例：0.4/0.9 ≈ 0.444 | 18.3 |
| 算术强度 `I = FLOPs / Bytes` | — | Roofline 判据 | 19.1 |
| Roofline 上界 `= min(峰值算力, I × 带宽)` | — | 判断 compute/memory-bound | 19.1 |
| prefill：大 M 的 GEMM，算术强度高 ⟹ **compute-bound** | — | 瓶颈在算力 | 19.2 |
| decode：GEMV，算术强度极低 ⟹ **memory-bound** | 每步 1 个 token | 瓶颈在权重+KV 读取带宽 | 19.2 |
| online softmax 递推：`m_new = max(m_old, max(x_block))`；`ℓ_new = e^(m_old−m_new)ℓ_old + Σe^(x−m_new)` | 分块处理 | FlashAttention 核心 | 19.5 |
| 量化 `q = round(r/s)`、`r = s·q` | — | 线性量化 | 20.2 |
| 缩放因子 `s = max(\|r_min\|,\|r_max\|)/(2^(n−1) − 1)` | n bit，int8 时 n=8 | 让最大幅值落满量程 | 20.2 |
| 非对称量化 `q = round(r/s) + z` | 有零点 z | 适配非对称分布 | 20.3 |
| `s = a/2^b`：乘法 → `a₁a₂ / 2^(b₁+b₂)` | — | **a 相乘、b 相加** | 20.4 |
| `s = a/2^b`：加法 → `(a₁≪(Δ) + a₂≪(Δ'))/2^max` | — | 移位 + 加法 | 20.4 |
| `b` 取满足 `half_up(s·2^b) ≤ 127` 的最大值 | int8 | b 越大精度越高 | 20.4 |
| 集合通信：All-Reduce 通信量 `2(N−1)/N × 数据量` | Ring 实现 | 与参数量同阶 | 21.1 |
| TP（Megatron）：每层前向 + 反向各 1 次 All-Reduce | MLP 列切 + 行切 | 通信频繁 ⟹ 必须同机 | 21.3 |
| PP bubble 比例 `≈ (p−1)/(m + p − 1)` | p 级、m 个 micro-batch | 流水线空闲占比 | 21.4 |
| ZeRO 显存节省：优化器状态 4×、梯度 2×、参数 2×（混合精度） | 分片到 N 卡 | 节省 ≈ 1/N | 21.5 |

---

## A.8 算法与工程

| 公式 / 结论 | 成立条件 | 用途 | 出处 |
|---|---|---|---|
| 区间和 `sum(l..r) = P[r+1] − P[l]` | 前缀和 P | O(1) 区间查询 | 23.2 |
| 窗口方差 `= (Σx²)/m − μ²`，需截断负值 | 前缀和两条 | O(1) 窗口统计 | 23.2 / 5.3 |
| 单调队列维护窗口最值：入队弹尾 + 出队检查队头 | 比较关系具有传递性 | O(N) 总代价 | 23.4 |
| 0/1 背包：`f[j] = max(f[j], f[j−w]+v)`，**j 倒序** | 每件至多一次 | 防重复选取 | 24.3 |
| 完全背包：同式但 **j 正序** | 每件可重复 | 允许重复选取 | 24.4 |
| 二维费用背包：**两维都倒序** | 两种资源约束 | 运维任务收益最大化 | 24.5 |
| 分组背包：每组必选一件 ⟹ **每层新开数组** | 组内互斥 | 原地滚动会让同组被选两次 | 24.6 |
| "恰好"口径的单调性：初值 `f[0]=0`、其余 `−∞` | — | 还原实际资源用量 | 24.7 |
| 排除任一元素后的最小值 ∈ {最小值, 次小值} | — | 消掉一重枚举（多 Agent 调度） | 24.8 |
| 并查集复杂度 `O(α(n))` | 路径压缩 + 按秩合并 | 近似常数 | 25.2 |
| half-up 取整 `⌊x + 0.5⌋` | 恰为 .5 向上 | **不能用 Python `round()`（银行家舍入）** | 26.3 |
| 浮点判等 `\|a − b\| < EPS`，EPS 取 1e−9 | — | 断同分、判"不超过半径" | 26.2 |
| 距离比较用平方 + 容差 `d² ≤ r² + 1e−7` | 坐标精度有限 | 省开根号 + 防漏判 | 26.2 |
| 负零归一 `-0.00 → 0.00` | 格式化输出 | 避免格式判错 | 26.4 |
| 复杂度反推可接受算法 | `N ≤ 2000 → O(N²)`；`N ≤ 1e5 → O(N log N)` | 读题先看数据范围 | 22.4 |
| Python 安全操作量级 | 约 `1e6 ~ 1e7` 次基本操作/秒 | 估算是否会超时 | 22.6 |

---

> [!TIP]
> **如何用这张表**：考前 1 小时只看两列 —— **公式**与**成立条件**。所有被真题设为干扰项的，都是"条件被悄悄改掉"的公式，例如把"单位向量下"的 `2 − 2cosθ` 换成 `1 − cosθ`，把"列数"换成"行数"，把"恰好"换成"不超过"。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/appendix-a/  

