理解算法的复杂度

关于时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用大O符号表示，不包括这个函数的低阶和首项系数，使用这种方式时，时间的复杂度可被成为是渐近的（asymptotic analysis），渐近是指在数学分析中是一种描述函数在极限附近的行为的方法，有多个科学领域应用此方法。

（1）在计算机科学中，算法分析考虑给定算法在输入非常大的数据集时候的性能。

（2）当实体系统的规模变得非常大的时候，分析它的行为。

举个简单的例子：函数f(n)=3n^2+3n ，当n变得非常大的时候，函数的第二项3n要远比第一项n^2影响小，所以我们对于这个函数的复杂度描述可以近似认为是O( n^2 )，注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数，简单的来说，我们在评估时间复杂度影响的时候，为了简化表示，只看对其影响最大的主要路径，其他的细枝末叶都可以忽略。

算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。

常见的算法时间复杂度由大到小如下：

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n^2)＜Ο( n^3 )＜Ο(2^n)＜Ο(n!) 随着问题规模 n的不断增大，时间复杂度不断增大，算法的执行效率越低。

看下面一个图，从直观上感受一下他们的曲线走势：

根据经验值，在上面表格中只有前4个的时间复杂度是比较快的，一般可以在秒级别返回比如一些排序算法，但稍微大一些的n就会令这些算法不能动了，当n=10万的时候，平方阶一般需要几分钟才能计算完毕，而立方阶则需要200多天，至于更后面的复杂度得需要几年才能运算完毕。如果大于10万，则更加糟糕，所以在设计程序的时候我们得注意相关算法的时间复杂度。

关于空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

对于一个算法，其 时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

总结

本文主要介绍了算法的时间复杂度和空间复杂度的概念和定义，一个好的算法往往能大幅度提升程序的性能，一个坏的算法往往会拖慢整个程序的运行，因此了解算法的复杂度对我们日常开发和写代码则很有指导意义，在掌握本篇文章的知识之后，我们就可以学以致用，对于一些常见的数据结构试着去分析一下其复杂度，比如数组，链表，Hash表，二叉树等。