递归算法如何计算时间复杂度：
递归次数*每次递归调用的次数
例题7：阶乘递归
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1)*N; } 复制代码
例题8：斐波那契数列
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); } 复制代码
虽然F(n-1)和F(n-2)都在F(N)的递归里面，但是他们不是同时调用的，是先调用完F(n-1)之后再调用F(n-2)
所以递归调用的次数为：1
空间复杂度经典例题分析
例题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; } } 复制代码
额外开辟常量个空间：i和exchange和end
每次进入内循环时，exchange变量和i变量创建空间，出了内循环后，空间销毁。然后不断循环n次。**再一次创建是在同一个地方创建，本质上相当于没有销毁。**只占了那一个空间，所以时间复杂度是O(1)而不是O(N)，
例题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; } 复制代码
额外开辟了n+1个空间的数组，空间复杂度为：0(N)
时间复杂度也是0(N)，循环共执行了N-1次
例题3：求n的阶乘-递归
==递归中：栈帧的消耗看递归的深度==
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1)*N; } 复制代码
==每次递归调用都开辟函数栈帧==，共开辟N个栈帧，每个栈帧使用了常数个空间。所以空间复杂度为：O(N)
经典名句：空间是可以重复利用的，但是时间是一去不复返的
例题4：斐波那契数列-递归版
// 计算斐波那契递归Fib的空间复杂度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); } 复制代码
最多创建N个栈帧，后序开辟的都不会比N多
所以空间复杂度为:O(N)
==递归中：栈帧的消耗看递归的深度==
常见复杂度对比
时间复杂度和空间复杂度例题就讲解到这里啦，如果对你有所帮助的话，欢迎三连支持一下博主！欢迎各位大佬批评指正！
