廣告贊助

在數學演算法上

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

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

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


 

f(x)=y

x 的集合 為 定義域

y 的集合 為 值域

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

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

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


 

舉例

第一種情況

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

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

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

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

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

(計算時間 > 儲存空間)

 

第二種情況

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

當你想知道 f(x) = ?

x 有無限多種可能

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

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

(計算時間 < 儲存空間)


創作者介紹

Frank's 資訊科技潮流站

finalfrank 發表在 痞客邦 PIXNET 留言(0) 人氣()