Question

硬件的发展一直遵循着摩尔定律，内存的容量基本上每隔18个月就会翻一番。由于内存的容量增加迅速，在软件开发的过程中我们允许以牺牲一定的空间为代码来优化时间性能，以尽可能地缩短软件的响应时间。这就是我们通常所说的以空间换时间。

在面试的时候，如果我们分配少量的辅助空间来保存计算的中间结果以提高时间效率，这样的思路通常是可以接受的。本书中收集的面试题中有不少这种类型的题目，比如在面试题34丑数中用一个数组按照从小到大的顺序保存已经求出的丑数；在面试题43n个骰子的点数中交替使用两个数组求骰子每个点数出现的次数。

值得注意的是，以时间换空间的策略并不一定都是可行的，在面试的时候要具体问题具体分析。我们都知道在n个无序的元素里做查找操作，需要O（n）的时间。但如果我们把这些元素放进一个哈希表，那么在哈希表内就能实现O（1）的查找。但同时实现一个哈希表是有空间消耗的，是不是值得以多消耗空间为前提来换取时间性能的提升，我们需要根据实际情况仔细权衡。在面试题35第一个只出现一次的字符中，我们用数组实现了一个简易哈希表，有了这个哈希表就能实现O（1）查找任意字符。对于ASCII码的字符而言，总共只有256个字符，因此只需要1K的辅助内存。这点内存消耗对于绝大多数硬件来说是完全可以接受的。但如果是16位的Unicode的字符，创建这样一个长度为2¹⁶的整型数组需要4×2¹⁶也就是256K的内存。这对于个人电脑来说也是可以接受的，但对于一些嵌入式的开发就要慎重了。

很多时候时间效率和空间效率存在类似于鱼与熊掌的关系，我们需要在它们之间有所取舍。在面试的时候究竟是以时间换空间还是以空间换时间，我们可以和面试官进行探讨。多和面试官进行这方面的讨论是很有必要的，这既能显示我们的沟通能力，又能展示我们对软件性能全方位的把握能力。