介绍

空间复杂度是衡量算法所用的内存空间的大小。

书中是这么说的：

“一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。

其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。”

也就是说，不能把问题本身所用的空间算进去，而是单纯讨论这一算法所用的空间如何，也即衡量它的辅助空间。

案例1

举个例子，这里有一个列表：

lst = [1, 2, 3, 4, 5, 6, 7]

我想让它的顺序反过来，不使用Python内置的排序方法，自己手动去排序，结果就像下面这样，应该怎么做？

lst = [7, 6, 5, 4, 3, 2, 1]

算法一：前后交换

把1和7交换，2和6交换，3和5交换，搞定。用Python写成通用的解法（不止是针对这一个list）便是：

def my_reverse(lst: list):  
    i = 0  
    n = len(lst)  
    while i < n / 2:  
        t = lst[i]  
        lst[i] = lst[n - i - 1]  
        lst[n - i - 1] = t  
        i += 1  
    return lst

算法二：借助一个新列表

建立一个新列表lst2，把1放到lst2的末尾，把2放到倒数第2的位置，把3放到倒数第3的位置，……，知道第一个位置放的是7，然后把这个列表复制给原来的列表。

def my_reverse(lst: list):  
  
    n = len(lst)  
  
    # 这里初始化一个lst2，默认值为0，长度与lst等长  
    lst2 = [0] * n  
  
    i = 0  
    while i < n:  
        lst2[i] = lst[n - i - 1]  
        i += 1  
  
    j = 0  
    while j < n:  
        lst[j] = lst2[j]  
        j += 1  
  
    return lst

找出其中的差别了吗？

算法一只需要借助一个变量t，而且这个变量t，随着问题规模n的增长，不发生改变，所以永远都只需借助这一个空间，空间复杂度为O(1)。

而算法二需要借助一个大小为n的列表，所以空间复杂度为O(n)。

时间复杂度与空间复杂度之间的关系

对于算法，它的时间复杂度和空间复杂度往往是相互影响的。常常会存在这样一种情况，追求时间复杂度的同时，发现空间复杂度又高了；空间复杂度低的同时，往往时间复杂度高。所以会有“时间换空间”或“空间换时间”的说法。

实际上，多数时候，是拿空间换时间。正所谓，光阴似箭，日月如梭，时间本来就比空间更为宝贵，程序也不例外。

一方面，现在的内存很充足。

1988年9月发布的Apple IIc Plus电脑，其内存容量为 128 kB。最高可扩充至1.125 MB。

想象一下，如果你的电脑内存只有128kB，那确实不得不考虑空间不够的问题。

现在的电脑一般都能达到8个G内存，容量比以前的老电脑大很多。而且就算内存不够，系统还会通过“虚拟内存技术”把磁盘（外存）拿一块来当作内存读写，外存一般可达到128G以上。

另一方面，是用户体验的问题。据说有人看着浏览器那个加载的loading条就很焦虑。灵魂拷问就是，你忍心让用户在那里傻傻地等待吗？机器可以无限等待下去，但人不喜欢任何的等待。所以宁可牺牲内存，也得换来执行时间的缩短，以减少用户的等待时间。

但这也不意味着完全不考虑空间，毕竟内存不是无限的，很多时候内存都很紧张。我平时就喜欢打开浏览器，同时开十几个网页，再加之各种其他软件的运行，Word，Excel，甚至是像Photoshop或视频剪辑软件之类的，8个G的内存可能直接用完了。而且一般来讲尽量别让系统用“虚拟内存技术”到磁盘（外存）找一块当作内存读写，一方面是磁盘读写真的很慢，和内存不是一个等级的，另一方面，频繁读写会降低磁盘的使用寿命。

所以，虽然时间复杂度会更重要，但还是得综合考虑时空复杂度。