从 O(n²) 到 Karatsuba:大整数乘法的分形复杂度解释
snikolov · x · 2026-10-08
针对一条引发争议的整数乘法复杂度讨论,@bzogrammer 给出通俗解释:这其实是典型的分形式复杂度界,并非离奇结果。
- 朴素大整数乘法是 O(n²),曾长期被认为是最优的,直到 Karatsuba 提出指数为 log2(3)≈1.58 的算法。
- 标准算法可以递归化:把一次乘法拆成 4 个更小的乘法加一些便宜的加法;Karatsuba 的技巧是用一组多项式恒等式把 4 次乘法减到 3 次,代价是更多加减法。
- 直觉上像一个面积每次边长翻倍增长 4 倍的正方形,但每次都能砍掉其中一块——复杂度指数因此从 2 降到 log2(3)。
所属事件:整数乘法首破 n log n 下界,AI 主导引热议(11 条相关)→
「研究」频道最新
- 斯坦福 CS312 深度学习炼金术课开课,作者建议用课程测验做合成数据种子 — jasondeanlee · 2026-11-22
- John Langford 评 FBT 笔记:定点迭代收敛与量化隐状态缓存 — JohnCLangford · 2026-11-22
- 菲尔兹奖得主吴宝珠评 AI 证明黎曼猜想:把 AI 输出当作待审视的自然数据 — Dr_Atoosa · 2026-11-22
- GPT-6 写出六页证明 Deligne 界,仅用 Cauchy–Schwarz 不等式 — Singularitarian · 2026-11-22
- 从 Hassabis 到 Tao:年初还被泼冷水的 AI 解数学千年难题,如今接连告破 — haider1 · 2026-11-22
- 清华提出 JANUS:微调后矫正参数,旧知识恢复超预训练水平 — 机器之心 · 2026-11-22