时间复杂度分析，这个很多人都不知道，更别谈会了！

太过爱你忘了你带给我的痛 2023-01-11 03:58 120阅读 0赞

## 时间复杂度 ##

请原谅我也是一个**标题党**！

关于时间复杂度和空间复杂度分析的文章其实不少，但大多数都充斥着复杂的数学计算，让很多读者感到困惑，我就不跟大家扯皮了，关于什么是渐近分析、最坏时间复杂度、平均时间复杂度和最好的时间复杂度，以及大记法等等，大家好好花点儿时间看看严老师的书就会了。

我们从代码和实现的层面讲讲，如何计算你写的代码的时间复杂度？

任何一门语言的逻辑结构无非三种：顺序结构、循环结构和分支结构，但是真正影响到时间复杂度只有循环结构，如果分支结构影响复杂度，也是因为分支内部包含了循环。

![format_png][]

循环的实现有 `for` 和 `while` 两种形式，但是本质都是一样的，我们接下来均以 `for` 循环进行说明。

如果一个函数（语句）不包含循环、迭代或非常数时间的函数，则可以认为函数为的时间。

// 非循环或者递归语句或函数
    int love = 520;

比如交换两个数的 `swap()` 函数的时间复杂度就是:

void swap(int *xp, int *yp) 
    { 
        int temp = *xp; 
        *xp = *yp; 
        *yp = temp; 
    }

一个循环如果仅仅运行常数次，那么时间复杂度也可以当作来处理：

// c 表示一个常量
    for(int i = 0; i < c; i++) {
        // O(1) 表达式
    }

如果循环控制变量 `i` 递增/递减的步长为一个常数，则认为循环的时间复杂度为。例如，以下函数的时间复杂度为：

// c 是一个正整数常量
    for(int i = 0; i < n; i += c) {
        // O(1) 表达式
    }
    -------------------------------
    for(int i = n; i > 0; i -= c) {
     // O(1) 表达式
    }

，嵌套循环的时间复杂度等于最内层语句的执行次数。例如，下面示例循环的时间复杂度为：

for (int i = 1; i <= n; i += c) {
        for (int j = 1; j <= n; j += c) {
      // O(1) 表达式
        }
    }
    
    for (int i = n; i > 0; i -= c) {
        for (int j = i+1; j <= n; j += c) {
      // O(1) 表达式
        }
    }

如果循环控制变量 `i` 乘以或除以一个常数，则循环的时间复杂度为量级：

// c 是一个正整数常量
    for(int i = 1; i < n; i *= c) {
        // O(1) 表达式
    }
    -------------------------------
    for(int i = n; i > 0; i /= c) {
     // O(1) 表达式
    }

简单地分析一下，循环控制变量到达的顺序为，如果我们令，那么，也就是循环到达 n 仅仅会执行次，复杂度自然为量级。

比如二分查找（binary search）的迭代实现的时间复杂度就是：

int binarySearch(int arr[], int l, int r, int x) 
    { 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
            if (arr[m] == x) 
                return m; 
    
            if (arr[m] < x) 
                l = m + 1; 
            else
                r = m - 1; 
        } 
        return -1; 
    }

如果循环控制变量 `i` 以指数级别增加或者减少，则时间复杂度为量级。

情况一：

for(int i = 2; i <= n; i = pow(i, k)) {
        // O(1) 表达式或语句
    }

这种情况下，`i` 的取值为  ，而最后一项一定小于等于，即  ，也就是说循环执行了次，每一次迭代的时间为常数时间，则上面的迭代总的时间复杂度为量级。

情况二：

// fun(i) 表示为 i 开方或者开立方
    for(int i = n; i > 0; i = fun(i)){
        // O(1) 表达式或语句
    }

`i` 的取值为， ，所以迭代总共执行次，时间复杂度为量级。

##### 如果程序中包含多个循环，又该如何时间复杂性？ #####

如果程序中存在多个连续循环时，时间复杂度为多个单循环的时间复杂度之和。

for (int i = 1; i <= m; i += c) {  
        // O(1) 表达式或语句
    }
    for (int i = 1; i <= n; i += c) {
        // O(1) 表达式或语句
    }

上面程序的时间复杂度为，当时，则，依旧是量级。

##### 如果循环内部包含大量的 `if...else...` 语句时，又该如何计算时间复杂度？ #####

在最好、平均和最差时间复杂度中，我们一般只关注最坏时间复杂度。考虑最坏的情况，当`if...else...` 条件中的语句导致执行时间复杂度的增加，就需要将其计算到最坏时间复杂度中。

int search(int arr[], int n, int x) 
    { 
        int i; 
        for (i = 0; i < n; i++) { 
            if (arr[i] == x) 
                return i; 
        } 
        return -1; 
    }

例如，考虑上面的线性搜索函数，其中我们考虑元素出现在数组 `arr[]` 的末尾或根本不存在的情况，分别对应和的时间复杂度，但是我们仅关注最坏的时间复杂度。

当代码太复杂而无法考虑所有 `if...else` 情况时，我们可以忽略 `if...else` 和其他复杂的控制语句来计算最坏情况下的时间复杂度。

##### 递归算法的时间复杂度又该如何计算？ #####

很多算法都是基于递归思想的，我们分析这些递归算法，可以得到关于时间复杂度的递归关系式。比如 [「归并排序」][Link 1] 的时间复杂度一般表示为，还有二分查找，汉诺塔问题等等，但是关于递归的时间复杂度并不简单。

对于递归的时间复杂度的计算主要有三种方式：

**一、代入法：先对解进行猜想，然后用数学归纳法证明猜想的正确性。**

已知，注意前面的系数；

又很容易得到和之间的关系式，即.

将与之间的关系式带入当中，就是将所有的替换为：

则，，注意

就得到了与之间的关系式，

同理，与之间的关系为：,

带入，得到和之间的关系式；

，注意

以此类推...

可以推知与之间的关系：

∴ 归并排序的时间复杂度为量级。

**二、主定理**

令和是常数，是一个函数，是定义在非负整数上的递归式：

其中我们将解释为或，那么有如下渐近界：

1.  若对某个常数有，则.
2.  若，则.
3.  若对某个常数有，且对某个常数和所有足够大的有，则.

主定理对递归式所提供的一种 “菜谱式” 的求解方法，关于主定理的证明就不在这里解释了，感兴趣可以看一下 《算法导论》4.6 节的主定理的证明。

我们这里直接 “下菜“ 即可。

已知；

首先和对应起来

、、

则

∴  .

即归并排序的时间复杂度为.

**三、递归树**

在该方法中，我们绘制了一棵递归树，并计算了树的每一层所花费的时间。最后，我们总结了各级所做的工作。为了绘制递归树，我们从给定的递归开始，不断绘制，直到在级别之间找到一个模式。通常是算术或几何级数。

以递归关系为例，其递归树可以表示为：

![format_png 1][]

我们进一步打开表达式  ，以及表达式  :

![format_png 2][]

继续把  ， 拆分。

而为了计算，则需要一层一层地将树中的所有结点累加起来，即：

上面序列的几何级数的系数为 5/16，为了获得上限，我们可以无限趋近于无穷大，获得，时间复杂度为量级。

是不是被这种方法搞得晕晕乎乎，没关系，这属于了解内容，当然想深究的可以看看算法导论。

你该不会到这里就结束了吧！

其实计算算法的时间复杂度还有一种方法，就是根据题型去判断计算：

<table> 
 <thead> 
  <tr> 
   <th>题型</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数组、动态规划</td> 
   <td><code>for</code> 循环执行次数</td> 
  </tr> 
  <tr> 
   <td>链表</td> 
   <td><code>while</code> 循环执行次数</td> 
  </tr> 
  <tr> 
   <td>栈、队列</td> 
   <td>栈或者队列的大小</td> 
  </tr> 
  <tr> 
   <td>二叉树</td> 
   <td>结点个数</td> 
  </tr> 
  <tr> 
   <td>回溯法、BFS/DFS</td> 
   <td>元素个数 O(n)</td> 
  </tr> 
  <tr> 
   <td>二分查找</td> 
   <td>log(n)</td> 
  </tr> 
  <tr> 
   <td>分治法</td> 
   <td>log n （归并排序、快速排序）</td> 
  </tr> 
 </tbody> 
</table>

当然这也只是一个比较粗略的概括，时间复杂度的分析无定法，仅仅是大家的一个共识而已，最好的方法是，将你的代码结合数据跑起来，计算它的运行时间，但是这也需要大家规定设备的型号和运行内存等等硬件。

谁说深究不是一种品质呢？如果你真的对时间复杂度和空间复杂度感兴趣，那就研究下去！！！

**推荐阅读：**

[一道 LeetCode 周赛的题目，让我自信满满！][LeetCode]

[LeetCode 全站第一，牛逼！][LeetCode 1]

[format_png]: /images/20221119/3d304d9fa8de4939933d21008608ff41.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA%3D%3D&idx=2&mid=2647522698&scene=21&sn=c933a80e36743389ae812ad9509f59cb#wechat_redirect
[format_png 1]: /images/20221119/f10201bf579a4fdd9ddc854754945d25.png
[format_png 2]: /images/20221119/1ad25a3f79204a96b3929bed76c27840.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d9741cd7a1e57f51fea06a3fce8a51958edd6796872099d88c022ef829d4a79f0b644573e&idx=1&mid=2247497920&scene=21&sn=2ac76d76fe0424b2e99ed22a74e4f3ca#wechat_redirect
[LeetCode 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d9701cd7a1e17dff4816fe0bdc7aff009b060269e0ccde010d224bddc078f3beb5f4a691a&idx=1&mid=2247497856&scene=21&sn=6bf63f8f7ced8e634185691a1949f026#wechat_redirect