1. 分析普通情况下的时间复杂度/空间复杂度 2. 分析二分查找、递归实现的斐波那契数列的时间/空间复杂度

1.时间复杂度：

  时间复杂度其实即使算法执行次数n的某个函数f(n)，进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用"O"来表示数量级，时间复杂度的表达式为。

                                                                                 T(n)=O(f(n));

  它表示随着问题规模的n的增大，算法的执行时间的增长率和f(n)的增长率相同，这称作算法的渐进时间复杂度，简称时间复杂度。而我们一般讨论的是最坏时间复杂度，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，分析最坏的情况以估算算法指向时间的一个上界。

 

时间复杂度的分析方法：

1、时间复杂度就是函数中基本操作所执行的次数

2、一般默认的是最坏时间复杂度，即分析最坏情况下所能执行的次数

3、忽略掉常数项

4、关注运行时间的增长趋势，关注函数式中增长最快的表达式，忽略系数

5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势

6、递归算法的时间复杂度为：递归总次数 * 每次递归中基本操作所执行的次数

 

空间复杂度：

  算法的空间复杂度不计算实际占用的空间，而是算整个算法的“辅助空间单元的个数”，与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。

  S(n)=O(f(n))  若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数，则称这个算法的辅助空间为O(1);

  递归算法的空间复杂度：递归深度N*每次递归所要的辅助空间， 如果每次递归所需的辅助空间是常数，则递归的空间复杂度是 O(N).

 

2.二分查找的时间空间复杂度

 首先了解二分查找，首先在长度为n的表范围中查找，第一次循环在n/2中查找，第二次在n/2/2中查找，依次循环。假设在第X次找到，那么 就是找2的X次方次，有2的X次方=n解出x为log2的n ，故时间复杂度为log2N。由于辅助空间是常数级别的所以：

空间复杂度是O(1);

  

递归实现斐波那契数列的时间空间复杂的

 首先了解什么是斐波那契数列，就是这样一组数 1 1 2 3 5 8 13...，前两个数为1后面的数依次为其前两个的和

递归实现的算法为

long long Fib(int n)  

{  

       assert(n >= 0);  

       return n<2 ? n : Fib(n - 1) + Fib(n-2);  

}  

 

将递归执行图画出来可以明显的看出来，这是一颗二叉树，无论他是否是满二叉树，因为我们前面说过我们只计算最坏的情况，所以要计算这课二叉树有多少个元素，数的深度为n，那么元素为2^N-1；去掉常数项就是2的n次方

递归的时间复杂度是：  递归次数*每次递归中执行基本操作的次数

所以时间复杂度是： O(2^N)  （共执行多少次）

递归的空间复杂度是：  递归的深度*每次递归所需的辅助空间的个数

所以空间复杂度是：O(N)      （ 递归一次要开辟一个空间）