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

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

大O符号表示法

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

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

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

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

常见时间复杂度量级

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

• 常数阶。
• 对数阶。
• 线性阶。
• 线性对数阶。
• 平方阶。
• 立方阶。
• K方阶。
• 指数阶。
• 组合阶。

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

O(1)

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

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

O(n)

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

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

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

O(logN)

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

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

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

O(nlogN)

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

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

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

O(n)、O(n)和O(n)

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

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

在这个示例中使用了一个三层的循环，所以这段代码的复杂度就应该是，简化以后就是。

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