掌握这些数学函数，你会在算法效率的分析时经常用到 _函数

文章插图

如何进行算法分析呢？
最简单方法是分别运行解决同一个问题的两个算法进行比较，但这样做法在很多时候并不理想。面对这样的困难迫使我们求助于数学工具，虽然我们不能对一个还没有完整实现的程序使用运行比较法，但却能通过数学分析了解程序性能的大致轮廓并预估改进版本的有效性。
大多数算法都有影响运行时间的主要参数 N，这里的 N 是所解决问题的大小的抽象度量，比如对于一个排序算法来说，N 是待排序元素的个数。我们的目标是尽可能地使用简单的数学公式，用 N 表达出程序的运行效率。
函数的增长对于将要比较的两个算法，我们并不满足于简单地描述为“一个算法比另一个算法快”，而是希望能够通过数学函数直观地感受到二者的差异，具体来说，是希望知道“一个算法比另一个算法快多少” 。
一些函数在算法分析中极为常见：

1 。如果程序中的大多数指令只运行 1 次或几次，与问题的规模无关，我们就说程序运行的时间是常量的。小高斯的算法就是典型的常量时间。
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，二分查找就其中的典型。
√N 。比 lg?N 稍大，当问题规模翻倍时，运行时间比翻倍少一点；当 N 增长了 100 倍时，程序运行时间增长 10 倍。开销是 √N 时间的程序通常对程序的终止条件做了处理，比如，在判断一个数是否是素数时，边界值是这个数的平方根，而不是这个数本身。
N 。这就是通常所说的线性时间，如果问题规模增大了 M 倍，程序运行时间也增大 M 倍。1 到 100 的蛮力求和法就是线性时间，这类方法通常带有一个以问题规模为终点的循环。
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 。
N2 。如果问题规模翻倍，运行时间增长 4 倍；问题规模增长 10 倍，运行时间增长 100 倍。
N3 。如果问题规模翻倍，运行时间增长 8 倍；问题规模增长 10 倍，运行时间增长 1000 倍。
2^N 。真正要命的增长。如果 N=10，2^N=1024；N 翻倍后，2^N=1048576 。复杂问题的蛮力法通常具有这样的规模，这类算法通常不能应用于实际。

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

文章插图

▲ 图 1 函数增长的曲线
以上函数能够帮助我们直观地理解算法的运行效率，让我们很容易区分出快速算法和慢速算法。大多数时候，我们都简单地把程序运行的时间称为“常数”、“线性”、“平方次”等。对于小规模的问题，算法的选择不那么重要，一旦问题达到一定规模，算法的优劣就会立马体现出来。代码 4-2 展示了当问题规模是 10、100、1000、10000、100000、1000000 时 lg?N 、√N 、N、N lg?N 、N2 、N3 的增长规模。
▼代码 2 函数的增长规模 C4_2.py
01 import math0203 fun_list = ['lgN', 'sqrt(N)', 'N', 'NlgN', 'N^2', 'N^3'] # 函数列表04 print(' ' * 10, end='')05 for f in fun_list:06 print('%-15s' % f, end='')07 print('\n', '-' * 100)0809 N_list = [10 ** n for n in range(7)] # 问题规模10 for N in N_list: # 函数在不同问题规模下的增长11 print('%-8s%-2s' % (N, '|'), end='')12 print('%-15d' % round(math.log2(N)), end='')13 print('%-15d' % round(math.sqrt(N)), end='')14 print('%-15d' % N, end='')15 print('%-15d' % round(N * math.log2(N)), end='')16 print('%-15d' % N ** 2, end='')17 print(N ** 3)