算法之空间复杂度：衡量一个算法运行需要开辟的额外空间

上次我们学习了时间复杂度，那么我们今天就来看看空间复杂度！

概念

空间复杂度是对一个算法在运行过程中临时占用空间大小的度量

和时间复杂度不是真的计算时间一样，空间复杂度也不衡量算法具体占用的内存字节数。

空间复杂度计算的是额外开辟的变量的个数，适用大O渐近法

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

空间复杂度计算

NO.1 冒泡排序

我们会发现，冒泡排序算法并没有额外定义非常多的变量，一共只有3个，属于常数阶

其空间复杂度为O(1)

计算时注意其与N的关系

当我们在算法中开辟空间，计算空间复杂度的时候，要注意开辟的这个空间与N有没有关系

NO.2 斐波那契数列

和上面的斐波那契数列的递归代码不同，这里我们新创建了一个数组，用来保存计算出来的斐波那契数

一共malloc了n+1个长整型的空间，空间复杂度是O(N)

空间重复使用问题

如果是递归方法的斐波那契算法，其空间复杂度是多少呢？

答案也是O(N)

因为对于递归算法而言，其开辟的函数栈帧空间是可以重复利用的！

如fib(8)的调用，其开辟的函数栈帧，是可以在后续继续调用fib函数时重复使用的

上图中f1和f2是两个函数，但执行了相同的功能。其函数调用的空间实际上是一个，f2在f1销毁后继承了它的空间

这就好比每一次新的递归都会开一家新的饭店，但是你下次还想吃东北菜的时候，可以去之前开的东北菜馆，咱没必要让别人再开一家馆子不是嘛？

不过由于斐波那契数的递归算法会递归非常多次，在数字很大的时候，会导致栈溢出

NO.3 阶乘

虽然函数本身的空间不计入时间复杂度，这里计算的是递归调用时额外开辟的函数栈帧空间

一共调用了N-1次，每个栈帧使用了常数个空间，空间复杂度是O(N)

常见复杂度对比

结语

时间复杂度和空间复杂度可以帮我们很好的了解自己所写算法的好坏，在未来面试的时候，HR肯定也更喜欢效率高的算法

要多刷题，好好积累自己的能力，想必之后写出好算法也是水到渠成（吧？）

-----------------------------------

51CTO丨作者：慕雪年华

为了帮助大家，轻松，高效学习C语言/C++,给大家分享我收集的资源，从最零基础开始的,帮助大家在学习C语言的道路上披荆斩棘！

微信公众号：C语言编程学习基地

C语言零基础入门教程（83集全）

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）最重要的是你可以在群里面交流提问编程问题哦！

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！大家也要把握住有限的时光，抓住成长的每一次机会哦~

编程学习书籍分享：

粉丝编程交流：