算法系列开篇:10分钟讲明白算法复杂度

【算法包罗万象，如果用一句话简单的定义，或许就是：解决某一个问题而采取的具体有效的操作步骤。认识算法，首先要对算法复杂度有基本的理解。算法复杂度，将是之后你学习算法、评价算法、开发算法的一杆秤。】

算法难吗——慢慢来就不难

一、算法的定义

算法(algorithm)：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。比如要解决1，2，3，……，n的求和，我们可以设计算法为：累加求和——先求得1、2的和，再将3加上去求和，再将4加上去求和……因此对应的代码就可以是：

假设n=100，则运行结果为：

需要解决的问题越难，算法的步骤、对应的代码就会更多。所以我们在学习算法的时候不用觉得算法很难，不是所有的算法都是卡尔曼、卷积……一步步前进就可以了。

二、如何理解算法复杂度

那么为什么有算法复杂度这个东西呢？因为算法其一是保证正确性，其二需要的是效率（如果计算机的计算速度是无限快的，或许可以忽略效率，但……）。我们仍旧以上面“解决1，2，3，……，n的求和”为例，还有第二种方法——公式法表述，即(1+n)*n/2。代码如下：

运行结果同样为5050。那么，在编写代码的时候选择哪一种好呢？这时候我们可以把n放得大一些，就看出来区别了，比如让n=100000000（n比较小的时候时间消耗差异不够明显）：

运行结果为：

用time模块计算运行时间就可以看到，虽然运算结果一样，但是消耗的时间完全不同，方法一计算花费的时间远大于方法二。试想一下如果程序多次用到方法一、且n的值再更大一些，是不是会造成整体代码的运行时间、消耗资源进一步放大。这就是算法复杂度（时间复杂度）的直观理解，这里方法二中算法复杂度（时间复杂度）小于方法一中算法复杂度，当然同等条件下优选方法二中的算法。

三、算法复杂度的定义

算法复杂度包括时间复杂度和空间复杂度，前面例子所阐述的就是时间复杂度方面。

时间复杂度

即算法的执行效率，是指算法的执行时间与算法的输入值之间的关系，一般用大O表示。常见的时间复杂度：O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(2^n)<Ο(n!)：

编程时需要关注for/while循环，考虑如何减少循环，以降低时间复杂度。下面举一些例子：

空间复杂度

指算法存储空间与输入值之间的关系，常见空间复杂度：O(1)<O(N)。O(1)举例说明：定义一个int型count变量，在下面代码中for循环改变的都是count的内容，count所占空间没有变更，因此空间复杂度为O(1)：

O(n)举例说明：定义一个数组，array中每增加一个值，就增加了相应的字节空间以存储，空间复杂度为O(N)：

是不是觉得算法很有意思？

下一期我们就来学习一些简单的排序算法。