Memoization / Precalculation

Memoization ( Tabulation )

在演算法執行過程中,將計算過的數值,儲存在記憶體裡面。下次若又需要相同的數值,就不必再重新計算一遍,只要使用記憶體裡面的資料就可以了。

Precalculation

在演算法開始之時,將常用到的數值先行計算好,儲存在記憶體裡面,如此就不必在演算法執行過程中,花時間去反覆計算這些數值。例如圓周率、字串的長度、常用的質數。

Lookup Table

在上述兩個方法當中,當有大量的、同性質的數值需要儲存的時候,通常我們會將這些數值有系統的整理成一個表(通常是陣列),以方便查閱──這個表即稱作Lookup Table。例如質數表便是一個Lookup Table。

舉例:求1到n的全部整數的立方和,n的範圍由1到10。

以直接的方式,累加每個立方數。(這個問題也有公式解,但是為了方便舉例,故這裡不採用公式。)

使用Memoization。

使用Precalculation。

Precalculation當然也可以直接算答案啦。

最後是Precalculation的極致。

UVa 141 10260 10082 10222 10738 417 10894 759 105 10415