随机算法为何无处不在:从快速排序到 Miller-Rabin 的可靠性逻辑
arpit_bhayani · x · 2026-11-05
系统工程师 Arpit Bhayani 撰文科普随机化算法:加入随机数后,快速排序随机选 pivot 可让期望复杂度从 O(n²) 降至 O(n log n),不再存在可预测的坏输入。
- 误差可任意缩小:Miller-Rabin 素性测试单轮错误率至多 1/4,独立跑 40 轮错误率降到 4^-40,远低于宇宙射线翻转内存比特的概率
- 生产系统中的随机化:哈希表防对抗性碰撞、跳表免重平衡获得期望平衡树性能、布隆过滤器/HLL 用微小误差换内存、随机双选负载均衡效果出乎意料地好
- 随机化买到三样东西:实现更简单、抗对抗输入、在确定性最优解未知或更慢时更快
作者结论:让算法可靠的最简单方式,有时就是放弃强求确定性。
「研究」频道最新
- Berkeley 团队揭示 LLM 递归自摘要信息丢失,用重构奖励的 RL 修复 — berkeley_ai · 2026-11-05
- ReproEvalCard：让 LLM 管线评测可复现的报告标准提案 — kalyan_kpl · 2026-11-05
- 哈佛 Gary King 团队推出 Certify：AI 代理自动认证论文复现包 — RexDouglass · 2026-11-05
- RETROGRADE 逆向工程 Agent 基准放榜:14 个前沿模型盲测,混淆让所有模型掉分 — amplifiedamp · 2026-11-05
- imec 球透镜方案实现光子芯片板级耦合，关键链路损耗仅 3.4dB — jwt0625 · 2026-11-05
- 谷歌论文详解太空数据中心:81 星编队让 TPU 在轨推理 — sebkrier · 2026-11-05