时空权衡

计算机科学中的时空权衡（英語：space–time trade off，又叫空间换时间）是指一个算法或程序用增加空间使用量来换取时间减少的情况。这里，空间指的是执行一个给定任务所消耗的数据存储（内存、硬盘等），而时间指的是执行一个给定任务所消耗的时间（计算时间或反應時間）。

一个给定的时空权衡的效用受到相关的固定和可变成本（如CPU速度、存储空间）的影响，并受到收益递减的影响。

历史

在动物行为的早期阶段，可以看到时空权衡的生物学用途。使用储存的知识或将刺激反应编码为DNA中的“本能”，可以避免在时间紧迫的情况下进行“计算”的需要。更具体到计算机，查找表从最早期的操作系统开始就已经实现了。

1980年，馬丁·赫爾曼首次提出使用时空权衡法进行密码分析。^[1]

权衡的类型

查询表 vs 重新计算

一个常见的情况是涉及查找表的算法：一个实现可以包含整个表，这减少了计算时间，但增加了所需的内存量；或者它可以根据需要计算表项，增加计算时间，但减少内存需求。

压缩数据 vs 不压缩数据

时空权衡可以应用于数据存储的问题。如果数据未经压缩就被存储，它需要更多的空间，但访问所需的时间要比数据被压缩后存储所需的时间少（因为压缩数据减少了它所占用的空间，但运行解压缩算法需要时间）。根据问题的具体实例，两种方式都是实用的。也有一些罕见的情况是可以直接使用压缩数据的，比如在压缩位图索引（英语：bitmap index）的情况下，使用压缩的方式比不使用压缩的方式更快。

重新渲染 vs 储存图像

只存储矢量图的SVG源代码，并在每次请求页面时将其渲染为位图图像，这是以时间换空间；使用更多的时间，但空间更少。在改变页面时渲染图像并存储渲染后的图像是以空间换取时间；使用更多的空间，但减少时间。这种技术更普遍地被称为缓存。

代码量少 vs 循环展开

在应用循环展开时，较大的代码量可以换来较快的程序速度。这种技术使循环的每一次迭代的代码变长，但却节省了在每一次迭代结束时跳回循环起点所需的计算时间。

其他例子

同样利用时空权衡的算法有：

• 计算离散对数的大步小步算法
• 密码学中的彩虹表，比蛮力攻击所需的指数级时间做得更好。彩虹表使用加密哈希函数的哈希空间中的部分预计算值，在几分钟内而不是几周内破解密码。减少彩虹表的大小会增加在哈希空间上迭代所需的时间。
• 中途相遇攻擊使用时空权衡，只需${\displaystyle 2^{n+1}}$ 次加密（和${\displaystyle O(2^{n})}$ 空间）就能找到加密密钥，而朴素的攻击预计需要${\displaystyle 2^{2n}}$ 次加密（但只需${\displaystyle O(1)}$ 空间）。
• 动态规划通过使用更多的内存，可以大大降低问题的时间复杂性。

参见

• 算法效率
• 計算資源
• 布盧姆加速定理
• 萨维奇定理

参考文献

1. Hellman, Martin. A Cryptanalytic Time-Memory Tradeoff. IEEE Transactions on Information Theory. July 1980, 26 (4): 401–406. CiteSeerX 10.1.1.120.2463  . doi:10.1109/tit.1980.1056220. 

外部链接

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.（页面存档备份，存于互联网档案馆）
• Once Upon a Time-Memory Tradeoff. （页面存档备份，存于互联网档案馆）