dsfds' blog

学海无涯，回头是岸

0%

算法复杂度分析

发表于 更新于 分类于 ， Valine：

以下内容为了极客时间专栏『数据结构与算法之美』的学习笔记。

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率和数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。

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

具体的时间复杂度分析，有下面几个比较实用的方法：

  • 只关注循环次数执行最多的一段代码

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

    如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))。

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

    如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))。

1.1 几种常见的时间复杂度实例分析

可以分为多项式量级和非多项式量级，把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。

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

  • O(logn)、O(nlogn)：

1
2
int i=1;
while (i <= n) i = i * 2;
  • O(m+n)、O(m*n)

1.2 空间复杂度分析

类比时间复杂度，空间复杂度的全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。一般情况下，很少去分析空间复杂度，因为在现在的硬件条件下，绝大多数时候，我们更加在乎时间复杂度，常常牺牲一部分空间复杂度去降低算法的时间复杂度。

1.3 Q：我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？

我不认为是多此一举，渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对我们的程序或算法有一个大致的认识，让我们知道，比如在最坏的情况下程序的执行效率如何，同时也为我们交流提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是 O(n)，算法2的时间复杂度是 O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。

当然，渐进式时间，空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得 O(logN) 的算法一定优于 O(n), 针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下的最有算法。

综上所述，渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。

2.1 最好、最坏时间复杂度分析

同样一段代码在不同的数据输入情况下，所需的时间可能是不相同，因此需要针对不同的输入进行复杂度分析，也就有了最好、最坏和平均情况时间复杂度分析

  • 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
  • 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

一般情况下，我们都不会去关注最好情况时间复杂度，因为它没有什么意义，最坏情况时间复杂度明确给出了算法的复杂度上界，这个信息在实际工程中是非常重要的。

2.2 平均情况时间复杂度

虽然最坏时间复杂度对于工程的指导非常重要，但是这种情况出现的概率也很小，因此我们有必要对平均情况下的复杂度进行分析，即平均情况时间复杂度分析。平均情况时间复杂度的分析关键在于对每种输入的概率进行考虑，对每种输入下的时间复杂度进行一个概率加权，然后再把加权后的结果加起来，作为最终的平均情况时间复杂度。

看起来很复杂，但实际上只要我们知道了输入的分布，这都不是什么难事儿，无非是一个加权积分或者加权求和的事儿，路径是很清晰的，就是计算可能会很麻烦，还好实际使用中，我们只粗略关注时间复杂度即可，并不区分的这么细。

2.3 均摊时间复杂度

均摊时间复杂度，听起来和平均情况时间复杂度有点像，事实确实如此，均摊时间复杂度就是一种特殊的平均时间复杂度。均摊时间负责度分析起来更加简单，用不着去进行概率加权求和，针对一些特殊的场景：

  • O(1) 出现的频率远高于 O(n)
  • O(1) 和 O(n) 出现的时机有规律，一般是执行一个 O(n) 操作，紧接着执行 n-1 个 O(1) 操作。

我们引入更加简单的分析方法：摊还分析，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。

由于这种分析方法的应用场景比较少，一般情况下并不会用到，这里简单列出：

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。