11.1　时间复杂度

在讲解常用算法之前，不得不提的一个概念就是时间复杂度，它是用来衡量一个算法优劣的重要指标。下面就来介绍什么是时间复杂度以及如何计算时间复杂度。

提到时间复杂度，不得不提一下语句频度，它指的是算法中每条语句被执行的次数。如果这样简单地讲解不够明朗，那么通过一段代码具体介绍什么是语句频度，看看下面的代码。

for（i=0；i＜n；i++）

a+=1；

在上面的代码中，a+=1总共被执行了n次，所以a+=1语句的语句频度为n。

时间复杂度指的是算法所需的执行时间，而算法的执行时间就是代码中每条语句执行时间的总和，记为T（n），其中，参数n是问题规模，当n变化时，T（n）也会随之变化。

还有一个概念不得不提，那就是渐进时间复杂度，它指的是当表示问题规模的n值趋于无穷大时的时间复杂度，将其记做：T（n）=O（f（n）），其中，f（n）和T（n）是同数量级的，即当n趋向于无穷大的时候，T（n）/f（n）的极限值为非零常数。因此，f（n）越大，所对应的时间复杂度就越大，而f（n）的取值通常用执行语句中语句频度最大的值的数量级来描述。如果代码中某条语句的语句频度最大，其值为3n⁴+6n+9，那么f（n）的取值就为其数量级n⁴。

由于在实际运行中算法执行时间受多方面因素的影响，不可能得到精确的计算时间，加之，引入时间复杂度的目的仅仅是为了对比算法的优劣性，并不是要计算出算法实际的运行时间，只需要知道哪种算法在执行时间上有优势即可。因此在计算时间复杂度时采用的都是理想情况，假设每条语句每次的执行时间完全一致，都为单位时间，算法的执行时间等于所有被执行语句的语句频度之和乘以执行每条语句所需的单位时间。由于单位时间都是一样的，因此对比时间复杂度就转换为对比算法中所执行语句的语句频度之和。在实际对比算法的时间复杂度时，主要参照标准是算法的渐近时间复杂度，对比其中的f（n）的大小，因此经常将渐近时间复杂度T（n）=O（f（n））简称为时间复杂度。接下来通过代码示例介绍如何计算渐进时间复杂度。

示例1：

for（i=0；i＜n；i++）

{

a+=i；

for（j=0；j＜n；j++）

{

b+=i+j；

}

}

在上面的代码中使用了一个二重循环，要想知道该算法的时间复杂度，就需要找出该语句中语句频度最大为多少。由于a+=i语句的语句频度为n，而b+=i+j的语句频度为n的平方，因此可以将其时间复杂度表示为T（n）=O（n^2）。

示例2：

for（i=0；i＜n；i++）

for（j=0；j＜n；j++）

for（k=0；k＜n；k++）

sum+=1；

从上面的三重循环中可以看出，语句频度最大的语句是sum+=1，其值为n³，所以，可以将其时间复杂度表示为T（n）=O（n³）。适当地修改上面的代码，得到的代码如下：

示例3：

for（i=1；i＜=n；i++）

for（j=1；j＜=i；j++）

for（k=1；k＜=j；k++）

sum+=1；

在上面的代码中，仅对内层循环做了简单的修改，此时的三重循环的时间复杂度又是多少呢？当最外层循环中i值为1时，sum+=1被执行了1次，当i值为2时，sum+=1被执行了1+2次，依此递推，当i值为n时，sum+=1被执行了1+2+……+n次，由此可以得出sum+=1的语句频度为1+（1+2）+（1+2+3）+……+（1+2+3+……+n）=n（n+1）（n+2）/6，所以其时间复杂度可表示为T（n）=O（n³）。

对比上面代码的时间复杂度可以发现，对于多重循环语句，其时间复杂度主要由最内层循环体中的语句来决定。同时在使用时间复杂度的时候需要注意的一点就是，渐进估计是对算法的理论分析和大致比较，并不能够准确表示算法之间的关系。对于上面的示例2和示例3，它们的时间复杂度都是T（n）=O（n³），但是通过代码可知它们实际的执行时间并不相同；还有就是时间复杂度为O（n²）算法在n较小的情况下可能比时间复杂度为O（nlogn）的算法运行得更快。当然，随着n值的增大，复杂度变化较慢的算法必然工作得更快。

对于常见的时间复杂度，按数量级递增排列可依次表示为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n²）、立方阶O（n³）、指数阶O（2ⁿ）、阶乘O（n！）、n次方阶O（nⁿ）。它们之间的大小关系如下：

O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n²）＜O（n³）＜O（2ⁿ）＜O（n！）＜O（nⁿ）

从上面的大小关系中发现，基本满足这样一个关系：

常数＜对数＜多项式＜指数