目录
1.衔接前言-时间复杂度的回顾
2.关于算法复杂度
3.本文主角-空间复杂度
3.1大O的渐进表示方法
4.空间复杂度例题----实际感受空间复杂度
4.1冒泡排序的空间复杂度
4.2计算递归函数的空间复杂度
4.3动态开辟内存版本求斐波那契数列的空间复杂度
4.4（重要难点理解）求斐波那契数列递归算法的时间复杂度（注意空间复用）
5.常见复杂度对比
6.关于空间复杂度的oj题目练习-旋转数组
6.1思路1
6.2思路2
6.2.1k%n的重要性-----oj题目中的越界错误
6.3思路3-----旋转旋转再旋转
7.结语
1.衔接前言-时间复杂度的回顾
时间复杂度复习跳转
2.关于算法复杂度
- 算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
- 时间复杂度主要衡量一个算法的运行快慢，
- 而空间复杂度主要衡量一个算法运行所需要的额外空间。
- 在计算 机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
3.本文主角-空间复杂度
- 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
- 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。形式参数不算。
- 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
- 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。但是如果在运行期间额外调用堆栈要算
3.1大O的渐进表示方法
- 这个表示方法在时间复杂度讲过大家也可以先看完时间复杂度在过来。
- 1、用常数1取代运行时间中的所有加法常数。
- 2、在修改后的运行次数函数中，只保留最高阶项。
- 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
我们直接上代码来带入理解时间复杂度的计算方法：
4.空间复杂度例题----实际感受空间复杂度
重点：
运行过程中临时占用存储空间大小的量度
①空间复杂度算的运行过程中开辟的变量的个数。开辟的变量要满足要求就是为了实现这个算法，形式参数不算。
②运行期间额外调用堆栈要算
4.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;
}
}那我们首先看一下我们调用这个算法，会创建那几个变量：
如
- ①所示：end、exchange、i这三个变量就是我们的为了实现算法而创建的变量，分别为了实现我们算法中的循环、迭代等功能。所以按照大O的渐进表示法，这个算法的空间复杂度就是O(3),但是，根据第一条：用常数1取代运行时间中的所有加法常数。所以这个冒泡排序算法的空间复杂度表示为O(1).
- ②这是一个形式参数，不算做空间复杂度的计算对象
- ③这是一个指针参数，指向一个数组，很多伙伴会想这个数组的空间要不要算作空间复杂度的计算之中，实际上是不必要的，我们要牢牢扣住空间复杂度的定义，为了实现算法而额外开辟的空间才纳入计算，那么如果我们不是为了实现这算法而是要调用其他算法，那么这个数组的空间照样要上传到其他算法1，所以这个数组的空间就不算做时间复杂度的值内。
4.2计算递归函数的空间复杂度
long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
4.3动态开辟内存版本求斐波那契数列的空间复杂度
// 计算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; }
4.4（重要难点理解）求斐波那契数列递归算法的时间复杂度（注意空间复用）
重点：计算时间复杂度的时候时间是可以累加的，但是空间却是可以重复利用的
先上代码：
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }我们在计算其时间复杂度的时候我们这样来理解这个算法的调用的：
在这个时候我们理解的是：递归调用函数是一起调用的，但是在真正的递归在内存中跑起来却不是这样调用的：
我们以Fib(4)举例讲解：
然后后面的调用都是使用这片空间，我们如果在程序中调试去看，我们的N的值应该会这样变化：4-3-2-1-3-4-2-4：
那么当我们有n个递归：
是不是只会总的开辟N个空间从N到1，那么空间复杂度就为O(N)
5.常见复杂度对比
6.关于空间复杂度的oj题目练习-旋转数组
做题链接
可以参考字符串左旋的解题过程：字符串左旋详细讲解
要求时间复杂度O(N)
空间复杂度O(1)
6.1思路1
我们将最后一个数存放在一个变量之中，然后我们将前面的数往后挪，再把最后一个数放在第一个就完成了一次左旋，循环k次就完成了k次左旋。可参考左旋的这个图解，注意方向相反就行，原理一样：
那么此时我们计算一下
- 时间复杂度：循环K次，由于假如我们四个数，我们是不是最多可以右旋3次，旋转第四次就得到原数组内容，那么我们最多旋转k%N次，最大为N-1,我们交换需要交换n次最多，那么时间复杂度就是（N-1）^2,就是O(N).
- 接下来我们估算一下空间复杂度，由于我们没有额外申请空间，创建一个temp变量用于交换，创建i变量用于循环，我们的空间复杂度为常数个就是O(1),
- 那么测试用例过不了应该是因为时间复杂度。
6.2思路2
时间复杂度：使用拷贝函数的话最坏遍历循环n次，调用三次拷贝函数，为3n，时间复杂度为O(N).
空间复杂度：我们额外申请了numsize个空间和创建一些变量，空间复杂度应该为N+1,就是O(N).
空间消耗很多注意。
6.2.1k%n的重要性-----oj题目中的越界错误
在代码中K%n是必要的，因为我们知道旋转最多旋转n-1次，因为选择n次相当于回到原点，如果我们不模出，就会出现越界问题。我们可以看一下这个错误的代码：
6.3思路3-----旋转旋转再旋转
参考我们的左旋思路：
- 我们分析一下时间复杂度：每一次调用我们的旋转函数，是不是最坏的情况就是循环n-1次，调用三次旋转函数，就是3n-3,那么我们的时间复杂度就为O(N)
- 空间复杂度：我们只是创建了一些变量，额外写了旋转函数，在栈上额外开辟了一个空间，那么额外空间开辟就是常数个，空间复杂度就是O(1).
我们实现一下：
7.结语
以上就是本期的所有内容，知识含量蛮多，大家可以配合解释和原码运行理解。创作不易，大家如果觉得还可以的话，欢迎大家三连，有问题的地方欢迎大家指正，一起交流学习，一起成长，我是Nicn，正在c++方向前行的奋斗者，数据结构内容持续更新中，感谢大家的关注与喜欢。
