初學者學演算法|從費氏數列認識何謂遞迴

程式麻瓜的程式知識課(七)

Cheng-Wei Hu | 胡程維
AppWorks School
8 min readMar 5, 2018

--

初學者學演算法系列的第一篇文章中,我們認識了演算法這個玩意兒,也對評斷演算法好壞的工具「時間複雜度」有了基本的概念。在前兩篇文章中,我們分別介紹了三個演算法入門的必備知識:選擇排序法、插入排序法與合併排序法。

而在合併排序法的程式碼實作中,我們偷偷運用到了一點遞迴的觀念,接下來,就讓我們一邊認識 O(2^n) 的費氏數列算法以及遞迴觀念。

目錄:常見的六種時間複雜度與演算法

  1. O(1):陣列讀取
  2. O(n):簡易搜尋
  3. O(log n):二分搜尋
  4. O(n²):選擇排序法、插入排序法
  5. O(n logn):合併排序
  6. O(2^n):費波那契數列

O(2^n):費波那契數列 (Fibonacci numbers)

時間複雜度為 O(2^n) 的演算法,代表著執行步驟會是 2 的 n 次方。實務上來說,這樣的執行效率非常的慢,例如當輸入為 100 時,執行步驟就會暴增到 30 位數,等於即使每秒都能執行 1 百億個步驟,也需要個天荒地老 1 千億年才能完成。因此,這樣的時間複雜度是大部分工程師在設計演算法時想要避免的。

而這樣的時間複雜度,最常見的例子是以遞迴計算費波那契數列 (Fibonacci numbers)。

費波那契數列

所謂費波那契數列,是指在一串數字中,每一項是前兩項的和。數學上的定義為:

  • 第 0 項 = 0
  • 第 1 項 = 1
  • 第 n 項 = 第 n-1 項 + 第 n-2 項

從上面的數學定義,我們可以簡單列出數列的 0 到 10 項為:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55。

知道了何謂費波那契數列後,接著我們就要先來解釋如何計算在程式中計算數列的第 n 項為何,以及為何它的時間複雜度為 2 的 n 次方。

計算費波那契數列第 10 項的程式碼如下:

def fibo(n):
if n == 0:
return 0;
elif n == 1:
return 1;
return fibo(n-1) + fibo(n-2)

print(fibo(10))

觀察上面的程式碼我們可以看到,程式碼的設計幾乎只是單純地把數學定義寫成程式碼。接下來,我們就要藉由上面的這段簡單程式碼,解答讀者心中可能長久以來未解的迷惑:何謂「遞迴」?

從費波那契認識遞迴

所謂遞迴,最簡單的定義就是

在函式之中呼叫函式自己本身

所謂函式,我們可以簡單理解成它是一個把一串程式碼包成一個動作的工具。而執行這一個動作就稱為呼叫。

以 Python 為例,我們會用 def 把下面所有縮排的那串程式碼包成一個動作。def 後面是這個動作的名稱,名稱後面的括弧裡放著這個動作所要使用的參數。return 則是將這個動作賦予一個值,把 return 後面接的東西賦予給它。

以 fibo 為例,def 後面加的 fibo( ) 為這個動作的名字(函式名稱),括弧內的 n 為傳入的參數。所以當我們呼叫 fibo(10) 的時候,就會把 n 當作 10 去執行動作。

而 return 是為動作賦值,所以當 n 不是 0 或 1 時,fibo(n) = fibo(n-1) + fibo(n-2),剛好等於它的定義。

所以在上面的程式碼中,當我們執行 print(fibo(10)) 時,就會執行 def 後面的五行程式碼,並把 10 作為 n 執行,最後把它 return 的值印出來。

但根據費波那契數列的定義,要知道第 n 項,我們就需要知道第 n-1 項與第 n-2 項,於是在程式碼中我們可以看到,在 n 不等於 0 或 1 時,fibo( ) 函式就會呼叫函式自己,只是這次是想要來計算第 n-1 項與第 n-2 項,所以就呼叫 fibo(n-1) 與 fibo(n-2)。

而要如何知道第 n-1 項是多少呢?我們這時就需要知道第 n-2 與第 n-3 項,如此類推,最後直到我們想要知道的項為第 0 項與第 1 項時,因為這兩項已經被定義了,所以我們就能一一解答前面的所有項了。

還是有點抽象嗎?讓我們以計算 n=5 時的費波那契數列為例,他在進行函式執行時的呼叫順序如下:

每一項都會按照定義往前呼叫它的前兩項。

從上面的圖可以觀察到,每一次函式往下的呼叫,最後都會停在 F(1) 或 F(0),因為這兩項是唯一在計算費波那契數列時唯一先被定義的。因此找到這兩項後,就可以開始往前加總出其他項的值,而往前加總的順序如下:

每一項在呼叫到 F(1) 或 F(0) 後,才會往回推算到該項。

了解了費式數列遞迴程式碼如何運作後,老樣子我們要開始分析他的時間複雜度。

費氏數列的時間複雜度

最簡單理解時間複雜度的方法就是直接使用觀察法。從上面的圖我們可以看到,每往下一層,每一項需要呼叫的次數就變成 2 倍,像 F(5) 要呼叫 F(4) + F(3) 、F(3) 要呼叫 F(2) + F(1) 等等。

而要找到數列的第 5 個數,我們需要的層數是剛好是 5 層,而推展到第 n 個數時,我們剛好需要 n 層。這個部分如果有點抽象的話,可以直接觀察上面的例子,圖中每一層的最左邊那項,是從 F(n) 一路遞減到 F(1),這樣剛剛好會是 n 層。

整理上面兩段如下,我們就可以求出最後時間複雜度約等於為 O(2^n)。

  • 每往下一層,步驟數變 2 倍
  • 總共有 n 層
  • 時間複雜度:O(2^n)
註:有些讀者可能會有疑問,觀察上面的圖,並不是每個數都會呼叫到 n 層,越往圖的右邊呼叫的層數越少。經過神秘的數學運算,最後時間複雜度其實是 1.6180339887^n (那一串數字是大名鼎鼎的黃金比例),但簡單起見,我們比較常用 O(2^n) 去理解。

同場加映:如何加速計算費氏數列的演算法

在上面我們提到過,時間複雜度 O(2^n),在實務上非常的慢。因此,我們就要來試著改善上面的演算法,看看能不能讓他加速一點。

首先,我們還是要先使用觀察大法,重新檢視上面進行函式執行時的呼叫圖。我們可以輕鬆發現,圖中有很多地方是被重複計算的。例如:我們計算了 F(3) 兩次、F(2) 三次,而這些重複的部分就是拖慢演算法的元兇。

那要如何減少重複計算呢?我們可以「用空間換取時間」,把每一個算過的值都用一個大表依序記下來。這樣當我們想要知道 F(3) 是多少時,我不用重新計算 F(2)+F(1),只要去大表上找到 F(3) 的答案就好。讓我們以計算 F(10) 為例:

而上面這個方法的時間複雜度為多少呢?我們可以很快心算一下,算每一項的同時我們需要去讀取前兩項的值,並把它加起來,總共需要三個步驟。而我們總共需要算 n-1 次,所以總共的步驟數是 3(n-1) 次,只看最高次方項並拔掉係數後,我們就可以得到加速後的時間複雜度:O(n)。

在程式碼的實作中,我們可以藉由不斷更新大表的數字已達到節省空間的效果,簡單實作計算費氏數列第十項的程式碼如下

table = [0]*3
table[0] = 0
table[1] = 1

for i in range(2,11):
table[2] = table[1] + table[0]
table[0] = table[1]
table[1] = table[2]

print(table[2])

小結

在這篇文章中,我們先瞭解了何謂費氏數列,並透過費氏數列瞭解了基本遞迴的定義以及所需的時間。接著,我們透過以「空間換取時間」的方式,加速了計算費氏數列的演算法,並將時間複雜度從 O(2^n) 進步到了 O(n)。

【AppWorks School Batch #12 限時招生中】
AppWorks School 將開設 Android、iOS、Front-End 與 Backend Class 四個不同技能的訓練班次,全程免費,透過線上學習 4 週,駐點集訓 16 週的專案導向訓練,幫助你成為軟體工程師。
歡迎想成為軟體工程師的朋友,把握機會申請,報名到 7/22 23:59 截止喔!~https://bit.ly/2BUQmvn

想要準時收看新文章嗎?快追蹤 AppWorks School 的粉專與 Medium Publication 吧!

嗨,我是程維,目前在美國 Google 擔任軟體工程師。如果你對入門機器學習、深度學習、人工智慧和大語言模型有興趣,我目前在準備一系列入門的文章。歡迎在這個網頁表單輸入你的電子信箱,我會在寫好的第一時間將文章寄送給你。

--

--

Cheng-Wei Hu | 胡程維
AppWorks School

Subscribe to chengweihu.com for new article and newsletter! 新的文章還有電子報可以在 chengweihu.com 訂閱