下载掌阅APP，畅读海量书库
立即打开
程序算法在执行时会需要如下两种空间：
（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（n 2 ） 。为了提高效率，我们可以使用额外的内存存储中间数据，这个额外内存就是 空间复杂度 。
我们来看相同的数据，假设在遍历每个数据时，就将此数据放在一个字典形式的 哈希表 （Hash Table），笔者将在第8章说明表的建立方式，如下所示：
上述的字典 哈希表 左边字段 Key 是 键值 ，右边字段 Value 是该键值出现的 次数 ，每次遍历一个数值时，先检查该值在字典是否出现，如果没有就将此数值依哈希表规则放入字典内。如果遍历到最后一个数值是3，可以发现该值出现过，这时就获得我们所要的解答了。
上述 时间复杂度 则是 O（n） ，效率大大提高了，而使用额外暂时存储的字典哈希表空间是n，相当于空间复杂度：
S(n) = O(f(n))
有的人也将空间复杂度的f（ ）省略表示为：
S(n) = O(n)
而原先使用 重复遍历 找寻重复数字的 空间复杂度 是 O（1） ，但是 时间复杂度 则是 O（n 2 ） ，其实在两者取舍时， 时间复杂度 是 优先于 空间复杂度 ，因为算法的时间成本更重要，相当于用内存空间去换取时间。
空间复杂度场景1
使用Python语言，可以使用下列语法将x、y两个数字对调。
在内存内部，实际上是使用下列方式执行数值对调。
这个算法使用一个 tmp 内存空间，整个空间复杂度是 O（1） ，我们也可以将此 空间复杂度 称为 常数空间 。
空间复杂度场景2
暂时存储中间数据所需的空间与数据规模n呈线性正相关。例如，前一小节我们使用字典哈希表找寻重复的数据，此字典哈希表所使用的内存空间与原先数据是呈线性正相关的，这时的 空间复杂度 是 O（n） ，我们也可以将此 空间复杂度 称为 线性空间 。
空间复杂度场景3
如果一个输入数据是n，算法存储中间数据所需的空间是 n*n ，这时 空间复杂度 是 O（n 2 ） ，我们也可以将此 空间复杂度 称为 二维空间 。
空间复杂度场景4
程序实例ch1_1.py： 笔者在计算阶乘问题时介绍了递归式调用（recursive call），在该程序中虽然没有很明显地说明内存存储了中间数据，不过实际上是有使用内存的，笔者将对其进行详细解说，下列是递归式调用的过程。
在编译程序中是使用 栈 （stack）处理上述 递归式调用 ，这是一种 后进先出 （last in first out）的数据结构，笔者将在第5章说明 栈的 建立方式，下列是编译程序实际使用栈的情形。
数据放入 栈 称 推入（push） 。上述计算3的阶乘时，编译程序其实就是将数据从栈中取出，此动作的术语称 取出（pop） ，整个概念如下：
从上述执行结果可以看到，栈所需的内存空间和递归式的深度有关，如果递归式调用深度是 n ，则 空间复杂度 就是 O（n） 。