复杂度分析的套路及常见的复杂度

﹏ヽ暗。殇╰゛Y 2023-03-01 12:25 34阅读 0赞

![file][]

# 前言 #

> 本篇文章收录于专辑：[http://dwz.win/HjK][http_dwz.win_HjK]，点击解锁更多数据结构与算法的知识。

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节，我们一起学习了表示复杂度的几个符号，我们说，通常使用大O来表示算法的复杂度，不仅合理，而且书写方便。

那么，使用大O表示法评估算法的复杂度有没有什么套路呢？以及常见的复杂度有哪些呢？

本节，我们就来解决这两个问题。

# 前情回顾 #

在正式讲解套路之前，我们先回忆一下前面几节讲到的内容。

在第2节，我们学习了渐近分析法，将算法的复杂度与输入规模挂钩，随着输入规模的增大，算法执行的时间将呈现一种什么样的趋势，将这个趋势用函数表示，再去除低阶项和常数项，就得到了算法的时间复杂度。

在第3节，我们分别从最坏、平均、最好三种情况来分析了算法的复杂度，得出结论，一般使用最坏情况来评估算法的复杂度。

在第4节，我们通过动态数组的插入元素及经典快速排序的时间复杂度，解释了有的时候不能使用最坏情况来评估算法的复杂度。

在第5节，我们从读音、数学、通俗理解三个方面分析了各种表示算法复杂度的符号，得出结论还是使用大O比较香，大O代表了算法的上界，它与前面讲到的最坏情况往往是对应的。

所以，这里所说的套路也是针对大部分情况，也就是最坏情况，对于一些个例，比如经典快排，我们虽然也是使用大O表示他们的复杂度，但是，其实是一种均摊的复杂度。

好了，让我们看看计算算法复杂度的套路到底是什么吧。

# 套路 #

我将计算算法复杂度的套路归纳为以下五步：

1.  明确输入规模n；
2.  考虑最坏情况或均摊情况，如果最坏情况为个例，那就是均摊；
3.  计算算法执行的次数与n的关系，并用函数表示出来；
4.  去除低阶项；
5.  去除常数项；

比如，对于在数组中查找指定元素的操作：

1.  输入规模为数组的长度n；
2.  考虑最坏情况为目标元素不在数组中；
3.  算法的执行次数为遍历所有数组元素，也就是n次，用函数表示f(n) = n；
4.  去除低阶项，没有低阶项，还是n；
5.  去除常数项，没有常数项，还是n；

所以，在数组中查找指定元素的时间复杂度为O(n)。

OK，使用这种方式可以很快的计算出算法的复杂度，也不需要进行额外的计算，非常快捷高效。

# 常见的复杂度 #

上面我们说了，复杂度的计算就是计算与输入规模n的关系，所以，我们想想数学中关于n的函数就能得出常见的复杂度了，我绘制了一张表格：

<table> 
 <thead> 
  <tr> 
   <th>与n的关系</th> 
   <th>英文释义</th> 
   <th>复杂度</th> 
   <th>示例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>常数（不相关）</td> 
   <td>Constant</td> 
   <td>O(1)</td> 
   <td>数组按索引查找元素</td> 
  </tr> 
  <tr> 
   <td>对数相关</td> 
   <td>Logarithmic</td> 
   <td>O(logn)</td> 
   <td>二分查找</td> 
  </tr> 
  <tr> 
   <td>线性相关</td> 
   <td>Linear</td> 
   <td>O(n)</td> 
   <td>遍历数组的元素</td> 
  </tr> 
  <tr> 
   <td>超线性相关</td> 
   <td>Superlinear</td> 
   <td>O(nlogn)</td> 
   <td>归并排序、堆排序</td> 
  </tr> 
  <tr> 
   <td>多项式相关</td> 
   <td>Polynomial</td> 
   <td>O(n^c)</td> 
   <td>冒泡排序、插入排序、选择排序</td> 
  </tr> 
  <tr> 
   <td>指数相关</td> 
   <td>Exponential</td> 
   <td>O(c^n)</td> 
   <td>汉诺塔</td> 
  </tr> 
  <tr> 
   <td>阶乘相关</td> 
   <td>Factorial</td> 
   <td>O(n!)</td> 
   <td>行列式展开</td> 
  </tr> 
  <tr> 
   <td>n的n次方</td> 
   <td>无</td> 
   <td>O(n^n)</td> 
   <td>不知道有没有这种算法</td> 
  </tr> 
 </tbody> 
</table>

在这张表中，复杂度是依次增加的，可以看到常数复杂度O(1)无疑是最好的，让我们用一张图来直观感受下：

![file][file 1]

# 后记 #

本节，我们一起学习了复杂度分析的套路以及常见的复杂度，到目前为止，我们不管是举例还是讲解基本上都在说时间复杂度。

那么，空间复杂度又是什么呢？空间与时间之间如何权衡呢？

下一节，我们接着聊。

> 关注公号主“彤哥读源码”，解锁更多源码、基础、架构知识。

![file][file 2]

[file]: /images/20230208/9a75c3e796234c50aa1d0985be02c28d.png
[http_dwz.win_HjK]: http://dwz.win/HjK
[file 1]: /images/20230208/b762f1698893464f922e4bc9308e4147.png
[file 2]: /images/20230208/9aa1f2432bf74b9aa01c9d60d517a11c.png