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

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

大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(logN)$。
• 线性阶$O(n)$。
• 线性对数阶$O(nlogN)$。
• 平方阶$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(logN)$。例如：

1
2
3
4

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

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

线性对数阶

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

1
2
3
4

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

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

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)$阶复杂度，所以如果一段代码是二方阶复杂度，或者三方阶复杂度且不过分要求时间，可以选择不进行优化。