從斐波那契數列說起
斐波那契（Fibonacci）數列是數學中一個著名的數列，有很多神奇的特性，在多個領域有廣泛使用，定義如下數列為斐波那契數列：
該如何撰寫程式求解出斐波那契數列第n項呢？
一、遞回法
根據上述公式，可以很容易用Python實作如下代碼：
def fib(n): return n if n <= 1 else fib(n - 1) + fib(n - 2)
上述程式實作簡單，且可讀性強，只需要一行代碼即可完成，這種解法是遞回演算法，將f(n)拆分為f(n-1)與f(n-2)，在函式體內回圈呼叫函式本身，直至達到終止條件f(0)與f(1)，我們以計算f(5)為例畫圖拆分求解程序:
用同一種顏色標注的方塊為重復計算的內容，可以看到僅僅是計算f(5)，就存在非常多的重復計算情況，我們也能發現，隨著n越來越大，計算時間呈指數增長，讀者可以嘗試使用這種方法分別計算f(10)、f(20)、f(30)、f(40)、f(50)等，比較耗時增長的情況，實際上，該演算法的時間復雜度為0(2n)級別，計算效率很低，
二、遞推法
遞回演算法的計算程序是從后往前，一直計算到f(0)和f(1)，一種簡單的辦法是利用f(n)的遞推公式，從前往后，這樣避免了遞回，用一個回圈就可以直接得到結果，代碼如下：
def fib_for(n): result = [_ for _ in range(n + 1)] for i in range(2, n + 1): result[i] = result[i - 1] + result[i - 2] return result[n]
這種辦法存盤一個長度為n+1的串列，由f(0)和f(1)計算得到f(2)，再由f(1)和f(2) 計算得到f(3)，依次類推，得到f(n)，這種方法時間復雜度為0(n)級別，會很快得到期望結果，但同時我們發現，這種方法需要占用一個n+1的串列，針對這一問題，我們可以進一步優化，
我們在計算中重復使用公式f(n)=f(n-1)+f(n-2)，而該公式只占用三個變數，且最終我們只需要獲得f(n)即可，不用保留中間值，因此我們可以不要存盤串列，而采用滾動賦值的方法，做如下修改：
def fib_foropt(n): if n < 2: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b
這種方法將空間復雜度由0(n)降為0(1)，大幅節省了記憶體占用，
三、矩陣快速冪法
遞推法的時間復雜度為0(n)，矩陣快速冪法可以進一步降低時間復雜度至0(logn)，當n>1時，由f(n)=f(n-1)+f(n-2)，可以得：
重復矩陣相乘，進一步得
問題轉化為計算
，很明顯，如果
直接相乘n-1次可以得到結果，但是時間復雜度依舊是0(n)，使用快速冪法方法可以使時間復雜度降低為0(logn)，具體地，某個正整數a的n次冪an有如下性質：
我們將矩陣
套用以上公式，撰寫代碼為：
def multiply(a, b): c = [[0, 0], [0, 0]] for i in range(2): for j in range(2): c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) return c def fib_mat(n): if n < 2: return n def matrix_pow(a, m): if m == 0: return 1 if m == 1: return a res = matrix_pow(a, m >> 1) res = multiply(res, res) if m & 1: res = multiply(res, a) return res out = matrix_pow([[1, 1], [1, 0]], n - 1) return out[0][0]
分析總結
對比以上三類解法，我們可以發現，同一個問題，可以有不同的演算法解決，對于斐波那契數列問題，遞回法實作容易，可讀性好，后期易于維護，但是運行效率低，矩陣快速冪法運行效率高，占用記憶體小，但實作復雜，后期維護成本高，相對而言，遞推法編程比較容易，代碼清晰，運算速度快，更加適用于解決該問題，
不同的演算法效率不同，占用記憶體不同，撰寫復雜程度不同，后期維護的難易程度也不同，因此，在我們日常作業中，需要有意識地考慮演算法的性能，平衡編程、維護、效率等方面的關系，選擇合適的演算法，本系列后續文章會逐步介紹演算法的相關基礎知識，希望在歸納整理程序中，和讀者共同成長，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509617.html
標籤：其他
下一篇：CPU 是如何與記憶體互動的