实例5:

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1;
}

我们可以来推导一下：假定我们要查找的数据个数为N,由二分查找的算法思想可知，每次查找都将会缩小一半的区间，最坏情况下就会查找到区间长度为1，假定我们查找了x次，

则有：2^x=N      ------>   x=logN( 以2为底）

所以时间复杂度为O(logN)

其他说明：

1 二分查找的前提是必须有序，想了解更多的可以移步到另外一篇文章：

详解二分查找相关练习。

2 以后在力扣或者牛客上刷题题目中logN无明确要求一般是默认以2为底。

实例6:

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 return Fac(N-1)*N;
}

由函数栈帧的知识我们可知：每递归调用一次函数都将会额外开辟栈帧，由代码可知每递归调用一次函数里面执行次数就为常数个，则用大O渐进法可知其时间复杂度为O(N)

实例7:

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 return Fib(N-1) + Fib(N-2);
}

这个题与上面一题有点儿类似，都要调用栈帧，但是区别是本题每次递归调用一次函数里面的执行次数并不为常数个，通过分析我们发现该函数调用过程酷似二叉树里面的前序遍历，

想了解更多的可以移步 二叉树  。通过分析该结构像一个二叉树，而二叉树的高度不难算出为N-2,所以用大O渐进法可知其时间复杂度为O(2^N).

总结：

通过上面例题我们不难发现，时间复杂度的计算的只是一个大概值，并不会让我们计算的非常精确，这样做实际意义不大。

重要的事情说3遍：

时间复杂度与套了几次循环无关

时间复杂度与套了几次循环无关

时间复杂度与套了几次循环无关

这是很多初学者容易犯的问题，认为镶嵌了几次循环时间复杂度就是N的几次方，这种方法在某些情况可能结果正确，那也只是碰巧而已，计算时间复杂度看的是算法思想

3.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间大小的量度

空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用 大 O 渐进表示法 。

注意： 函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的 额外空间 来确定。

实例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

实例1使用了常数个额外空间，所以空间复杂度为O(1)

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
}

实例2动态开辟了N个空间，空间复杂度为O(N)

实例3：

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 return Fib(N-1) + Fib(N-2);
}

我们知道函数递归调用是要开辟函数栈帧的，由前面我们可以知道该函数递归调用了2^N次，那么开辟的额外栈帧占用的空间也是2^N个吗？

当我们将高度次的栈帧（本题精确的应该是N-2,但是算复杂度计算的是大概值，后面的常数可以忽略）开辟完了后到达临界条件就把结果给返回了，这时就要销毁本次的栈帧，下次再开辟的时候操作系统会再刚才被销毁的栈帧空间下继续开辟，所以这样不断算下来额外开辟的空间就为N，故空间复杂度为O(N).

写在最后：

时间复杂度与空间复杂度是我们刷一些算法题的基本功，代码的优化往往是从这两方面出发，所以能够清楚的理解复杂度也是我们必不可少的技能之一。最后祝愿大家都能够进到自己想进的公司，拿到满意的offer，我们下期再见啦。