时空权衡

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

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

历史

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

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

权衡的类型

查询表 vs 重新计算

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

压缩数据 vs 不压缩数据

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

重新渲染 vs 储存图像

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

代码量少 vs 循环展开

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

其他例子

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

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

参见

参考文献

  1. Hellman, Martin. . IEEE Transactions on Information Theory. July 1980, 26 (4): 401–406. CiteSeerX 10.1.1.120.2463可免费查阅. doi:10.1109/tit.1980.1056220.

外部链接

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.