12. 空间界¶
除时间外，空间是程序员通常关心的另一种计算资源。 正如计算机这些年来变得快得多一样，它们也获得了更大的内存分配额度。 即便如此，可用的磁盘空间或主存容量对算法设计者来说仍可能是重要的约束。
用于度量空间需求的分析技术与用于度量时间需求的技术类似。 然而，时间需求通常是针对操作特定数据结构的算法来度量的， 而空间需求通常是针对数据结构本身来确定的。 关于输入规模增长率的渐近分析概念完全适用于度量空间需求。
数据结构的首要目的是以允许高效访问数据的方式存储数据。 为了提供高效的访问，可能有必要存储关于数据在数据结构中位置的附加信息。 例如，链表的每个结点都必须存储一个指向表中下一个值的指针。 所有这类除实际数据值之外存储的信息称为 空间开销 。 理想情况下，应在允许最大访问能力的同时把开销保持在最低。 正是在这些相互对立的目标之间保持平衡的需要，使得数据结构的研究如此有趣。
算法设计的一个重要方面称为 时空权衡 原理。 时空权衡原理指出，如果愿意牺牲空间，通常就能缩短时间，反之亦然。 许多程序可以通过"打包"或编码信息来减少存储需求。 "解包"或解码这些信息需要额外的时间。 因此，得到的程序使用更少的空间，但运行得更慢。 反过来，许多程序可以通过预先存储结果或重新组织信息来以更大的存储需求为代价换取更快的运行时间。 通常，这种时间和空间的变化都是常数因子倍。
时空权衡的一个经典例子是 查找表 。
查找表预先存储某个函数的值，否则每次需要时都得计算它。
例如，12! 是阶乘函数能够存储在 32 位 int 变量中的最大值。
如果你编写的程序经常计算阶乘，
那么预先计算并把这 12 个值存储在表中很可能在时间上高效得多。
每当程序需要 \(n!\) 的值时，只需查一下查找表即可。
（如果 \(n > 12\) ，该值无论如何都太大，无法存储为 int 变量。）
与计算阶乘所需的时间相比，为存储查找表而需要的少量额外空间可能是很值得的。
查找表还可以存储诸如正弦或余弦之类代价高昂函数的近似值。 如果你只针对精确的度数计算该函数，或者愿意用最近度数的值来近似答案， 那么就可以使用存储精确度数计算结果的查找表，而不必反复计算正弦函数。 注意，初始构建查找表需要一定的时间。 你的应用必须足够频繁地使用查找表，才能让这一初始化值得。
时空权衡的另一个例子是程序员在试图优化空间时可能遇到的典型情形。 下面是一个对整数数组排序的简单代码片段。 我们假定这是一个特殊情况：有 \(n\) 个整数，它们的值是 0 到 \(n-1\) 的整数的一个排列。 这是一个 binsort 的例子。 箱排序把每个值分配到与其值相对应的数组位置。
这样既高效又只需要 \(\Theta(n)\) 时间。 然而，它还需要两个大小为 \(n\) 的数组。 下面是一个把排列排好序、但在同一个数组内完成的代码片段（因此它是"原地"排序的一个例子）。
函数 swap(A, i, j) 交换数组 A 中的元素 i 和 j 。
第二个代码片段实际上能对数组排序，这一点可能并不明显。
要看出它确实有效，请注意每次执行 for 循环至少会把值为 \(i\) 的整数移到它在数组中的正确位置，
并且在这一轮迭代中， A[i] 的值必定大于或等于 \(i\) 。
总共最多进行 \(n\) 次 swap 操作，
因为一个整数一旦被放到正确位置就无法再被移出，
而每次交换操作至少把一个整数放到它的正确位置。
因此，这个代码片段的代价为 \(\Theta(n)\) 。
然而，它比第一个代码片段需要更多的运行时间。
在我的计算机上，第二个版本运行所需的时间几乎是第一个的两倍，但它只需要一半的空间。
关于程序空间需求与时间需求之间关系的第二条原理，适用于处理 stored on disk 信息的程序。 说来奇怪，基于磁盘的时空权衡原理几乎与使用主存的程序的时空权衡原理相反。
基于磁盘的时空权衡 原理指出，磁盘存储需求能压得越小，程序运行得就越快。 这是因为从磁盘读取信息的时间与计算时间相比是巨大的， 因此为解包数据所需的几乎任何额外计算量，都会少于通过减少存储需求所节省的磁盘读取时间。 这一原理自然并非在所有情况下都成立， 但在设计处理存储在磁盘上的信息的程序时，记住它是很有好处的。
