大整数乘法如何优化？Karatsuba 分治为什么比 O(n²) 快？

简化版

小学竖式乘法逐位相乘，是 O(n²)（n 为位数）。Karatsuba 把两个 n 位数各从中间拆成高低两半，本来求乘积需要 4 次子乘法，它用一个恒等式 ad+bc = (a+b)(c+d) − ac − bd，把 4 次子乘法减到 3 次。递归式从 4T(n/2) 降到 3T(n/2)+O(n)，由主定理得 O(n^log₂3) ≈ O(n^1.585)，比 O(n²) 快。同样的「减少子乘法次数」思想用在矩阵上就是 Strassen 算法（8 次减到 7 次，O(n^2.807)）。

详细版

把两个 n 位大数 x、y 从中间劈开（m = n/2）：

x = a · 10^m + b      （a 是高位半，b 是低位半）
y = c · 10^m + d
x · y = ac·10^(2m) + (ad + bc)·10^m + bd

朴素分治：算 ac, ad, bc, bd 共 4 次 n/2 位乘法 → T(n)=4T(n/2)+O(n)=O(n²)，没省。
Karatsuba 的巧思：注意到中间项 ad+bc 不必单独算两次乘法。令

p1 = a·c
p2 = b·d
p3 = (a + b)·(c + d) = ac + ad + bc + bd
则  ad + bc = p3 − p1 − p2

只用了 p1, p2, p3 3 次乘法（加减是 O(n) 的廉价操作）。递归式变成：

T(n) = 3·T(n/2) + O(n)   →   O(n^log₂3) ≈ O(n^1.585)

收益来源：把「4 次子乘法」压成「3 次」，指数从 log₂4=2 降到 log₂3≈1.585。

完整版教学

一、竖式乘法为什么是 O(n²)

两个 n 位数相乘，小学竖式的做法是：用第二个数的每一位去乘第一个数的每一位，再错位相加。总共 n × n 次一位数乘法，所以是 O(n²)。位数不大时无所谓，但做大整数运算（密码学 RSA 动辄几千位）时，O(n²) 就成了瓶颈，需要更快的乘法。

二、分治拆分：高低两半，四次子乘法（先没省）

分治的第一反应：把两个 n 位数各从中间劈成「高位半」和「低位半」，各 n/2 位。记 x = a·10^m + b、y = c·10^m + d（m=n/2），展开：

x·y = (a·10^m + b)(c·10^m + d)
    = ac·10^(2m) + (ad + bc)·10^m + bd

要算出结果，似乎需要 4 个乘积：ac、ad、bc、bd（乘 10^m 只是移位、加法是廉价的）。写成递归式 T(n)=4T(n/2)+O(n)，由主定理（情况一，n^log₂4=n²）得 O(n²)——和竖式一样，白分治了。想真正加速，必须减少子乘法的次数。

三、Karatsuba 的巧思：3 次乘法代替 4 次

Karatsuba（1960 年）的关键观察：中间项 ad+bc 可以用另外几个已经要算的乘积「凑」出来，不必花两次乘法。

构造三个乘积：

p1 = a · c                     （高位 × 高位）
p2 = b · d                     （低位 × 低位）
p3 = (a + b) · (c + d)         （和 × 和，只 1 次乘法）

展开 p3 = ac + ad + bc + bd，于是：

ad + bc = p3 − p1 − p2

最终：

x·y = p1·10^(2m) + (p3 − p1 − p2)·10^m + p2

整个过程只做了 p1, p2, p3 三次 n/2 位乘法，外加几次 O(n) 的加减和移位。用廉价的加减，换掉了一次昂贵的乘法。

四、复杂度：主定理算出 n^1.585

递归式变为：

T(n) = 3·T(n/2) + O(n)

套主定理：a=3, b=2 → 分水岭 n^(log₂3) ≈ n^1.585，而 f(n)=n 更小（情况一），所以

T(n) = Θ(n^log₂3) ≈ Θ(n^1.585)

n^1.585 明显小于 n²。位数越大，Karatsuba 相对竖式的优势越明显（大数库在位数超过某阈值时才切换到它，小数用竖式常数更小）。

五、延伸：Strassen 矩阵乘法与 FFT

「用加减凑、减少乘法次数」这个思想不止用于整数：

Strassen 矩阵乘法：两个 n×n 矩阵相乘，朴素分块要 8 次 n/2 子矩阵乘法（T(n)=8T(n/2)+O(n²)=O(n³)）。Strassen 用 7 个精心构造的乘积把它减到 7 次 → T(n)=7T(n/2)+O(n²)=O(n^log₂7)≈O(n^2.807)，突破了 O(n³)。和 Karatsuba 是同一路数。
更快的大数乘法：基于快速傅里叶变换（FFT） 的乘法能做到 O(n log n) 级别，是超大整数（如上百万位）实际使用的算法；Karatsuba 处在「竖式」和「FFT」之间的中等规模区间。

六、递归式、合并证明与数字推演

这道题的分治闭环是：把 x=aB^m+b、y=cB^m+d，利用 (a+b)(c+d)-ac-bd 得到交叉项，把 4 次半长乘法降为 3 次。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=3T(n/2)+Θ(n)=Θ(n^(log₂3))≈Θ(n^1.585)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：12×34：a=1,b=2,c=3,d=4；ac=3、bd=8、(a+b)(c+d)=21，交叉项 10，得到 3×100+10×10+8=408。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：小规模上常数和进位处理使朴素乘法更快；实现需处理符号、奇数位、基数和临时内存。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：Karatsuba 仍做 4 次递归乘法。 第三个乘积同时恢复 ad+bc，所以只有 3 次。
误区：复杂度是 O(n log n)。 指数是 log₂3≈1.585，不是 n 乘 log n。
误区：任何长度都比竖式快。 小输入的加减和分配开销可能更大，通常设置阈值切换。
追问：交叉项如何得到？ (a+b)(c+d)-ac-bd=ad+bc。
追问：奇数位怎么拆？ 可补零或让高低部分长度不同，但位权必须一致。
追问：更大整数还能怎样优化？ Toom-Cook、FFT/NTT 在更大规模有更优渐进复杂度。

九、加强记忆

大整数乘法：竖式逐位相乘是 O(n²)。Karatsuba 把两数各拆高低两半，x·y=ac·10^n+(ad+bc)·10^(n/2)+bd，朴素要 4 次子乘法（仍 O(n²)）；用恒等式 ad+bc=(a+b)(c+d)−ac−bd 把子乘法从 4 次减到 3 次 → T(n)=3T(n/2)+O(n)=Θ(n^log₂3)≈O(n^1.585)。同思想用在矩阵是 Strassen（8→7 次，O(n^2.807)），更大规模用 FFT 乘法（O(n log n)）。核心：用廉价的加减换掉昂贵的乘法。

简化版

详细版