附录 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 |
提示
如何用这张表：考前 1 小时只看两列 —— 公式与成立条件。所有被真题设为干扰项的，都是"条件被悄悄改掉"的公式，例如把"单位向量下"的 2 − 2cosθ 换成 1 − cosθ，把"列数"换成"行数"，把"恰好"换成"不超过"。