简介空间复杂度

      我们承接上一篇博客。我们写了时间复杂度之后，我们就要来介绍一下另一个相关复杂度了。空间复杂度。我觉得大家应该对空间复杂度认识可能比较少一些。我就是这样，我很少看见题目中有明确要求过空间复杂度的。但确实有这个是我们不可忽视的，所以我们要来学习和了解一下。

空间复杂度的含义

      我们还是老样子，对于空间复杂度的含义，我们先用官方的解释来看一下：空间复杂度 (Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S (n)=O (f (n))。 比如直接 插入排序 的 时间复杂度 是O (n^2),空间复杂度是O (1) 。 而一般的递归算法就要有O (n)的空间复杂度了，因为每次递归都要存储返回信息。这是比较官方的解释了如果换成白话就是：空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。 就是一个代码在运行时需要临时创建的空间。可以理解为我原本只创建了40个字节的空间。然后再后面代码运行需要的时候又创建出来的空间大小，那么这就是空间复杂度了。当然有很多题在最开始创建的时候就给你确定的空间大小不能超过多少多少。所以我们这也是需要了解空间复杂度的必要性。

        然后对于空间复杂度来说也是用大O表示法来表示的。并且因为前面已经讲过大O表示法了，那么我们这里就不在赘述了。接下来我们就还是直接来讲述一下如何计算空间复杂多了。

举例解释空间复杂度

示例1：

        我们先来看一下我们上一篇博客也引用过就是冒泡排序。我们这里就来看看冒泡排序的空间复杂度是多少：

         我们在前面说过空间复杂度是计算我们在代码运行时需要临时创建的空间大小，那么就是我们的空间复杂度。

       我们看看冒泡排序的我们可以看一下这里它是否有重新创建一个新的空间？好像没有吧？因为这里面最多只是用那个是swap，就算是swap。他在内部重新创建了一个空间的话，那么也是个固定的，因为我们每次都可以直接重复利用，那么是不是我们这个冒泡排序的空间复杂度为零或者为一个常数？ 然而我们在前面大o表示法中提及过，如果为常数的话，那么我们用大多表示法是不是都为O(1)。我们可以看到我们冒泡排序的空间复杂度和时间复杂度都为O（1）。所以大家也不要认为空间复杂度和时间复杂度是不相同的。

示例2：

        接下来我们用的第二个例子就是我们上一篇也使用过的斐波那契数列。当然与上一篇博客的系数是有一点不相同的。因为我们要计算它的空间复杂度，所以稍微改变了一下，大家可以先看一下下面的照片，大概尝试着计算出这个代码的空间复杂度是多少？

        我们可以看到这个代码里面在代码开头的时候就已经创建了一个空间了。在下面的for循环里面，我们对它的空间重新利用了一下。我们就在他后面都是创建新的空间。我们看一看这个。循环需要创建多少？是不是最主要的是就是我们的n。我们只需要确定了n的大小，那么我们就确定了我们还需要创建的空间大小了。然后我们也在前面说过大O表示法取最坏的结果。那么这个空间复杂度大家认为是多少呢？答案显而易见就是O（n）了。

示例3：

        接下来我们再举一个例子，我相信大家就对空间复杂度的计算很了解了。上面我们也讲过递归的时间复杂度是如何计算的，那么接下来我们就计算递归的空间复杂度是如何计算的？

        我们，大家来看一下这个递归。我们看递归嘛。肯定是会创建一个新的空间的。这里的递归是比较简单的，只创建一个。每一次都会创建一个，那么我们的这个递归是不是就是n啊。递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N) ？

       这个递归是比较简单的，很容易看出它的空间复杂度是多少。我们的空间反度其实相对的话使用的比较少，除非一些考官在面试的时候会专门挑刺来考你。

总结

        主要是大家需要了解一下和大概知道空间复杂度是如何计算的，这样就可以了。因为对于空间复杂度要求的话，其实题目还算比较少的，也像我们上面说过，除了一些在面试的时候需要考虑的话，至少我现在个人很少遇见对空间复杂度有要求的。总之大家还是需要了解一下如何计算嘛，然后这里就是今天这篇博客想与大家分享的吧。当然还有很多遗漏的东西，希望大家可以在评论区留言，然后我好补充。