复杂度¶

算法复杂度是衡量一个算法优劣的金标准。它可以分为 时间复杂度 和 空间复杂度 。时间复杂度表示需要多久去计算，空间复杂度则表示需要多少内存来完成计算。由于目前计算机技术的发展，空间复杂度的重要性越来越低，而时间复杂度的重要性越来越高，所以当我们提到复杂度的时候，一般都表示时间复杂度。我们通常通过 渐进分析（Asymptotic Analysis） 来分析算法的复杂度。

让我们从一个简单的\(n\)位数乘法运算例子来开始这一章。

传统计算机是如何进行乘法运算的呢？按位相乘？不，这有些太传统了。分治法（Divide and Conquer）？对，没有什么比分治法最简单得了，将一个复杂的大问题转换成多个简单的小问题，多么美妙！对于\(n\)位数\(x\)和\(y\)，我们可以将它们之间的乘法运算\(x \times y\)转换为\((a \times 10^\frac{n}{2} + b) \times (c \times 10^\frac{n}{2} + d)\) = \((ac) \cdot 10^n + (ad + bc) \cdot 10^\frac{n}{2} + bd\)。就这样，通过几步简单的操作，我们就将一个\(n\)位数相乘问题转换成了四个\(\frac{n}{2}\)位数相乘问题。只是，他的复杂度稍微高了一些，有\(O(n{^2})\)。那么，我们如何能优化他呢？通过观察，我们可以发现\(ad + bc = (a + b) \cdot (c + d) - ac - bd\)。由于\(ac\)、\(bd\)都是我们计算所需要的，我们可以通过替代来将这里的两个乘法缩减到一个新乘法，最终转换为：\((ac) \cdot 10^n + ((a + b) \cdot (c + d) - ac - bd) \cdot 10^\frac{n}{2} + bd\)。这个式子看起来要更复杂一些，但实际上我们将这个\(n\)位数相乘问题转换成了三个\(\frac{n}{2}\)位数相乘问题，使得时间复杂度降低到了\(O(n^{\log_2 3})\)（如果你在这里还一头雾水的话，请不要担心，我们稍后会详细解释）。这个算法也被称作Karatsuba算法，与之类似的还有Toom-Cook算法，他将这个\(n\)位数相乘问题转换成了五个\(\frac{n}{3}\)位数相乘问题，使得时间复杂度进一步降低到了\(O(n^{\log_3 5})\)。我们强烈建议你试试能不能自己去找到如何完成这样的分解。此外，如果你有志于算法的话，Arnold Schönhage和Volker Strassen于1971年提出使用快速傅里叶变换（FFT）进行乘法运算的SSA（Schönhage-Strassen algorithm）将乘法运算提升到了多项式时间，今年早些时候，David Harvey和Joris van der Hoeven发布的论文Integer multiplication in time O(n log n)将乘法运算的速度提升到了目前的理论极限 – \(O(n log n)\)。

符号¶

我们刚才提到了算法的复杂度是\(O(n log n)\)，这又是什么意思呢？

大O符号，又称渐进符号，是德国数学家1892年引入的。除此之外还有大Ω符号与大Θ符号（一个有趣的事实，大O符号其实应该是大Ο符号（希腊字母，Omicron，但是因为Ο和O没什么视觉区别，所以一般会直接说O。

算法是多样的，同一个算法在不同情况下的复杂度一般不同（比如快速排序和归并排序最好情况都为\(\Omega(n \log n)\)，但快速排序最坏情况是\(O(n^2)\)，而归并排序则是\(O(n \log n)\)），Θ在实际当中很少应用。此外，一个算法的最坏情况要比最好情况更有价值。所以一般情况下，我们说到复杂度的时候都会使用O，甚至有些时候我们会说某个算法的最好情况是\(O(n \log n)\)，而不使用Ω。

有了大O和大Ω，自然就有小o和小ω。

小o和小ω表示的是绝对大于，譬如说当\(f(n) = n^2 + n\)时，\(f(n) = Ω(n^2)\)但\(f(n) \neq ω(n^2)\)。函数\(f(n)\)的复杂度可能既为\(O(g(n))\)也为\(\Omega(g(n))\)（此时即为\(\Theta(g(n))\)，但不可能同时为\(o(g(n))\)和\(\Omega(g(n))\)或者\(O(g(n))\)和\(\Omega(g(n))\)。小o和小ω仅在这里列出以供读者了解，现实当中几乎没有人使用这些符号。

时间¶

我们通常会按照复杂度称这个算法是某某时间的。

下表提供了当c=2，n=1000时各个时间所需的运算次数，可以直观地发现多项式时间及以上的算法不可解。

分析¶

说了这么多，终于到了这最重要的一步了。如果分析一个算法的复杂度呢？

用我们之前的Karatsuba算法举例来说：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def karatsuba(x, y):
  x_len = len(str(x))
  y_len = len(str(y))

  if x_len == 1 or y_len == 1:
    return x * y

  else:
    n = ceil(max(len_x, len_y) / 2)
    a = floor(x / 10**n)
    b = x % 10**n
    c = floor(y / 10**n)
    d = y % 10**n
    ac = karatsuba(a,c)
    bd = karatsuba(b,d)
    e = karatsuba(a+b, c+d) - ac - bd

    return ac * 10**(n*2) + (e * 10**n) + bd

很简单，不是吗？