算法概念公式大全（掌握这些数学函数）(1)

如何进行算法分析呢？

最简单方法是分别运行解决同一个问题的两个算法进行比较，但这样做法在很多时候并不理想。面对这样的困难迫使我们求助于数学工具，虽然我们不能对一个还没有完整实现的程序使用运行比较法，但却能通过数学分析了解程序性能的大致轮廓并预估改进版本的有效性。

大多数算法都有影响运行时间的主要参数 N，这里的 N 是所解决问题的大小的抽象度量，比如对于一个排序算法来说，N 是待排序元素的个数。我们的目标是尽可能地使用简单的数学公式，用 N 表达出程序的运行效率。

函数的增长

对于将要比较的两个算法，我们并不满足于简单地描述为“一个算法比另一个算法快”，而是希望能够通过数学函数直观地感受到二者的差异，具体来说，是希望知道“一个算法比另一个算法快多少”。

一些函数在算法分析中极为常见：

  1. 1。如果程序中的大多数指令只运行 1 次或几次，与问题的规模无关，我们就说程序运行的时间是常量的。小高斯的算法就是典型的常量时间。
  2. lg⁡N。随着问题规模的增长，程序运行时间增长较慢，可以认为程序的运行时间小于一个大常数。虽然对数的底数会影响函数的值，但影响不大。鉴于计算机是 2 进制的，所以通常取 2 为底数，lg⁡N=log2(⁡N)，这与数学中略有差别（数学中 lg⁡N=log10⁡(N)）。当 N=1024 时，lg⁡N=10；当 N 增长了 10 倍时，lg⁡N≈13，仅有略微的增长；只有当 N 增长到 N^2 时，lg⁡N 才翻倍。如果一个算法是把一个大问题分解为若干个小问题，而每个小问题的运行时间是常数，那么我们认为这个算法的运行时间是 lg⁡N，二分查找就其中的典型。
  3. √N。比 lg⁡N 稍大，当问题规模翻倍时，运行时间比翻倍少一点；当 N 增长了 100 倍时，程序运行时间增长 10 倍。开销是 √N 时间的程序通常对程序的终止条件做了处理，比如 ，在判断一个数是否是素数时，边界值是这个数的平方根，而不是这个数本身。
  4. N。这就是通常所说的线性时间，如果问题规模增大了 M 倍，程序运行时间也增大 M 倍。1 到 100 的蛮力求和法就是线性时间，这类方法通常带有一个以问题规模为终点的循环。
  5. N lg⁡N。当问题规模翻倍时，如果运行时间比翻倍多一点，我们就简单地说程序运行的时间是 N lg⁡N。当 N=1024 时，N lg⁡N=10240；如果 N=2048 ，N lg⁡N=22528。N lg⁡N 与 lg⁡N 都是把一个大问题分解为若干个能过在常数时间内运行的小问题，区别在于是否需要合并这些小问题，如果合并，就是 N lg⁡N；如果不合并，就是 lg⁡N。大多数归并问题的运行时间可以简单地看作 N lg⁡N。
  6. N²。如果问题规模翻倍，运行时间增长 4 倍；问题规模增长 10 倍，运行时间增长 100 倍。
  7. N³。如果问题规模翻倍，运行时间增长 8 倍；问题规模增长 10 倍，运行时间增长 1000 倍。
  8. 2^N。真正要命的增长。如果 N=10，2^N=1024；N 翻倍后，2^N=1048576。复杂问题的蛮力法通常具有这样的规模，这类算法通常不能应用于实际。

来看一下这些函数的增长曲线，如图 1 所示。

算法概念公式大全（掌握这些数学函数）(2)

▲ 图 1 函数增长的曲线

以上函数能够帮助我们直观地理解算法的运行效率，让我们很容易区分出快速算法和慢速算法。大多数时候，我们都简单地把程序运行的时间称为“常数”、“线性”、“平方次”等。对于小规模的问题，算法的选择不那么重要，一旦问题达到一定规模，算法的优劣就会立马体现出来。代码 4-2 展示了当问题规模是 10、100、1000、10000、100000、1000000 时 lg⁡N 、√N 、N、N lg⁡N 、N² 、N³ 的增长规模。

▼代码 2 函数的增长规模 C4_2.py

01importmath 02 03fun_list=['lgN','sqrt(N)','N','NlgN','N^2','N^3']#函数列表 04print(''*10,end='') 05forfinfun_list: 06print('%-15s'%f,end='') 07print('\n','-'*100) 08 09N_list=[10**nforninrange(7)]#问题规模 10forNinN_list:#函数在不同问题规模下的增长 11print('%-8s%-2s'%(N,'|'),end='') 12print('%-15d'%round(math.log2(N)),end='') 13print('%-15d'%round(math.sqrt(N)),end='') 14print('%-15d'%N,end='') 15print('%-15d'%round(N*math.log2(N)),end='') 16print('%-15d'%N**2,end='') 17print(N**3)

运行结果如图 4.2 所示。

算法概念公式大全（掌握这些数学函数）(3)

图 2 告诉我们，该问题规模是 1 的时候，所有算法都同样有效，问题规模越大，不同复杂度的算法运行效率相差得越大。

2^N 增长得太过迅猛，作为一个另类单独列出。

▼ 代码 3 2^N 的增长

01forNinrange(10,110,10): 02print('2**{0}={1}'.format(N,2**N))

运行结果如图 3 所示。

算法概念公式大全（掌握这些数学函数）(4)

▲ 图 4.3 2^N 的增长

这些运行结果告诉我们，有些时候，选择正确的算法是解决问题的唯一途径。对于函数的输出结果来说，如果把 100 看作 1 秒，那么 10000 就是 100 秒，超过 1 分半。这意味着对于一个规模是 1000000 的问题来说，一个是 lg⁡N 复杂度的算法可以立刻得出结果，√N 复杂度的算法耗时约 10 秒，N 复杂度的算法耗时将超过 2.7 小时，N^3 复杂度则需要 3 万多年！也许我们可以忍受一运行 10 秒或 2.7 小时的程序，但一定没法容忍有生之年看不到结果的程序。

算法概念公式大全（掌握这些数学函数）(5)

上文 [遇见] 授权节选自北大出版社《程序员数学从零开始》

270余幅插图 90余段Python代码 20余个原理剖析，教你学会程序员必须掌握的数学及算法背后的数学原理。

,