Question

算法的空间复杂度是指什么?

Answer 1

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的。

它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变。

我们称这种算法是“就地\"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

Answer 2

空间复杂度便是我们对自己代码的“实际分析”。可能我们个人写代码体会不到空间复杂度的重要性。假设你在大型企业上班，你的老板要求你开发一个手机应用，这个时候，我们要考虑的就不仅仅是，我写的代码能不能正常运行起来这件事了，因为你要站在用户的角度去考虑，你的体验度是怎么样的，作为手机应用的使用者，我们自然会想到，我希望这个手机应用能够秒开，而不是点进去半天才能加载出来，同时也希望这个手机应用占手机的内存少一点。而作为老板，让员工开发应用的时候，也希望公司提供的电脑能安全完成开发，不希望出现因为代码运行时间过长而消耗电脑硬件，导致电脑坏掉拖延项目进展的事情发生。
空间复杂度有着类似于时间复杂度的概念：一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。
从整个程序来讨论的话，程序的空间复杂度可以完全用程序代码本身所占用的存储空间多少来表示。
首先，程序自身所占用的存储空间取决于其包含的代码量，我们只要在编程环境下输入代码进行运行，那么这段代码必定会占用电脑的存储空间。想要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码，但从这一方面来讲，过于庞大，毕竟我们编写一段代码，其中包含着很多内容，我们将继续将代码拆分分析为以下两种情况去推算空间复杂度。
一般一段代码的空间复杂度涉及到的空间类型有：
1…输入、输出空间。程序中如果需要输入输出数据，也会占用一定的存储空间。程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。即，无论是我们使用 10 行代码还是三行代码去实现同一个问题，他们最终输出的东西一样的话，即使二者代码长度不尽相同，但是输出所占的存储空间是差不多大的。
2…暂存空间。程序在运行过程中，可能还需要临时申请更多的存储空间。事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。
通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。