時空權衡

計算機科學中的時空權衡（英語：space–time trade off，又叫空間換時間）是指一個算法或程序用增加空間使用量來換取時間減少的情況。這裡，空間指的是執行一個給定任務所消耗的數據存儲（內存、硬盤等），而時間指的是執行一個給定任務所消耗的時間（計算時間或反應時間）。

一個給定的時空權衡的效用受到相關的固定和可變成本（如CPU速度、存儲空間）的影響，並受到收益遞減的影響。

歷史

在動物行為的早期階段，可以看到時空權衡的生物學用途。使用儲存的知識或將刺激反應編碼為DNA中的「本能」，可以避免在時間緊迫的情況下進行「計算」的需要。更具體到計算機，查找表從最早期的操作系統開始就已經實現了。

1980年，馬丁·赫爾曼首次提出使用時空權衡法進行密碼分析。^[1]

權衡的類型

查詢表 vs 重新計算

一個常見的情況是涉及查找表的算法：一個實現可以包含整個表，這減少了計算時間，但增加了所需的內存量；或者它可以根據需要計算表項，增加計算時間，但減少內存需求。

壓縮數據 vs 不壓縮數據

時空權衡可以應用於數據存儲的問題。如果數據未經壓縮就被存儲，它需要更多的空間，但訪問所需的時間要比數據被壓縮後存儲所需的時間少（因為壓縮數據減少了它所占用的空間，但運行解壓縮算法需要時間）。根據問題的具體實例，兩種方式都是實用的。也有一些罕見的情況是可以直接使用壓縮數據的，比如在壓縮位圖索引（英語：bitmap index）的情況下，使用壓縮的方式比不使用壓縮的方式更快。

重新渲染 vs 儲存圖像

只存儲矢量圖的SVG源代碼，並在每次請求頁面時將其渲染為位圖圖像，這是以時間換空間；使用更多的時間，但空間更少。在改變頁面時渲染圖像並存儲渲染後的圖像是以空間換取時間；使用更多的空間，但減少時間。這種技術更普遍地被稱為緩存。

代碼量少 vs 循環展開

在應用循環展開時，較大的代碼量可以換來較快的程序速度。這種技術使循環的每一次迭代的代碼變長，但卻節省了在每一次迭代結束時跳回循環起點所需的計算時間。

其他例子

同樣利用時空權衡的算法有：

計算離散對數的大步小步算法
密碼學中的彩虹表，比蠻力攻擊所需的指數級時間做得更好。彩虹表使用加密哈希函數的哈希空間中的部分預計算值，在幾分鐘內而不是幾周內破解密碼。減少彩虹表的大小會增加在哈希空間上迭代所需的時間。
中途相遇攻擊使用時空權衡，只需 $2^{n+1}$ 次加密（和 $O(2^{n})$ 空間）就能找到加密密鑰，而樸素的攻擊預計需要 $2^{2n}$ 次加密（但只需 $O(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. （頁面存檔備份，存於網際網路檔案館）

[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.

[1]