算法的复杂度
什么是算法的复杂度
对于任何一个程序来说，都可以从三个方面进行分析，分别是 输入、处理、输出，也即 IPO（Input、Process、Output），这种分析方法对硬件和软件程序都是适用的。
数据的来源（Input）：可以是硬件传感器收集的，也可以是从网上爬取的…。数据的输出（Output）：可以显示在网页上，安卓APP上，电子屏幕上…。而最重要的是程序处理，可以对数据进行简单的处理，也可以对数据进行挖掘。
评价一个程序的复杂程度，关键也是看程序中处理数据的这部分，对数据处理就要用到算法了。
分析一个算法的复杂度，也是在分析一个算法的好坏优劣，简单高效的算法才是我们应该追求的，而复杂低效的算法则是我们需要改进的。算法的复杂度包括 时间复杂度 和 空间复杂度，下面将用尽量少的概念来帮你搞懂这两个度。
什么是算法的时间复杂度
讨论算法的时间复杂度，也是在讨论程序使用该算法运行的时间。而单纯从程序运行需要的时间长短上，并不能反映算法的优劣，因为这和运行的设备也有很大关系（计算机计算主要用到的是 CPU 和 GPU）。
算法的时间复杂度并不能以具体的时间数值为单位（如1秒钟，1分钟等），那算法复杂度中的时间单位是什么呢？这个时间单位其实更像是程序中执行的次数或者步骤数。
举个栗子，当你忘记东西放哪里了，可能会把所有的抽屉都找一遍，假如你有 n 个抽屉，那么找完 n 个抽屉就可以找到你的东西了，每个抽屉都找了一遍，就找了 n 遍。算法的时间复杂度（运行时间）用大 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)。
什么是算法的空间复杂度
程序运行时肯定是要消耗空间资源的，寄存器、内存和磁盘等。输入和输出这两部分占用空间是必需的，所以程序处理的空间指的是程序运行算法时所需的那部分空间。先来看个例子，交换两个数的值，相信大家都做过吧，一般的方法是找一个中间变量存储其中一个数的值，再让一个数等于另一个数的值，另外一个数等于中间变量的值，就像下面的伪代码这样。
// 交换 a 和 b
temp = a
a = b
b = temp
栈这种数据结构，我都应该很熟悉，特点是先进后出（FILO），交换的这两个数肯定都是要放在栈中的，但由于引入了中间变量实现，所以在程序栈中还要有中间变量的空间，一个变量占用一块栈空间（想象一下），我们用一个格子来表示，就像下面这样，中间变量也要占用一个格子（其实这个格子在其他栈中叫做 帧，如 Java虚拟机的本地方法栈和虚拟机栈，帧又是一种数据结构）。
因为这个值交换算法用到了中间变量，而中间变量又要占用一个格子，所以这个算法的空间复杂度用大 O 表示法表示就是 O(1)。
相比较而言，算法的空间复杂度比较简单，所以我们在讨论一个算法时，更多的是讨论算法的时间复杂度。
一些常见的大 O 运行时间
- O(1)，如 y = x + 1，只需要一次计算便可得到结果。
- O(logn)，也称为对数时间，如二分查找算法。
- O(n)，也称为线性时间，如我们上面例子中的找东西，用的就是简单查找算法。
- O(n*logn)，如快速排序算法。
- O(n2)，如选择排序算法。
- O(n!)，如著名的旅行商问题。
算法的速度，指的并不是时间，而是增速，反应的在图中就是曲线的斜率，可以看到，随着输入的增加，有的算法所需要的时间越来长，也就是使用这种算法的程序会越来越慢。
小结
算法的复杂度和需要的时间、空间都有关系，我们更多谈论的是算法的时间复杂度，算法的时间复杂度不是以秒为单位，算法运行的速度是从其增速的角度度量的，也即是输入越多，算法运行的时间改变的快慢。一个好的算法应该是时间复杂度和空间复杂度都比较低，通俗的说就是花最少的时间和精力达到最好的效果，但是这两样往往是很难同时做到的，这就需要我们牺牲一样来做到尽可能的更好。
