Python 費氏數列解法(一)

面試被問到的題目,雖然是很基本的題目,但相關延伸也有不少,寫篇文章記錄一下。

遞迴:最基本又直觀的解法

def fibonacci(n):
    if n < 3:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

時間複雜度

$O(2^n)$,每次呼叫 fibonacci(n) 都會進行額外兩次呼叫,n 每次會 -1,直到 n == 2。整個呼叫會是高度 n 的二元樹的子集合,而每次運行時間都是 $O(1)$,因此整體時間的 upper bound 就是二元樹的節點數量:

$$
2^0 + 2^1 + 2^2 + … + 2^{n-1} = \frac{2^n - 1}{2 - 1}
$$

空間複雜度

$O(1)$

遞迴優化:利用 Hash 減少計算次數

在原本的解法中,會有很多次重複計算 fibonacci(n-1), fibonacci(n-2) … 等,因此可以把計算結果儲存起來,

def fibonacci(n):
    table = {}
    def fib_table(n):
        if n < 3:
            return 1
        table[n] = fib_table(n-1) + fib_table(n-2)
        return table[n]
    return fib_table(n)

這邊我利用了 Python 變數 scope 的 LEGB 特性,也就是查找順序為:local, enclosed, global, built-in。可以參見官方 document,有趣的是 LEGB 並不是官方名詞而是社群流傳的口訣。

也許聽起來很複雜,但其實也就是簡單的往外查找規則罷了。

因此 table 雖然是在外部的 fibonacci 定義的,但 fib_table 內(local)沒有另外定義 table 變數的情況下,會往外查找,因此可以讀取外部的 table(enclosed)。

可能有人會問,我有 assign 值到 table 內部啊,這樣不用宣告 global table 嗎?答案是不需要的,在 Python 中,table 變數存的是物件的 reference,因此改變物件內的屬性並不會影響 table 這個變數。而 table[n] = fib_table(n-1) + fib_table(n-2) 這行實際上是呼叫了 table 指向的物件的 __setitem__ 方法,改變物件內部的屬性。

時間複雜度

$O(n)$,對每個 n 只需要算一遍,不會每次都要往 n-1,n-2 展開。

空間複雜度

$O(n)$,table 需要存 fib_table(3)fib_table(n) 的結果。

遞迴優化:使用 Cache

Python 有內建的 Cache 可以記錄函式呼叫結果:

@cache
def fibonacci(n):
    if n < 3:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

這其實就是第一個解法加上一行 @cache 而已。

在函式開頭加上 @something 的寫法是呼叫 Python 中的 decorator,是 Python 中一個重要的特性。在 Python 語言中,函式是一等公民,也就是函式可以被當作變數 assign,也可以當作參數傳遞。 decorator 實際上就是把他裝飾的函式傳到 decorator 內部再做一些事情,以這邊的 @cache 為例,decorator 會自動幫忙把 fibonacci 這個函式的呼叫結果記錄起來,並回傳包裝後的函數,我們最後拿到的 fibonacci 實際上會多了包裝後的方法:

> fibonacci.__dir__()
['cache_parameters',
 ...
 'cache_info',
 'cache_clear',
 ...
]

比自己用 hash 實作簡單多了。

這邊的 cache 實際上是 functools.lru_cache(maxsize=None),一個不限制大小的 LRU Cache,如果想要限制大小可以在修改 maxsize 發揮 LRU 的功能。

學會了這招才是真正的 Pythonist。

Cache Size 要設定成多少?

既然可以設定 cache size,我們真的需要一直記著每次計算的結果嗎?

當計算第 n 項時,只需要 n-1 和 n-2 兩項結果,所以就設成 2 就好了對吧?但如果直接這樣改,會發現程式跑的時間還是會變很長。

實際上當計算 n-1 時,需要知道 n-2 和 n-3 的值,先計算 n-2 後計算 n-3。因此最後 cache 內記錄的會是 n-1 和 n-3 的值。
所以會在接下來算 n-2 時造成一個 cache miss。

如果不改其他部分,可以把 maxsize 設成 3,就可以避免掉這個 cache miss。

但仔細思考,其實會有這個 miss,歸根究底是我們先計算比較靠近 n 的 n-1,後計算比較遠離 n 的 n-2 造成的。那何不將兩者交換呢?

@lru_cache(maxsize=2)
def fibonacci(n):
    if n < 3:
        return 1
    return fibonacci(n-2) + fibonacci(n-1)

做完簡單的修改,一樣漂亮的 code,可以給出不錯的時間複雜度和常數的空間複雜度。

時間複雜度

$O(n)$,不會有 cache miss,每個 n 只需要計算一次。

空間複雜度

$O(1)$,因為 cache size 最大是 2。

尾遞迴 Tail Recursive / Tail Call

當函式本身在回傳時會呼叫自己即為尾遞迴,可以說是遞迴中的特例。

要撰寫尾遞迴,需要思考每次遞迴時我們往前取了什麼資訊。在上一個 LRU cache 的解法中知道,我們只需要紀錄 n-2 和 n-1 兩個值即可。分別命名為 f1f2,每次呼叫我們把 n 減 1,把 f1 指定為 f2,並把 f2 改為 f1 + f2

def fibonacci(n):
    def fib_tail_recursive(n, f1, f2):
        if n < 3:
            return f2
        return fib_tail_recursive(n - 1, f2, f1 + f2)
    return fib_tail_recursive(n, 1, 1)

尾遞迴的版本我認為比較不好理解,但是為了下一個迭代法,還是練習了一下尾遞迴的解法。

下面對於不同的 n 做分析:

  • 初始時 f1f2 分別代表第一項和第二項,都是 1。
  • 當 n < 3 時直接回傳 f1 為 1
  • 當 n = 3 時,會跑一次尾遞迴,此時 n 變成 2,f1 變成 1, f2 變成 1 + 1 = 2,接著回傳 f2 即為 2

以下依此類推…

時間複雜度

$O(n)$,從 n 呼叫到 2。

空間複雜度

$O(1)$,沒有額外的 cache 或是查表。

迭代法:使用迴圈,攤平遞迴

尾遞迴是攤平遞迴的中間做法,可以寫成尾遞迴的函式,就能快速改寫成迭代形式:

def fibonacci(n):
    f1, f2 = 1, 1
    for i in range(2, n):  # 當 n < 3 時不會進入迴圈
        f1, f2 = f2, f1 + f2
    return f2

做的事情和尾遞迴版本一模一樣。

也因此有些語言對於尾遞迴有做優化,當編譯器看到尾遞迴,會自動幫你攤平成迴圈(用 GOTO 實現),稱為尾遞迴優化(Tail Call Optimization)。主要會在以 functional programming 為主的語言中看到,例如 erlang 或是 haskell。

很可惜,Python 是沒有支援的那部分。

時間複雜度

$O(n)$,只有一個迴圈,迴圈內部運算都是 $O(1)$

空間複雜度

$O(1)$,只用了固定兩個變數

其他解法

雖然到這邊已經說明完正常的解法,但其實費氏數列還有更多有趣的解法。

時間複雜度更短的 $O(\lg n)$ 的:

以及所有解法的執行時間比較