算法妙应用-算法的复杂度

算法词云.png

0、什么是算法的复杂度？

对于任何一个程序来说，都可以从三个方面进行分析，分别是 输入、处理、输出，也即 IPO（Input、Process、Output），这种分析方法对硬件和软件程序都是适用的。

数据的来源（Input）：可以是硬件传感器收集的，也可以是从网上爬取的...。数据的输出（Output）：可以显示在网页上，安卓APP上，电子屏幕上...。而最重要的是程序处理，可以对数据进行简单的处理，也可以对数据进行挖掘...。

就拿最简单的 Hello World 程序来说，也是由这三方面组成的，输出函数（处理）帮你处理输入的 “Hello World” 字符串（输入），然后再帮你将这些字符输出显示到控制台上（输出）。大到现在热门的技术，物联网、大数据，人工智能等，做的也无非都是上面三个方面内的事情，关于这些，读者可以思考一下。

评价一个程序的复杂程度，关键也是看程序中处理数据的这部分，对数据处理就要用到算法了。什么？你说你没有用过算法，其实从你编程开始的第一句 “Hello World” 就注定编程和算法分不开了，一个输出函数背后也同样有算法呀，只是你在使用算法的时候并没有意识到你在用算法罢了（嘿嘿，就是这么神奇~）。

算法是一个程序的灵魂，就好比没有蛋的泡面是没有灵魂的一样。一个好的算法可以有很多的应用，比如在美剧《硅谷》中，主角发明了一种压缩算法，将它用在音乐、云存储、视频等方面都大获成功。虽然故事是虚构的，但是在一方面也说明了算法的重要性。

分析一个算法的复杂度，也是在分析一个算法的好坏优劣，简单高效的算法才是我们应该追求的，而复杂低效的算法则是我们需要改进的。算法的复杂度包括 时间复杂度 和 空间复杂度，下面将用尽量少的概念来帮你搞懂这两个度。

1、什么是算法的时间复杂度？

讨论算法的时间复杂度，也是在讨论程序使用该算法运行的时间。经常听到身边的同学说我的电脑好慢呀，打开个软件都要一分多钟，急死人了。这从算法的角度看，只能说电脑硬件比较差，不一定说程序写的很垃圾（当然也有可能有程序的锅），同样的程序可能在别人配置高的电脑上打开就很快。所以你看单纯从程序运行需要的时间长短上，并不能反映算法的优劣，因为这和运行的设备也有很大关系（计算机计算主要用到的是 CPU 和 GPU）。

算法的时间复杂度并不能以具体的时间数值为单位（如1秒钟，1分钟等），那算法复杂度中的时间单位是什么呢？这个时间单位其实更像是程序中执行的次数或者步骤数。

举个栗子，当你忘记东西放哪里了，可能会把所有的抽屉都找一遍，假如你有 n 个抽屉，那么找完 n 个抽屉就可以找到你的东西了，每个抽屉都找了一遍，就找了 n 遍。算法的时间复杂度（运行时间）用大 O 表示（不需要关心大 O 表示法怎么来的，就是个名字），把你找东西的这个过程写成程序，算法的时间复杂度就是 O(n)，是不是感觉算法其实就在我们中间。

在上面这个例子中，最好的情况是，当你找完第一个抽屉，你就找到你的东西了，这当然是最好的了，用大 O 表示法表示就是 O(1)，但是这样的情况存在偶然性，并不能代表算法的复杂度；最坏的情况是，直到你找完最后一个抽屉，累的要死，你才找到你的东西，用大 O 表示法表示就是 O(n)。位于最坏和最好之间的情况是，当你找到中间一个抽屉时，你找到的你的东西了，用大 O 表示法表示就是 O(n/2)。

那么这三种情况，哪一种应该代表算法的时间复杂度呢？最好的情况毕竟是小概率事件，不具有普适性，肯定是不能代表算法真实的时间复杂度。平均的情况，确实在一定程度上可以反映出算法的时间复杂度，但是学过数学的我们知道，平均值容易受到极端值的影响（在评委打分时也经常是去掉最高分和最低分），所以平均情况也不是很合适。而最坏的情况却可以给我们一种保证，我们心里也可以有一个预期，这个算法在最差的情况下表现如何（就像我们做事也常常考虑最坏的情况一样），所以我们用最坏情况下的时间复杂度来衡量算法的时间复杂度。

对于大 O 括号内的参数（或者称为操作数）的系数，往往被我们主动忽略，如一个计算出所需次数为 n/2 的算法，用大 O 表示法表示是 O(n)，而对于计算次数是个常数（如 1，5， 9）的算法，用大 O 表示法表示都是 O(1)，这点是需要我们注意一下的。为什么这样做呢？因为对于计算次数是 n2/2 + n/2 + 5 这样的算法，起决定作用的是 n，而不是 n 前面的系数，当 n 为无穷大时，n 前面系数的影响就微不足道了，最终这个算法的时间复杂度用大 O 表示法为 O(n2 + n)。

2、什么是算法的空间复杂度？

程序运行时肯定是要消耗空间资源的，寄存器、内存和磁盘等。输入和输出这两部分占用空间是必需的，所以程序处理的空间指的是程序运行算法时所需的那部分空间。先来看个例子，交换两个数的值，相信大家都做过吧，一般的方法是找一个中间变量存储其中一个数的值，再让一个数等于另一个数的值，另外一个数等于中间变量的值，就像下面的伪代码这样。

// 交换 a 和 b
temp = a
a = b
b = temp

栈这种数据结构，我都应该很熟悉，特点是先进后出（FILO），交换的这两个数肯定都是要放在栈中的，但由于引入了中间变量实现，所以在程序栈中还要有中间变量的空间，一个变量占用一块栈空间（想象一下），我们用一个格子来表示，就像下面这样，中间变量也要占用一个格子（其实这个格子在其他栈中叫做 帧，如 Java虚拟机的本地方法栈和虚拟机栈，帧又是一种数据结构）。

因为这个值交换算法用到了中间变量，而中间变量又要占用一个格子，所以这个算法的空间复杂度用大 O 表示法表示就是 O(1)。

算法复杂度.png

相比较而言，算法的空间复杂度比较简单，所以我们在讨论一个算法时，更多的是讨论算法的时间复杂度。

3、一些常见的大 O 运行时间

• O(1)，如 y = x + 1，只需要一次计算便可得到结果。
• O(logn)，也称为对数时间，如二分查找算法。
• O(n)，也称为线性时间，如我们上面例子中的找东西，用的就是简单查找算法。
• O(n*logn)，如快速排序算法。
• O(n2)，如选择排序算法。
• O(n!)，如著名的旅行商问题。

这里提到的算法，将在后面的文章中讨论，感兴趣的小伙伴不妨先搜索了解一下。

上面几种大 O 运行时间，反应在图中如下（注意：图中曲线并不一定从原点开始画的，只需要知道算法运行时间的大概走势就可以了）：

几种常见的算法时间.jpg

算法的速度，指的并不是时间，而是增速，反应的在图中就是曲线的斜率，可以看到，随着输入的增加，有的算法所需要的时间越来长，也就是使用这种算法的程序会越来越慢。

4、小结

算法的复杂度和需要的时间、空间都有关系，我们更多谈论的是算法的时间复杂度，算法的时间复杂度不是以秒为单位，算法运行的速度是从其增速的角度度量的，也即是输入越多，算法运行的时间改变的快慢。一个好的算法应该是时间复杂度和空间复杂度都比较低，通俗的说就是花最少的时间和精力达到最好的效果，但是这两样往往是很难同时做到的，这就需要我们牺牲一样来做到尽可能的更好。

——本文转自我的微信公众号《编程心路》。