算法的复杂度分析

2019-03-30 本文已影响5人柳年思水

本文是对极客时间《数据结构与算法之美》03-04 节课关于算法复杂度分析的小结。

前面：为什么要学习数据结构与算法

内容来自《数据结构与算法之美》01-02 节的内容，当我们需要做大量 coding 工作时，必要的数据结构和算法基础是非常重要的，写完一段代码，很多时候是需要去思考：这个数据结构设计得合理不合理？这段代码是否还有优化空间？是不是可以用个设计模式让代码架构显得更简洁清晰？这些思考的背后都是需要相应的基础做为支撑，如果这些基础比较薄弱的话，还是应该每周抽出个 2-3h 来去定向地提高自己，有了相应的工作经验之后再去复习这些基础，理解效果可能会更深刻一些（与大家共勉）。

对于业务开发同学来说，平时更多的是利用已经封装好的现成接口、类库来堆砌、翻译业务逻辑，很少需要自己实现数据结构和算法，但是不需要自己实现，并不代表什么都不需要了解。

如果不了解其背后的原理，怎么能用好它们？出了问题怎么快速去定位问题？调用了某个函数之后，如何评估代码的性能和资源消耗呢？工作中，会用到各种框架、中间件和底层系统，在这些基础框架中，一般都糅合了很多基础数据结构和算法的设计思想。

比如：我们常用的 key-value 数据库 Redis 中，里面的有序集合是用什么数据结构来实现的呢？为什么要用跳表来实现呢？为什么不用二叉树呢？

掌握数据结构和算法，不管对于阅读框架源码，还是理解其背后的设计思想，都是非常有用的。

对于基础架构的研发同学来说，写出达到开源水平的框架才是应该是我们的目标。

现在互联网上的技术文章、架构分享、开源项目满天飞，照猫画虎做一套基础框架不是并不难。但不同做出的东西，差距非常大！
高手之间的竞争就在细节，这些细节包括：你用的算法是不是够优化，数据存取的效率够不够高，内存是不是够节省等等。这些累积起来，决定了一个框架是不是优秀。所以，如果你还不懂数据结构和算法，没听说过大 $O$ 复杂度分析，不知道怎么分析代码的时间复杂度和空间复杂度，那肯定说不过去了。

掌握了数据结构和算法，看待问题的深度，解决问题的角度就会完全不一样。

为什么要复杂度分析？

数据结构和算法本身解决的是【快】和【省】的问题，即如何让代码运行得更快、如何让代码更省内存空间。因此，执行效率是算法一个非常重要的考量指标，那么如何进行衡量呢？那就是——时间、空间复杂度分析。

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

把代码运行起来，通过统计和监控也能得到算法执行的时间和占用的内存大小。那为什么还要时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确么？

上面的评估方法是正确的，但它是事后统计法，这种方法的局限性很大：

测试结果非常依赖测试环境：比如不同的硬件环境的影响；
测试结果受数据规模的影响很大：比如，对于排序算法，待排序数据的有序度不一样排序的执行时间就会有很大差别。

因此，需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法，这就是时间、空间复杂度分析。

大 $O$ 复杂度分析法

一个算法的执行效率，简单来说，就是其算法的执行时间，如何从理论上进行分析呢？这就是这里要讲述的大 $O$ 复杂度分析法。

代码在运行时，从 CPU 的角度来说，其实都是读数据-运算-写数据，虽然每行代码执行时间并不一样（假设每行代码都是比较最简单的那种形式），但是在进行理论分析（粗略估计时），我们可以认为其是一样的，有了这个假设，那么：

一段代码的执行时间 $T(n)$ 与每行代码的执行次数 $n$ 成正比。

这里可以总结为一个公式：

$T(n) = O(f(n))$

这就是大 $O$ 复杂度分析，其中：

$T(n)$ ：代码的执行时间；
$n$ ：数据规模的大小；
$f(n)$ ：每行代码执行的次数总和。

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

时间复杂度分析

前面介绍了大 $O$ 时间复杂度的由来和表示方法，这里来看下如何分析代码的时间复杂度，这里有三个常用的方法：

只关注循环执行次数最多的一段代码；
加法原则：总复杂度等于量级最大的那段代码的复杂度；
乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

对于这三点，对于接触过这块内容的同学，其实是很容易理解的，这里就不再详细介绍，这里看下几种常见的时间复杂度实例分析。

复杂度量级 —— 图片来自极客时间

时间复杂度跟 n 的关系——图片来自极客时间

$O(1)$

$O(1)$ 并不是说代码执行一行，而是指代码执行了次数与 $n$ 无关，比如下面代码的时间复杂度就是 $O(1)$ ：

int a = 1;
int b = 2;
int c = a * b;

也就是说，只要代码不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 $O(1)$ 。

$O(logn)$ 、 $O(nlogn)$

对数阶的时间复杂度很常见，但是比较难以分析，下面有个示例：

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

这段代码到底执行多少次，只需要把 $2^k=n$ 中的 $k$ 找出来就行了，而 $k=log_2n$ ，如果乘以的是 3，那么结果就是 $k=log_3n$ ，也就是说其时间复杂度是 $O(log_2n)$ 、 $O(log_3n)$ 。

但是，由于 $log_3n=log_32 * log_2n$ ，所以不管是 $O(log_2n)$ 、 $O(log_3n)$ 、 $O(log_10n)$ ，这里都会统一记为 $O(logn)$ 。

$O(nlogn)$ 的例子也类似。

$O(m+n)$ 、 $O(m*n)$

对于这种类型，其复杂度是由两个数据规模来决定的，常见的示例就是有两个循环，一个是循环 $O(n)$ 次，一个是循环 $O(m)$ 次。

空间复杂度分析

有了前面关于时间复杂度的分析，这里的空间复杂度也类似，空间复杂度的全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 $O(1)$ 、 $O(n)$ 、 $O(n^2)$ 这种。

复杂度分析并不难、关键在于多练。

最好、最坏、平均、均摊时间复杂度

最好、最坏、平均情况时间复杂度

在分析时间复杂度时，很多情况下，其时间复杂度是有多种情况的，而为了表示在不同情况下的不同时间复杂度，这里引入了是三个概念：

最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度；
最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度；
平均情况时间复杂度：这种情况，需要考虑各种情况出现的概念，也称作加权平均时间复杂度。

一般来说，对于复杂度分析，这三种复杂度分析就足够了。

均摊时间复杂度

有种特殊的场景，其复杂度分析不需要像平均复杂度那样引入概率论去分析，而是引入了一个新的分析方法 —— 摊还分析法，分析的结果是均摊时间复杂度。

它对应的场景是：在绝大多数情况下是低级别复杂度，只有在极少数情况下是高级别复杂度；低级别和高级别复杂度出现具有时序规律。

举个例子：假设前 $n$ 个操作的复杂度都是 $O(1)$ ，第 $n+1$ 次操作的复杂度是 $O(n)$ ，所以把最后一次的复杂度均摊到前 $n$ 次上，那么均摊下来的每次操作复杂度为 $O(1)$ 。

总结：均摊时间复杂度就是一种特殊的平均时间复杂度，这里应该关注是其分析方法、分析思想。

算法的复杂度分析

前面：为什么要学习数据结构与算法

为什么要复杂度分析？

大 $O$ 复杂度分析法

时间复杂度分析