算法之空间复杂度
算法之空间复杂度：衡量一个算法运行需要开辟的额外空间
上次我们学习了时间复杂度，那么我们今天就来看看空间复杂度！
概念 空间复杂度是对一个算法在运行过程中临时占用空间大小的度量
和时间复杂度不是真的计算时间一样，空间复杂度也不衡量算法具体占用的内存字节数。
空间复杂度计算的是额外开辟的变量的个数，适用大o渐近法
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
空间复杂度计算 no.1 冒泡排序 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 a[i]) { swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; }} 我们会发现，冒泡排序算法并没有额外定义非常多的变量，一共只有3个，属于常数阶
size_t end = n;int exchange = 0;size_t i = 1; 其空间复杂度为o(1)
计算时注意其与n的关系
当我们在算法中开辟空间，计算空间复杂度的时候，要注意开辟的这个空间与n有没有关系
int arr[n];//c99变长数组，和传过来的参数有关int* a=(int*)malloc(sizeof(int)*n);//和传过来的参数有关，o(n)int* a=(int*)malloc(sizeof(int)*3);//和传过来的参数无关，o(1)
no.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;} 和上面的斐波那契数列的递归代码不同，这里我们新创建了一个数组，用来保存计算出来的斐波那契数
一共malloc了n+1个长整型的空间，空间复杂度是o(n)
空间重复使用问题
如果是递归方法的斐波那契算法，其空间复杂度是多少呢？
long long fib(size_t n){ if(n < 3) return 1; return fib(n-1) + fib(n-2);} 答案也是o(n)
因为对于递归算法而言，其开辟的函数栈帧空间是可以重复利用的！
如fib(8)的调用，其开辟的函数栈帧，是可以在后续继续调用fib函数时重复使用的
上图中f1和f2是两个函数，但执行了相同的功能。其函数调用的空间实际上是一个，f2在f1销毁后继承了它的空间
这就好比每一次新的递归都会开一家新的饭店，但是你下次还想吃东北菜的时候，可以去之前开的东北菜馆，咱没必要让别人再开一家馆子不是嘛？
不过由于斐波那契数的递归算法会递归非常多次，在数字很大的时候，会导致栈溢出
no.3 阶乘 long long fac(size_t n){ if(n == 0) return 1; return fac(n-1)*n;} 虽然函数本身的空间不计入时间复杂度，这里计算的是递归调用时额外开辟的函数栈帧空间
一共调用了n-1次，每个栈帧使用了常数个空间，空间复杂度是o(n)
常见复杂度对比
结语 时间复杂度和空间复杂度可以帮我们很好的了解自己所写算法的好坏，在未来面试的时候，hr肯定也更喜欢效率高的算法
要多刷题，好好积累自己的能力，想必之后写出好算法也是水到渠成（吧？）
操纵继电器的主要用途与归类是怎样的
产品设计以工业设计为核心，构建完善的产业链
RUILON 连续三次荣获“国家高新技术企业证书
＂惨业＂DRAM今非昔比 Q2营收大增
高频运算放大器比较器的设计指南分享
算法之空间复杂度
Qorvo增益块放大器的主要特性以及典型应用
超微7纳米CPU、GPU大军后段封装订单由三强分食
eigrp的基本配置及配置命令
基于DAG网络上运行的Obyte分散式分类账算法介绍
如何设计一个超低压差的BOOST变换器
如何实现OPC UA协议远程通讯？
深圳安防品牌不力，华为或成最后希望
压阻式传感器的结构与产品推荐
改善音响音质的灵丹妙药——甲类并联式稳压电源
天馈系统的频率范围
Bourns IsoMOV 保护器重新定义了 MOV 保护技术
避雷器计数器校验仪的操作说明及注意事项
中国移动在江西光伏电站成功打造出全国首个5G网络的智慧电厂
索尼研发负责人：语音将成为VR重要交互方式
上次我们学习了时间复杂度，那么我们今天就来看看空间复杂度！
概念 空间复杂度是对一个算法在运行过程中临时占用空间大小的度量
和时间复杂度不是真的计算时间一样，空间复杂度也不衡量算法具体占用的内存字节数。
空间复杂度计算的是额外开辟的变量的个数，适用大o渐近法
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
空间复杂度计算 no.1 冒泡排序 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 a[i]) { swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; }} 我们会发现，冒泡排序算法并没有额外定义非常多的变量，一共只有3个，属于常数阶
size_t end = n;int exchange = 0;size_t i = 1; 其空间复杂度为o(1)
计算时注意其与n的关系
当我们在算法中开辟空间，计算空间复杂度的时候，要注意开辟的这个空间与n有没有关系
int arr[n];//c99变长数组，和传过来的参数有关int* a=(int*)malloc(sizeof(int)*n);//和传过来的参数有关，o(n)int* a=(int*)malloc(sizeof(int)*3);//和传过来的参数无关，o(1)
no.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;} 和上面的斐波那契数列的递归代码不同，这里我们新创建了一个数组，用来保存计算出来的斐波那契数
一共malloc了n+1个长整型的空间，空间复杂度是o(n)
空间重复使用问题
如果是递归方法的斐波那契算法，其空间复杂度是多少呢？
long long fib(size_t n){ if(n < 3) return 1; return fib(n-1) + fib(n-2);} 答案也是o(n)
因为对于递归算法而言，其开辟的函数栈帧空间是可以重复利用的！
如fib(8)的调用，其开辟的函数栈帧，是可以在后续继续调用fib函数时重复使用的
上图中f1和f2是两个函数，但执行了相同的功能。其函数调用的空间实际上是一个，f2在f1销毁后继承了它的空间
这就好比每一次新的递归都会开一家新的饭店，但是你下次还想吃东北菜的时候，可以去之前开的东北菜馆，咱没必要让别人再开一家馆子不是嘛？
不过由于斐波那契数的递归算法会递归非常多次，在数字很大的时候，会导致栈溢出
no.3 阶乘 long long fac(size_t n){ if(n == 0) return 1; return fac(n-1)*n;} 虽然函数本身的空间不计入时间复杂度，这里计算的是递归调用时额外开辟的函数栈帧空间
一共调用了n-1次，每个栈帧使用了常数个空间，空间复杂度是o(n)
常见复杂度对比
结语 时间复杂度和空间复杂度可以帮我们很好的了解自己所写算法的好坏，在未来面试的时候，hr肯定也更喜欢效率高的算法
要多刷题，好好积累自己的能力，想必之后写出好算法也是水到渠成（吧？）
操纵继电器的主要用途与归类是怎样的
产品设计以工业设计为核心，构建完善的产业链
RUILON 连续三次荣获“国家高新技术企业证书
＂惨业＂DRAM今非昔比 Q2营收大增
高频运算放大器比较器的设计指南分享
算法之空间复杂度
Qorvo增益块放大器的主要特性以及典型应用
超微7纳米CPU、GPU大军后段封装订单由三强分食
eigrp的基本配置及配置命令
基于DAG网络上运行的Obyte分散式分类账算法介绍
如何设计一个超低压差的BOOST变换器
如何实现OPC UA协议远程通讯？
深圳安防品牌不力，华为或成最后希望
压阻式传感器的结构与产品推荐
改善音响音质的灵丹妙药——甲类并联式稳压电源
天馈系统的频率范围
Bourns IsoMOV 保护器重新定义了 MOV 保护技术
避雷器计数器校验仪的操作说明及注意事项
中国移动在江西光伏电站成功打造出全国首个5G网络的智慧电厂
索尼研发负责人：语音将成为VR重要交互方式