large-scale-math-algorithmslisted

# 大规模数学算法升级 `complexity-cuts` 帮你把现有代码降一个复杂度档；本技能在**经典算法已是最优（O(n log n) 已是地板）**时介入，靠数学再凿穿一层地板——通常以「接受有界近似 / 利用结构 / 换到更聪明的代数空间」换取渐近优势。模型懂这些技法，但几乎从不主动提出，本技能负责逼它伸手去够。 > 铁律：**没有书面 ε/δ 且调用方明确接受，绝不引入任何近似结构。** 把 Bloom 过滤器塞进调用方默认精确的路径，是生产事故，不是优化。 ## 何时使用 适用： - 大规模数据（**n ≥ 10⁶**）：相似检索、去重、Top-K / 重击者、流式分析、基数估计、向量检索、推荐。 - 信号/图像处理、多项式或大整数运算、卷积、图距离、计算几何、随机化算法。 - 经典 O(n log n) 已是地板、仍需渐近突破：Bloom、HyperLogLog、Count-Min、MinHash/LSH、FFT/NTT、JL 投影、sweep line、kd-tree/BVH、快速幂、幺半群并行归约、摊还势能法。 - 通常在 `complexity-cuts` 或经典选型已确认「经典解不够」之后再加载。 **不该用（负边界）**： - 调用方需要精确结果（鉴权、计费、为正确性去重、主键、任何流入主键的值）。 - n 小（n < 10⁴）且不在热路径——线性扫描微秒级搞定。 - 瓶颈在 I/O 而非 CPU/内存——数学优势会被网络/磁盘吃掉，退回去优化 I/O。 - 团队无人能在凌晨 3 点 debug 这个技法（写下「team familiarity: ?」）。 ## 步骤 提出任何数学级技法前，消息须**按此顺序**包含 1–7，缺任一项不得提出；齐了再给第 8 项代码： 1. **经典下限**：最好的非数学算法及其 Big-O（如「Hash join 是 O(n+m)，已经到顶」）。 2. **为何经典不够**：n 太大 / 空间爆 / 实时截止 / 单机内存放不下。 3. **命名技法**：必须**点名**，禁止「一个聪明的近似」这类含糊说法。 4. **精确还是近似**：`mode: exact` 或 `mode: approximate`；近似须写 ε/δ（误报率、相对误差、失真界）+ 一句「调用方能否容忍这种错」。 5. **新界推导**：一行 bound 论证（如「HLL：O(log log n) 位估基数，标准误 1.04/√m」）。无界不提。 6. **买卖代价**：一行写清「买到（空间/时间/wall-clock/并行）vs 付出（accuracy ε=? / 复杂度 / 依赖 / 非确定性 / 数值稳定性）」；代价对调用方不可见则写「callers see no change」。 7. **何时禁用**：至少一条 disqualifier。 8. **代码或伪代码**。 ## 指令 - **点名技法**（可审计 > 含糊）：`Bloom filter`、`HyperLogLog`、`Count-Min Sketch`、`MinHash + LSH`、`Johnson–Lindenstrauss 投影`、`FFT`、`NTT`、`Karatsuba`、`Strassen`、`快速幂`、`sweep line`、`kd-tree`、`BVH`、`带路径压缩的并查集`、`Boyer-Moore 多数投票`、`reservoir sampling`、`Floyd 龟兔判环`、`Fenwic