神奇的算法01--乘法

数学和计算机科学中的算法是指一系列有限的数学上严格定义的操作, 通常用来执行某种操作或完成某些计算任务. 其中, 我认为有很多算法非常好玩, 值得分享. 这个系列旨在通过最浅显易懂的语言向大家介绍一些十分有趣的算法, 以供感兴趣的同学们参考.

简单的算法分析

算法分析指对某一算法进行复杂度分析, 通常包括时间复杂度和空间复杂度. 复杂度指随着输入的规模的增长, 算法对某种资源消耗的增长趋势.

举个例子来说:

• 若一个算法的时间复杂度是线性的, 则我们可以认为输入规模扩大一倍时, 算法所运行的时间也会大致增长一倍.
• 若一个算法的时间复杂度是平方的, 则我们可以认为输入规模扩大一倍时, 算法所运行的时间会大致增长到四倍($(2n)^2 = 4n^2$).

为了能够精准描述算法的复杂度, 我们可以定义以下符号. 首先可以定义两个函数$f, g$:

• 若$f = O(g)$, 则$\exists C, \text{s.t. } f <= C\cdot g$
• 若$f = o(g)$, 则$\lim_{n \to \infty}\frac{f(n)}{g(n)} = 0$
• 若$f = \Omega(g)$, 则$g = O(f)$
• 若$f = \omega(g)$, 则$g = o(f)$
• 若$f = \Theta(g)$, 则$f = O(g)$且$f = \Omega(g)$

直观上来讲:

• $f = O(g)$意味着$f$的增长率小于等于$g$
• $f = o(g)$意味着$f < g$
• $f = \Omega(g)$意味着$f \ge g$
• $f = \omega(g)$意味着$f > g$
• $f = \Theta(g)$意味着$f = g$

乘法

现在, 让我们来讨论一下一个我们大家都十分熟悉的算法 – 乘法. 我们这里讨论的乘法是指两个$n$位十进制整数之间的乘法, 并且假设两个一位数之间的乘法复杂度是$O(1)$, 两个$n$位数之间的加法复杂度是$O(n)$.

算法一

我们先来讨论一个最简单的乘法算法: 两个$n$位整数之积$A \times B$等于$C$, 则$C$等于$B$个$A$之和. 伪代码如下:

def mul(A, B): 
  C = 0
  for i in range(B):
    C = C + A
  return C

让我们分析一下这个算法的时间复杂度吧! 首先, $C$最大不超过一个$2n$位整数, 因此可以将C + A看作一个$O(2n)$时间复杂度的算法. 而$O(2n) = O(n)$(常数不会影响增长率, 因此此后计算时间复杂度时都可以将常数一概省略).

同时, $B < 10^n$, 因此该算法的整体时间复杂度是$O(10^n \cdot n)$

这也就意味着, 若将输入的规模$n$扩大一倍, 则需要的时间大约翻了$200$倍. 天呐! 这个算法也太垃圾了吧!

算法二

显而易见的是, 我们在小学学过的乘法算法, 列竖式, 都比这方便多了.

     1234
*    5678
---------
     9872 <-- O(n)
    8638  <-- O(n)
   7404   <-- O(n)
+ 6170    <-- O(n)
---------
  7006652 <-- O(n)

由此观之, 算法的时间复杂度是$O(n^2 + n)$. 由于$n$这一项比$n^2$增长率要小, 因此

从此以后, 我们考虑复杂度时只需要考虑最大的一项即可.

我们能不能做得更好?

算法三

当然可以! 接下来, 我们要做一些看起来很奇怪的事: 将$A, B$平分为长度相等的两部分

因此

我们发现了什么?

我们将一个$n$位数的乘积转化为了四个$\frac{n}{2}$位数的乘积之和! 因此有:

同时, $T\left(\frac{n}{2}\right)$可以继续拆分, 形成一个递归的结构. 这不就是一个数列题嘛!

其中$k = \log_2 n$

?????这个算法还是$O(n^2)$的啊? 合着刚刚那一堆分析都白费了?

但是, 我们其实不需四个乘积之和的. 因为我们需要的是$A_{hi}B_{lo} + A_{lo}B_{hi}$, 而不需要求出它们各自的值!

因此, 我们只需要求:

• $P_1 = A_{hi}B_{hi}$
• $P_2 = A_{lo}B_{lo}$
• $P_3 = (A_{hi} + A_{lo})(B_{hi} + B_{lo})$

而$A_{hi}B_{lo} + A_{lo}B_{hi} = P_3 - P_2 - P_1$

因此! 递推公式转变为了

最终, 求得

伪代码如下:

def mul(A, B, n):
    if n == 1: 
        return A * B # O(1)
    else: 
        Ahi, Alo = A // 10 ** (n/2), A % 10 ** (n/2) # O(n)
        Bhi, Blo = B // 10 ** (n/2), B % 10 ** (n/2) # O(n)

        P1 = mul(Ahi, Bhi, n/2) # T(n/2)
        P2 = mul(Alo, Blo, n/2) # T(n/2)
        P3 = mul(Ahi + Alo, Bhi + Blo, n/2) # T(n/2)

        return P1 * 10 ** n + (P3 - P1 - P2) * 10 **(n/2) + P2 # O(n), 因为乘十和除十都是十分容易计算的

写在最后

这是我第一次尝试这样的文章, 欢迎大家私信我一些想法, 而我也会悉心听取大家的建议. 再次感谢大家的支持.