第二章 递归与分治策略（二）

2.4 大整数的乘法

设X和Y都是n 位的二进制整数,计算它们的乘积 XY。

方法一：直接计算,但是这样做计算步骤太多,效率较低。如果将每两个1位数的乘法或加法看作一步运算,那么这种方法要进行O(n²)步运算才能算出乘积XY。

方法二：分治法。

将 n 位二进制整数X 和 Y都分为 2 段,每段的长为 n/2 位

则：

需要进行 4 次 n/2 位整数的乘法（AA',AB',BA' 和BB'）,以及 3次不超过 2n位的整数加法（分别对应于式中的加号）,此外还要进行2次移位（分别对应于式中乘 2^n和乘 2^n/2）。所有这些加法和移位共用 O(n)步运算。设 T(n)是 2个 n 位整数相乘所需的运算总数,则有

T(n) = O(n^2)

尝试将式子写成：

此时：

得到：

2.5 其他实例