1-4　内存的使用：空间复杂度

1-4-1　基本概念

程序算法在执行时会需要如下两种空间：

（1）程序输入／输出所需空间。

（2）程序执行过程中暂时存储中间数据所需的空间。

程序输入与输出的空间是必需的，所以可以不用计算，所谓的空间复杂度（Space Complexity）是指执行算法暂时存储中间数据所需的空间，这里所谓的空间是指内存空间，也可以称空间成本。

例如，程序执行时，有时需要一些额外的内存暂时存储中间数据，以便可以方便未来程序代码的执行，存储中间数据所需的内存空间多少，就是所谓的空间复杂度。

假设有一个数列，内含一系列数字，此系列数字有一个是重复出现，我们要找出那个重复出现的数字，如下所示：

如果我们采用重复遍历方法，这个方法的演算步骤如下：

（1）如果这是第一个数字，不用比较，跳至下一个数字。

（2）取下一个数字，将此数字和前面的数字比较，检查是否有重复，如果有重复，则找到重复数字，程序结束。如果没有重复，则跳至下一个数字。

（3）重复步骤（2）。

整个执行过程如下：

过程1：

取第一个数字1，不用比较。

过程2：

取下一个数字3，将3和前面的1做比较，没有重复。

过程3：

取下一个数字4，将4和前面的1、3做比较，没有重复。

过程4：

取下一个数字5，将5和前面的1、3、4做比较，没有重复。

过程5：

取下一个数字2，将2和前面的1、3、4、5做比较，没有重复。

过程6：

取下一个数字3，将3和前面的1、3、4、5、2做比较，发现重复。

上述过程虽可以得到解答，但是这个程序的时间复杂度是O（n2）。为了提高效率，我们可以使用额外的内存存储中间数据，这个额外内存就是空间复杂度。

我们来看相同的数据，假设在遍历每个数据时，就将此数据放在一个字典形式的哈希表（Hash Table），笔者将在第8章说明表的建立方式，如下所示：

上述的字典哈希表左边字段Key是键值，右边字段Value是该键值出现的次数，每次遍历一个数值时，先检查该值在字典是否出现，如果没有就将此数值依哈希表规则放入字典内。如果遍历到最后一个数值是3，可以发现该值出现过，这时就获得我们所要的解答了。

上述时间复杂度则是O（n），效率大大提高了，而使用额外暂时存储的字典哈希表空间是n，相当于空间复杂度：

S(n) = O(f(n))

有的人也将空间复杂度的f（ ）省略表示为：

S(n) = O(n)

而原先使用重复遍历找寻重复数字的空间复杂度是O（1），但是时间复杂度则是O（n2），其实在两者取舍时，时间复杂度是优先于空间复杂度，因为算法的时间成本更重要，相当于用内存空间去换取时间。

1-4-2　常见的空间复杂度计算

　空间复杂度场景1

使用Python语言，可以使用下列语法将x、y两个数字对调。

在内存内部，实际上是使用下列方式执行数值对调。

这个算法使用一个tmp内存空间，整个空间复杂度是O（1），我们也可以将此空间复杂度称为常数空间。

　空间复杂度场景2

暂时存储中间数据所需的空间与数据规模n呈线性正相关。例如，前一小节我们使用字典哈希表找寻重复的数据，此字典哈希表所使用的内存空间与原先数据是呈线性正相关的，这时的空间复杂度是O（n），我们也可以将此空间复杂度称为线性空间。

　空间复杂度场景3

如果一个输入数据是n，算法存储中间数据所需的空间是n*n，这时空间复杂度是O（n2），我们也可以将此空间复杂度称为二维空间。

　空间复杂度场景4

程序实例ch1_1.py：笔者在计算阶乘问题时介绍了递归式调用（recursive call），在该程序中虽然没有很明显地说明内存存储了中间数据，不过实际上是有使用内存的，笔者将对其进行详细解说，下列是递归式调用的过程。

在编译程序中是使用栈（stack）处理上述递归式调用，这是一种后进先出（last in first out）的数据结构，笔者将在第5章说明栈的建立方式，下列是编译程序实际使用栈的情形。

数据放入栈称推入（push）。上述计算3的阶乘时，编译程序其实就是将数据从栈中取出，此动作的术语称取出（pop），整个概念如下：

从上述执行结果可以看到，栈所需的内存空间和递归式的深度有关，如果递归式调用深度是n，则空间复杂度就是O（n）。