ArchGrid - 架构知识网格

时间复杂度是我们衡量和筛选算法的一个常用考量维度，如何理解并使用它，是我们日常工作学习中常常会用到的，但是只要一段时间不用它是会很快被忘记的。所以这里把时间复杂度的概念简要记录一下，方便使用的时候能够快速恢复记忆。

对于算法的衡量一般是从两个维度进行的，一是空间维度，即算法执行所需要占据的内存空间；一是时间维度，即算法执行所需要的时间。时间与空间往往不能兼得，我们很难设计一个既使用很小的空间又能迅速执行的算法，所以在面临时间与空间的选择时，我们往往会选择更加宝贵的时间，毕竟一根内存条还是有价的。

大O符号表示法

对于时间复杂度的衡量，我们最常见的就是使用大O符号表示法，例如 $O (1)$ 、 $O (n)$ 等。之所以采用这样的方式衡量，是因为在不同配置的计算机上，相同的算法代码所呈现出来的性能也不尽相同。所以引入大O符号表示法可以使算法执行所消耗的时间标准化，更加易于对比。

大O符号表示法的完整格式是 $T (n) = O (f (n))$ ，这个函数表示的是代码执行次数与所使用时间之间的正比例关系。其中 $f (n)$ 表示算法中每行代码执行次数的和， $O ()$ 表示一个正比例关系。所以大O符号表示法所表示的是算法执行时间的增长变化趋势的，而不是算法实际的执行时间。在使用大O符号表示法的时候，我们一般会假设算法中每一行代码的执行时间都是一样，也就是一个单位时间会运行一行代码，这样我们就能够方便的计算 $f (n)$ 了。

在 $f (n)$ 中，如果 $n$ 趋近 $+ \infty$ ，那么 $f (n)$ 中所有的常量都将变得没有意义，所以常用 $T (n) = O (n)$ 来表示实际的时间复杂度。在这种简化的表示形式下，如果 $O (n)$ 中的 $n$ 变化越剧烈，则说明时间复杂度越大，例如 $n^{3}$ 就比 $n$ 的变化要剧烈的多，所以 $T (n) = O (n^{3})$ 就表示随着代码量的增长，算法所消耗的时间以代码量增长速度的三次方速度增长，这足以看出这个算法的时间复杂度。

大O符号表示法从来都不是一个精确的表示法，不要用它来做精确的计算。

常见时间复杂度量级

一般在代码设计中常常出现的时间复杂度量级主要有以下这些：

常数阶 $O (1)$ 。
对数阶 $O (l o g N)$ 。
线性阶 $O (n)$ 。
线性对数阶 $O (n l o g N)$ 。
平方阶 $O (n^{2})$ 。
立方阶 $O (n^{3})$ 。
K方阶 $O (n^{k})$ 。
指数阶 $O (2^{n})$ 。
组合阶 $O (n!)$ 。

以上这些复杂度量级从上到下所表示的复杂度越来越大，执行效率也越来越低。下面就一些示例来说明不同形式的代码其时间复杂度的量级。

常数阶

代码中没有循环结构，无论执行多少行，代码所消耗的时间始终固定，不随着某个变量的操作发生变化，其复杂度就是 $O (1)$ 。例如：

1
2
3
4


i = 1
j = 2
i += 1
j += 2

线性阶

代码中只有一层循环结构，没有任何嵌套的循环结构，代码执行所消耗的时间只与循环控制变量线性相关，那么这段代码的复杂度就是 $O (n)$ 。例如：

1
2
3


j = 0
for i in range(1000):
    j += i

在线性阶 $O (n)$ 中，每个单位时间中算法能够处理的变量数量是固定的，算法所处理的变量数量随时间线性增长。这一点需要牢记，否则将难以理解对数阶。

对数阶

代码中同样只有一层循环结构，没有任何嵌套的循环结构，但是代码执行所消耗的时间与循环控制变量指数相关，那么这段代码的复杂度就是 $O (l o g N)$ 。例如：

1
2
3
4


n = 100
i = 1
while i < n:
    i *= 2

在这段代码中，循环不是线性的，循环在 $2^{n}$ 次之后就会退出，所以这段代码的时间复杂度就是 $O (l o g 2^{n})$ ，所以可以简化表示为 $O (l o g N)$ 。对数阶量级主要表示随着时间的增加，所处理的n是以指数方式增加的情况。在这个方面，二叉树检索等算法都属于对数阶量级，这个量级的复杂度要比线性阶轻量。

线性对数阶

线性对数阶量级中就已经开始出现多层的循环结构了，在复杂度为 $O (n l o g N)$ 量级的代码中，有两层循环结构，其中一层为 $O (n)$ 量级的循环，一层为 $O (l o g N)$ 量级的循环。例如：

1
2
3
4


for i in range(10000):
    n = 1
    while n < i:
        n *= 2

在这种嵌套的循环结构中，其复杂度的计算方法是各层的复杂度相乘，即： $O (n) \times O (l o g N)$ ，这样相乘所得到的结果就是 $O (n l o g N)$ 。比较常见的快速排序算法的复杂度就是线性对数阶。

K方阶

从线性对数阶量级中可以看出，多层循环在进行嵌套的时候，算法复杂度也是逐步相乘的，所以 $O (n^{2})$ 、 $O (n^{3})$ 和 $O (n^{k})$ 这三个量级就十分容易理解了。K方阶量级中的指数 $k$ 可以直接认为代码中做了 $k$ 层的循环。例如：

1
2
3
4


for i in range(1000):
    for j in range(2000):
        for k in range(3000):
            n *= 2    # 不要真的去运行，计算机会炸的

在这个示例中使用了一个三层的循环，所以这段代码的复杂度就应该是 $O (i) \times O (j) \times O (k)$ ，简化以后就是 $O (n \times n \times n) = O (n^{3})$ 。

但一段代码使用了K方阶量级的复杂度以后，一般就说明这段代码需要进行优化了，并且K方阶的代码在一般情况下总可以找到低复杂度的优化实现。但我们一般所常用的排序算法大多是 $O (n^{2})$ 阶复杂度，所以如果一段代码是二方阶复杂度，或者三方阶复杂度且不过分要求时间，可以选择不进行优化。

时间复杂度

大O符号表示法

常见时间复杂度量级

常数阶

线性阶

对数阶

线性对数阶

K方阶

索引标签