#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題,也是典型用空間換取時間的策略.但奇怪的是,這個策略一點也不 dynamic ,一點也不 programming.老實說,我不知道為何這個策略叫 dynamic prograaming,我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子.Fibonacci number 是以數學多項式來表達的數字集合,以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時,你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上,我們會為這個 number 定義起始點,也就是說第 1 項和第 2 項的值是早被確定的,往後的項次皆由這兩項為基礎而算出來,所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ,那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時,就按以上的方法一直算到第 n 項就能得到答案. 接著,數學公式 F(n) = F(n-1) + F(n-2) 寫出來了,那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式.這一個程式碼沒有使用額外的記憶體空間,所以 space complexity 是 O(1),但仔細看一下 time complexity,卻發現超乎想像的大,因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是,當程式在 F(5) 那一個層次要往下呼叫時,程式會呼叫自己兩次,並傳送 4 和 3 為輸入參數,當第一個 recursive call 再進去時,又會再呼叫自己,並傳入 3 和 2 為輸入參數,以此類推.所以你可以看的出來,有許多重覆的計算在這 recursive 的過程中一直發生.以上圖來說,F(3) 發生了 2 次,F(2) 發生了 3 次.當 n 是一個大的數字時,你就可以發現比 n 越小的數字,重覆計算的次數越多,並且是以指數趨勢來增加.上述的程式碼雖然很簡單,但是 time complexity 卻是很可怕的.上述的程式碼是由上而下計算下來的,假設我們繼續用由上而下的計算方式,改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算.如上圖,如果 F(3) 只真正地被計算了一次,而 F(2) 只真正地被計算了一次,那麼就不會有重覆計算的事情了.為了達成這目標,最簡單的方法便是把計算後的結果儲存下來,等到要計算一樣的內容時,去 "查表" 即可.也就是說第一次 F(3) 計算的結果儲存下來,當程式遇到第二次的 F(3) 時,直接去查詢,若有答案,直接將答案拿來使用,這樣就不用計算了.同時,為了確保不會造成過多的 time complexity,我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小,如 O(1).這種 "查表" 的精神也是 dynamic programming 所代表的策略.

若將上述的程式碼加入 "查表" 的功能,它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣,但都是用了一個 array 來記錄每一個項次計算的答案,因此 time complexity 省下來了,而且 space complexity 也增加了,但這樣的空間增加似乎是值得的.當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小,不過這並不是這篇文章的重點.透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼.許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的,例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來.

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神,這是相當簡單的例子,下篇文章我們用較難的例子來說明 dynamic programming 的用法.


Share:

0 意見:

張貼留言