跳转至

复杂度

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

时间频度

时间频度使用\(T(n)\)符号表示，他代表一个算法执行所需要花费的时间。

大O

对于两个在任意正实数的无界子集上定义的关于\(n\)的实数或复数函数\(f(n)\)和实数函数\(g(n)\)

当且仅当存在正实数\(c\)和\(n_0\)，使得对于所有\(n, n > n_0\)都有\(0 \leq f(n) \leq c g(n)\)

则我们称\(f(n)\)的渐进上界为\(g(n)\)，记作\(f(n) = O(g(n))\)。

一般而言，\(O(g(n))\)表示算法\(f(n)\)的最差情况运行时间。

大Ω

对于两个在任意正实数的无界子集上定义的关于\(n\)的实数或复数函数\(f(n)\)和实数函数\(g(n)\)

当且仅当存在正实数\(c\)和\(n_0\)，使得对于所有\(n, n > n_0\)都有\(0 \leq c g(n) \leq f(n)\)

则我们称\(f(n)\)的渐进下界为\(g(n)\)，记作\(f(n) = \Omega(g(n))\)。

一般而言，\(\Omega(g(n))\)表示算法\(f(n)\)的最好情况运行时间。

大Θ

对于两个在任意正实数的无界子集上定义的关于\(n\)的实数或复数函数\(f(n)\)\(和实数函数g(n)\)

当且仅当存在正实数\(c_1\)、\(c_2\)和\(n_0\)，使得对于所有\(n, n>n_0\)都有\(0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\)，即\(O(g(n)) = f(n) = Ω(g(n))\)

则记作\(f(n) = Θ(g(n))\)。

一般而言，\(\Theta(g(n))\)表示算法\(f(n)\)的运行时间。

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

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

小o

对于两个在任意正实数的无界子集上定义的关于\(n\)的实数或复数函数\(f(n)\)和实数函数\(g(n)\)

当且仅当对于任意正实数\(c\)都存在\(n_0\)，使得对于所有的\(n, n > n_0\)都有\(0 \leq f(n) < c g(n)\)

则记作\(f(n) = o(g(n))\)。

小ω

对于两个在任意正实数的无界子集上定义的关于\(n\)的实数或复数函数\(f(n)\)和实数函数\(g(n)\)

当且仅当对于任意正实数\(c\)都存在\(n_0\)，使得对于所有的\(n, n > n_0\)都有\(0 \leq c g(n) < f(n)\)

则记作\(f(n) = ω(g(n))\)。

小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和小ω仅在这里列出以供读者了解，现实当中几乎没有人使用这些符号。

\(\log\)

在计算机科学当中，除非特别声明，否则我们会默认\(\log\)的底数为2。

时间

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

常数时间

算法复杂度与问题规模无关的一般记为\(O(1)\)，这样的算法可以被称为常数时间。

现实当中常数时间可解的问题非常少，比如在一个HashSet当中寻找元素。

对数时间

\(O(\log n)\)一般被称作对数时间。

与常数时间相似，仅有很少的问题能在对数时间当中解决。因此这个命名也并不常用。

线性时间

我们一般将\(O(n)\)、\(O(n \log n)\)称作线性时间。

大多数算法的复杂度都为\(O(n)\)或者更高，因为一个算法一般需要\(O(n)\)来读取数据。

多项式时间

我们将复杂度为\(O(n^c), c > 1\)或更低的称作多项式时间。

多项式时间包含了此前提到的线性时间、对数时间和常数时间–事实上，多项式时间这个名词出现的概率也会比此前的三个要广泛得多。我们将可以在多项式时间内求解的问题称作多项式时间可解的问题，即P（polynomial）问题；将可以在多项式时间内验证一个解是否正确的问题称为非决定性多项式时间可解问题，即NP（nondeterministic polynomial）问题。有关这些问题的具体描述及NP困难（NP-hardness）问题和NP完全（NP-complete）问题，我们将在专门的章节进行讨论。

指数时间和阶乘时间

我们将把\(O(c^n), c > 1\)称作指数时间，将\(O(n!)\)称作阶乘时间。

当复杂度达到这个级别时，我们通常会认为这个算法是不可用的。

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

常数时间 线性时间 多项式时间 指数时间 阶乘时间
运算次数 1 3000 1000000 \(1.07 \times 10^{301}\) \(4.02 \times 10^{2568}\)

分析

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

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

Karatsuba

Python
 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

我们可以观察到，注释注明Repeat的三行代码是不断重复的，即每次分治将一个问题变成三个问题，同时每次分治问题的大小变为原来的一半。

最终，这个问题会转换为\(3^t\)个\(\frac{n}{2^t}\)个计算，那么复杂度即为\(O(3{^\log{_2}n})\)，也即\(O(n{^\log{_2}3})\)。

很简单，不是吗？