一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
⑴找出算法中的基本语句
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵计算基本语句的执行次数的数量级
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
下面举一个简单例子：
for(i=1;i<=n;i++)
{a++};
{
for(j=1;j<=n;j++)
a++;
}
3、忽略掉常数项
1.二分查找
2.斐波那契的递归算法
一个程序的空间复杂度是指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
（1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。
（2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。
1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
3、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
4、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。
在斐波那契数求空间复杂度的过程中，我们需要考虑函数栈帧的过程，比如当我们求第五个斐波那契数的时候，这时候需要先开辟空间存放第四个数，然后再开辟空间存放第三个数；当开辟空间到第二个和第一个数的时候，第三个数得到结果并返回到第四个数中，第四个数的值已知后返回到第五个数中，在这个过程中，最大占用空间即为层数减一。如下图所示：
开辟空间的大小最多等于层数+1，也就是说求第N个斐波那契数，空间复杂度即为O（N）。
二分查找因为整个运算过程没有空间的改变，所以空间复杂度为O（1）。
非递归：
templateT*BinarySearch(T*array,intnumber,constT&data)
assert(number>=0);
intleft=0;
intright=number-1;
while(right>=left)
intmid=(left&right)+((left^right)>>1);
if(array[mid]>data)
right=mid-1;
elseif(array[mid] left=mid+1; else return(array+mid); returnNULL; 分析： 由于辅助空间是常数级别的，所以，空间复杂度是O(1)。 递归： templateT*BinarySearch(T*left,T*right,constT&data) assert(left); assert(right); if(right>=left) T*mid=left+(right-left)/2; if(*mid==data) returnmid; return*mid>dataBinarySearch(left,mid-1,data):BinarySearch(mid+1,right,data); 递归的次数和深度都是log2N,每次所需要的辅助空间都是常数级别的： 空间复杂度：O(log2N) //递归情况下的斐波那契数列 longlongFib(intn) assert(n>=0); returnn<2n:Fib(n-1)+Fib(n-2); 递归的空间复杂度是：递归的深度*每次递归所需的辅助空间的个数，所以，空间复杂度是：O(N)。