时间与空间的交换

复习

　　衡量一个算法，通常要看两样东西：花的时间，和占的空间。有意思的是，这两样常常可以互相交换。

　　我们前面其实已经见过这个套路了。缓存，就是用一块更快的空间，去减少“跑到慢存储里取数”的时间；哈希表，则是用额外的一张表，去换取几乎一步到位的查找。它们都在做同一件事：用空间，买时间。

　　最直白的例子，是查表。

　　假设程序需要频繁计算一个函数在整数 0 到 1000 上的取值。与其每次现算，不如提前把所有结果算好、存成一张表；之后用到时直接查，一步到位。

　　这就是典型的空间换时间：用一块额外的存储，把重复的计算省掉。

　　类似的思路到处都是：给数据库建索引、给函数结果加缓存、给常用数据做预处理。本质上，都是在说：多记一点，就能少算一点。

　　反过来，也有用时间换空间的时候。压缩就是个好例子：把数据压得更小，能省下宝贵的存储和带宽，代价是每次使用都要先解压，多花一点时间。

　　在一些资源受限的场合——比如嵌入式设备内存有限、或者网络带宽紧张——人们宁愿多花点时间算，也不愿多占空间。这时，时间就成了一种可以花的“货币”。

　　要记住，这两种交换都不是白来的。多占的空间会挤占别的用途，多花的时间会影响响应速度。所以，选择哪种权衡，永远取决于你的场景：

　　数据结构与算法的很多设计，说到底，就是在这两种资源之间找一个最舒服的平衡点。

　　接下来介绍一个更精细的工具，它看待“偶尔很贵”的操作，视角和前面不太一样。

思考题 1

　　为什么说哈希表是“用空间换时间”？它换来了什么？

思考题 2

　　举一个你身边“用时间换空间”的例子，并说说这样做的理由。

　　哈希表需要额外维护一张散列表（以及处理冲突的空间），占用的空间比简单地把元素排成一列要多。换来的，是查找时能根据键直接算出位置，接近一步到位，省去了逐个比较的时间。

　　比如压缩文件：保存时把它压小，省下磁盘空间；使用时先解压，多花一点时间。理由通常是存储或带宽资源紧张，而解压所需的时间可以接受。类似的还有图片的有损压缩、实时传输中的降质编码等。

设计师 | 南国微雪