算法复杂度

算法的效率如何分析呢？一种度量方式是当输入值具有一定规模时，计算机按此算法解题所花的时间。第二种度量方式是输入值具有一定规模时，实现这一算法计算机需要多大内存。

这些问题都涉及算法的计算复杂度(computational complexity) 。解决特定规模的问题所需时间的分析就是算法的时间复杂度。所需计算机内存的分析就是算法的空间复杂度。

基本操作

测定运行时间的最可靠方法就是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。

下表中列举了一些基本操作的例子。

程序	基本操作
排序一组整数	比较两个整数
把一个文件复制到另一个文件	复制一个字节
把两个多项式相加	把两个系数相加

在分析程序的运行时间时，重要的是把程序看成算法，即独立于实现它的程序设计语言的一系列步骤。

例子：多项式求值，在多项式求值中通常乘法比加法慢。因此，乘法是主导的基本操作。

输入规模

在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

算法	输入规模
排序	$n$ :要排序的整数的个数
文件复制	$n$ :输入文件中的字节数量
多项式加法	$n$ :第一个多项式的次数； $m$ ：第二个多项式的次数

时间复杂度

在输入具有一定规模时，算法的时间复杂度可以用算法所需的运算次数来表示。用于度量时间复杂度的运算可以是整数比较、整数加法、整数乘法、整数除法或任何其他基本运算。

注意

时间复杂度用所需运算次数而不是用计算机实际使用的时间来表示

例：求两个 $n$ 阶矩阵的乘积算法的时间复杂度，算法的 C 语言代码如下：

for(i=1; i<=n; i++) { 1
    for (j=1; j<=n; j++) { 2
        c[i][j] = 0; 3
        for(k=1; k<=n; k++) { 4
            c[i][j] = c[i][j] + a[i][k] * b[k][j]; 5
        }
    }
}
c

各步骤执行的基本操作次数如下：

①： $n + 1$
②： $n \times (n + 1)$
③： $n^2$
④： $n^2 \times (n + 1)$
⑤： $n^3$

所有步骤操作次数之和，就是算法执行的时间。我们用 $f(n)$ 来表示

f(n) = 2n^3 + 3n^2 +2n + 1

因此此算法的时间复杂度是 $\varTheta(x^2)$ 。

对于某些问题的算法，其基本语句的频度不仅仅与问题的规模相关，还依赖于其他因素。如从数组中查找一个元素的位置。

for (i = 0; i < n; i++) {
    if (arr[i] == e) { 1
        return i; 
    }
}
return -1;
c

可以看出 if 语句块（①）不仅与问题规模 $n$ 有关，还与元素的顺序有关。

① 如果要查找的元素在起始位置，那算法的复杂度就是 $O(1)$ ，
② 而如果元素在末尾，则算法的复杂度是 $O(n)$ ，
③ 现在我们假设，每个元素被查找的概率都是相同的，那么平均时间复杂度的计算如下：

第一个元素需要循环 $1$ 次，第二个元素 $2$ 次，依次类推，最后一个是 $n$ 次。所有元素都查询一次的总次数为 $\sum_{i =1}^{n} i$ ，而每次平均消耗的次数为

\frac{\sum_{i =1}^{n} i}{n} = \frac{\displaystyle\frac{1}{2}n(n+1)}{n} = \frac{1}{2}(n + 1)

因此平均时间复杂度为 $\varTheta(\displaystyle\frac{1}{2}n)$

提示

在本例中，我们只考虑 if 语句的比较，而不考虑 for 循环中 i 的自增操作。

最优时间复杂度（Best-case complexity） 描述了算法在最理想情况下的运行时间，即算法在最优输入情况下所需要的最少时间。了解最好时间复杂度可以帮助我们理解算法在最佳情况下的性能表现。（对应①）
最坏时间复杂度（Worst-case complexity） 表示在最不利的情况下，算法的运行时间。它是评估算法性能和确定其效率上界的重要指标。最坏情况运行时间函数常用 $T(n)$ 来表示。（对应②）
平均时间复杂度（Average-case complexity） 描述了算法在所有可能的输入情况下，运行时间的期望值。这种复杂度衡量了算法在一般情况下的性能，比最坏情况复杂度更能反映算法的实际效率。（对应③）

而对算法复杂度的度量，人们更关心的是最坏情况下的时间复杂度。很多情况下平均时间复杂度是难于确定的。

空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐近空间复杂度 (Space Complexity) 作为算法所需存储空间的量度，简称
空间复杂度。

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输人数据量而言是个常数，则称这个算法为原地工作，辅助空间为 $O(1)$ 。有的算法需要占用临时内存空间，一般与问题规模 $n$ 有关，如排序算法。

空间复杂度同样用大 $O$ 表示。

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间，即可能会使空间复杂度的性能变差，反之亦然。

典型运行时间的阶

典型的运行时间的阶有：常数阶、线性阶、二次阶、对数阶、三次阶、指数阶。

运行时间	阶	非正式术语
10	$O(1)$	常数
$3n+25$	$O(n)$	线性
$1.5n^2+25n-55$	$O(n^2)$	二次
$250n+10n\log{n} + 25$	$O(n\log{n})$	线性对数
$3\log{n}+30$	$O(\log{n})$	对数
$10n^3+2n$	$O(n^3)$	三次
$12 * 2^n$	$O(k^n)$	指数

阶的相对顺序

1 < \log{n} < \sqrt{n} < n < n\log{n}< n\sqrt{n}<n^2<n^3<k^n

参考资料

Kenneth H. Rosen. 《离散数学及其应用（原书第8版）》. 机械工业出版社. 2019: P183-P192
严蔚敏,李冬梅,吴伟民. 《数据结构（C语言版第2版）》. 清华大学出版社. 2015: P12-P16

基本操作​

输入规模​

时间复杂度​

空间复杂度​

典型运行时间的阶​

参考资料​