空间复杂度
空间复杂度是程序运行所以需要的额外消耗存储空间,也用o()来表示
比如插入排序的时间复杂度是o(n^2),空间复杂度是o(1)
而一般的递归算法就要有o(n)的空间复杂度了,因为每次递归都要存储返回信息
一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。
算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用T(n)表示算法基本操作的执行次数.在评价算法的时间复杂性时，不考虑两算法执行次数之间的细小区别，而只关心算法的本质差别:
为此，引入一个所谓的O() 记号，则T1(n)=2n=O(n),T2(n)=n+1=O(n)。一个函数f(n)是O(g(n))的，则一定存在正常数c和m，使对所有的n>m，都满足f(n)<c*g(n)。