【算法随笔】大数乘法

大数乘法

假设 x 和 y是拥有n位数的大数,那么x*y的时间复杂度是多少?

algorithm 1

最朴素的想法,是使用小学课本中教授的乘法竖式的算法。即,x的每一位都需要与y的每一位进行相乘运算,并将结果按位相加。这个时候,算法的复杂度为$O(n^2)$。对算法复杂度有所了解的同学都知道,平方级的复杂度的算法大多都是存在优化空间的。那么如何对 algorithm 1进行优化呢?

algorithm2

我们是否可以采用分而治之的思想,将x和y分成高n/2位与低n/2位,进行操作?然后递归的进行这个过程呢?基于这种想法,我们的表达式可以记为:

$$
x * y = x_hy_h * 10^n + (x_hy_l+x_ly_h)*10^{n/2} + x_ly_l
$$
如果我们记xy的复杂度为T(n),那么显然四个子部分的复杂度为4T(n/2),而乘以$10^n$ 与$10^{n/2}$这一步骤的复杂度为n的线性复杂度,可以记为cn,因此有如下表达式:
$$\begin{cases}
T(n) ≤ 4T(n/2) + cn \quad\quad\quad,n > 1\ ||
\quad\quad\quad\quad\quad\quad\quad\quad\quad1\quad\quad\quad,n=1
\end{cases}
$$

根据主定理结论,T(n) 的复杂度为O($n^2$)。这似乎与暴力的竖式算法木有区别呀!并且这只是实际上的理论复杂度,考虑递归操作往往需要栈来实现,出栈入栈还会带来额外的开销。

algorithm3

有没有更好的方法呢?当然是有的!如果我们把$x_hy_h$ 记为A,$x_ly_l$记为B,$(x_h+x_l)(y_h+y_l)$记作D,那么原来的表达式可以写为:
$$
x * y = A * 10^n + (D-A-B)*10^{n/2} + B
$$
这样一来我们的递归就简化为三路递归,迭代式也变为:
$$\begin{cases}
T(n) ≤ 3T(n/2) + cn \quad\quad\quad,n > 1\ ||
\quad\quad\quad\quad\quad\quad\quad\quad\quad1\quad\quad\quad,n=1
\end{cases}
$$
根据主定理,此时的复杂度为O($n^{log_23}$)
tips1: 这个算法就是大名鼎鼎的Karatsuba algorithm
tips2: python的大数乘法中也分段的引入了该算法,当n小于等于70时,使用我们熟悉的竖式算法,否则使用Karatsuba algorithm

ref

热门相关:骑士归来   薄先生,情不由己   天启预报   苏醒的秘密   大神你人设崩了