时间复杂度和空间复杂度

百度百科描述

时间复杂度： http://baike.baidu.com/view/104946.htm?fr=aladdin

空间复杂度： http://baike.baidu.com/view/540497.htm?fr=aladdin

 

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

 

一、定义 
 时间复杂度

  在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

 

空间复杂度：

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

 

二、 时间复杂度 计算方法

1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，

   因此，算法的时间复杂度记做：T(n)=O(f(n))

分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。

2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，

再找出 T(n) 的同数量级（它的同数量级有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，

2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，

则时间复杂度T(n) = O(f(n))

 

 

三、比较

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，

可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间

复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有

性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑

算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的

机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为

算法的复杂度。