查看“︁时空权衡”︁的源代码

{{NoteTA|G1=IT}}
[[计算机科学]]中的'''时空权衡'''（{{lang-en|space–time trade off}}，又叫'''空间换时间'''）是指一个[[算法]]或[[计算机程序|程序]]用增加空间使用量来换取时间减少的情况。这里，'''空间'''指的是执行一个给定任务所消耗的[[電腦數據存貯器|数据存储]]（[[动态随机存取存储器|内存]]、[[硬盘]]等），而'''时间'''指的是执行一个给定任务所消耗的时间（[[时间复杂度|计算]]时间或[[反應時間]]）。

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

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

1980年，[[馬丁·赫爾曼]]首次提出使用时空权衡法进行[[密码分析]]。<ref>{{cite journal | title=A Cryptanalytic Time-Memory Tradeoff | author=Hellman, Martin | journal=IEEE Transactions on Information Theory |date=July 1980 | volume=26 | issue=4 | pages=401–406 | doi=10.1109/tit.1980.1056220| citeseerx=10.1.1.120.2463 }}</ref>

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

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

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

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

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

==参见==
* [[算法效率]]
* [[計算資源]]
* [[布盧姆加速定理]]
* [[萨维奇定理]]

==参考文献==
{{Reflist}}

==外部链接==
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.]{{Wayback|url=http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf |date=20120204073703 }}
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.] {{Wayback|url=http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf |date=20211005164637 }}

[[Category:软件优化]]