「数据结构」时间复杂度-如何分析、统计算法的执行效率

前言

数据结构和算法本身是为了解决“时间上的快”和“空间上的省”的问题，如何让代码运行得更快，如何让代码更省存储空间，是一个非常重要的考量标准。

为什么需要复杂度分析？而不是运行代码，通过统计、监控就可以得到算法执行的时间和占用的内存大小（称之为事后统计法）？

首先，通过代码运行统计确实是正确的，但是，测试结果依赖于测试环境，在不同的测试环境中得到的结果相差可能非常大。

其次，测试结果受数据规模的影响很大。如排序算法，极端情况下，如果数据已经是有序的，执行时间就会非常短。除此之外，如果测试数据规则太小，测试结果可能无法真实反应算法的性能。比如，对于小规模的数据排序，插入排序可能会比快速排序快。

大O复杂度表示法

那么，如何根据代码进行执行时间的估算呢？

首先，假设每行代码的执行时间都是一样的，然后进行统计。

如上图所示的代码中，总执行时间就是 1 + n + n = 1 + 2n 的执行时间。我们再来看一下下面这段代码。

总执行时间就是 1 + n + n*n + n*n = 1+ n + 2n^2。

根据上文所示中，我们可以得到一个规则。代码的执行时间T(n)与每行代码的执行次数n成正比。

也就是说： T(n） = O（f（n））

T(n) 表示代码执行时间

n表示数据规模大小

f(n)表示每行代码执行的次数总和

O表示代码执行时间T(n)与f(n)表达式成正比

所以，上图中的1 + n + n*n + n*n = 1+ n + 2n^2 即 T(n) = O(1+n+2n^2)。

这就是时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执 行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

前文中介绍了大O时间复杂度表示方法，那么，如何分析一段代码的时间复杂度呢？

#只关注循环次数最多的一段代码

大O时间复杂度表示法只是表示一种变化趋势，所以，通常情况下，会忽略公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数n的量级，就是整段代码要分析的时间复杂度。

再来看之前的一段代码

在大O时间复杂度表示法中，该代码的总执行时间就是 1 + n + n = 1 + 2n 的执行时间。1是常量级执行时间，与n的大小无关，所以对于复杂度并没有影响。2n中的系数2也是可以忽略的。所有，该代码的总时间复杂度就是O(n)。

#加法法则：总复杂度等于最级最大的那段代码的复杂度

首先，第一段代码中的时间复杂度就是O(n)，第二段代码的时间复杂度是 n + 2n^2 = O(n^2)。

综合这二段代码的时间复杂度，取其中大的量级。所以，整段代码的时间复杂度就是O(n^2)。

也就是说，总的时间复杂度就是等于量级最大的那段代码的时间复杂度。

#乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

如上图所示，单独看calc()方法，时间复杂度T1(n)=O(n)。但是由于nested()方法不是一个普通操作，nested()方法的时间复杂度T2(n)=O(n)。

所以，整体来看，calc()方法的总时间复杂度T(n) = T1(n) * T2(n) = O(n * n) = O(n^2)。

常见时间复杂度实例分析

复杂度中，O(2^n）与O(n!）中的n值越大，执行时间会急剧增加，效率非常低。正常需要进行避免。

#O(1)

常量级时间复杂度。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代 码，其时间复杂度也是Ο(1)。

#O(logn)、O(nlogn）

对数阶时间复杂度非常常见，同时也是Y难分析的一种时间复杂度。我通过一个例子来说明一

下。

<code>
i
=
1
while
 
( i <= n) {
  
i
 = 
i * 2;
}
/<code>

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数Y多的。所以，我们只要能计算

出这行代码被执行了多少次，就能知道整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还 记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一

个列出来，就应该是这个样子的：

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2 =n 求解 x 这个问题我 们想高中应该就学过了，我就不多说了。x=log n，所以，这段代码的时间复杂度就是 O(log n)。

现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少

<code>
i 
=
1
while
 
( i <= n) {
  
i
 = 
i * 3;
}
/<code>

根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为 O(log n)。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都 记为 O(logn)。为什么呢？

我们知道，对数之间是可以互相转换的，log n 就等于 log 2 * log n，所以 O(log n) = O(C * log n)，其中 C=log 2 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时 候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log n) 就等于 O(log n)。因此，在对数阶 时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

如果你理解了我前面讲的 O(logn)，那 O(nlogn) 就很容易理解了。还记得我们刚讲的乘法法则 吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间 复杂度都是 O(nlogn)。

#O(m+n)、O(m*n)-

我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模来决定。老规

矩，先看代码！

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以

我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时 间复杂度就是 O(m+n)。

<code>
int
 
cal(int m, int n) {   
  
int
 
sum_1 = 0;   
  
int
 
i = 1;   
  
for
 
(; i < m; ++i) {     
    
sum_1
 = 
sum_1 + i;   
    

  
  
int 
 
sum_2 = 0;   
  
int
 
j = 1;   
  
for
 
(; j < n; ++j) {     
    
sum_2
 = 
sum_2 + j;   
                         
return
 
sum_1 + sum_2; } 
/<code>

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

内容小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间

的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从 低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)