大整数乘法

问题描述

$n$ 位二进制整数 $X$ 和 $Y$ 相乘,通常算法时间复杂度为 $O(n^2)$。是否存在分治算法可以降低时间复杂度?

问题分析

设 $X$ 和 $Y$ 是 $n$ 位整数,将 $X$ 分为 $n/2$ 位的两部分(高 $n/2$ 位的 $A$ 和低 $n/2$ 位的 $B$),将 $Y$ 分为 $n/2$ 位的两部分(高 $n/2$ 位的 $C$ 和低 $n/2$ 位的 $D$)。则 $X \times Y$ 可以表示为:

\begin{align} XY &= (A \cdot 2^{n/2} + B)(C \cdot 2^{n/2} + D) \\ &= AC \cdot 2^n + (AD + BC) \cdot 2^{n/2} + BD \\ &= AC \cdot 2^n + ((A+B)(C+D) - AC - BD) \cdot 2^{n/2} + BD \end{align}

需要计算的子问题包括 $AC$、$BD$、$(A+B)(C+D)$。其中 $(A+B)(C+D)$ 中的加法运算的时间复杂度取决于问题规模,即数字位数 $n$。因此可以得到如下递推式:

\begin{align} T(n) = 3 T\left( \frac{n}{2} \right) + \Theta(n) \end{align}

可以解得时间复杂度为:

\begin{align} T(n) = \Theta\left(n^{\log _{2}{3}}\right) \end{align}

Next