Frank's 資訊科技潮流站

在數學演算法上

空間和時間兩者是值得權衡(Trade-off)的兩個元素

在解一個問題的時候，其所需的時間和空間，是可以互換的。

(這裡的空間指的是需要記憶的項目)

f(x)=y

x 的集合 為 定義域

y 的集合 為 值域

如果你常常使用同一個函式，該函式需要相當大的計算持間，而且同一個x會使用兩次以上的時候

當 x 的集合數量很少的時候 (定義域很小的時候) ，在短時間內使用到同一個x的機會相當大，我們不妨把每個 f(x) 算出來並儲存起來，下次碰到同一個x的時候，只要去查剛才儲存的內容，就知道答案，不必重新算。

當 x 的集合數量很大的時候 (定義域很大的時候)，而x是相同的機率較低的時候，儲存每個值域的必要性就不是那麼大，而且所需儲存空間會相當巨大，可能是無限。

舉例

第一種情況

如果我們想知道某一個城市有多少人，會怎麼做？

在所有城市中查詢特定城市的時間，不會比做任一個城市的人口普查所需時間長

因此在查詢特定城市人口的時候，

會去查表，迅速得到答案，而不是去對特定城市再做一次人口普查

這種情況乃適合用空間換取時間的策略

(計算時間 > 儲存空間)

第二種情況

設有一線性方程式 y=x+10

當你想知道 f(x) = ?

x 有無限多種可能

所以不可能把所有 y 都儲存起來

這時候就不適合用空間換取時間

(計算時間 < 儲存空間)