快速計算斐波那契數列fibonacci(n)

02-07

今天課上自己獨立發現了一種比較快的計算fibonacci(n)的演算法（不知道是不是已經被人發現了，反正我是自己獨立發現的，意義在於享受創造的過程），先貼出代碼(初學python，所以只能寫這樣)，挺簡單的。

from functools import lru_cache@lru_cache(maxsize = 20)def fibo_1(n): if n < 2: return n half_1 = fibo_1((n >> 1) - 1) half = fibo_1(n >> 1) if n & 0x1: half_1 += half return half_1 * half_1 + half * half else: return half * (half + 2 * half_1)

演算法思想：

$fibo(n) =fib(n-1) + fib(n-2)$

$=1*fib(n-1)+1*fib(n-2) = fib(2)*fib(n-1)+fib(1)*fib(n-2)$

$= 2*fib(n-2)+1*fib(n-3) = fib(3)*fib(n-2)+fib(2)*fib(n-3)$

$= 3*fib(n-3)+2*fib(n-4) = fib(4)*fib(n-3)+fib(3)*fib(n-4)$

$= 5*fib(n-4)+3*fib(n-5) = fib(5)*fib(n-4)+fib(4)*fib(n-5)$ $cdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdotcdot$

於是得遞推公式：

$fib(n)=fib(k)fib(n - (k - 1)) + fib(k - 1)fib(n - k)$

n 取偶數時：

令 $k = frac{n}{2}$ ，則 $n - k = k = frac{n}{2},n - (k - 1) = k + 1$

把 $frac{n}{2}$ 作為 $k$ 代入，則：

$fib(n) = fib(frac{n}{2})cdot fib(frac{n}{2} +1) + fib(frac{n}{2} - 1)cdot fib(frac{n}{2})$

$= fib(frac{n}{2})[fib(frac{n}{2} + 1)+fib(frac{n}{2} - 1)]$

$=fib(frac{n}{2})[fib(frac{n}{2}) + 2fib(frac{n}{2} - 1)]$

n 取奇數時：

$fib(n)=fib(k)fib(n - (k - 1)) + fib(k - 1)fib(n - k)$

$=fib(k+1)fib(n - k) + fib(k)fib(n - (k+1))$

令 $k = leftlfloorfrac{n}{2} ight floor$ ，則 $k+ 1 = n - k, k = n - (k+ 1)$

把 $leftlfloorfrac{n}{2} ight floor$ 作為 $k$ 代入，即得：

$fib(n) = fib^2(leftlfloorfrac{n}{2} ight floor) + fib^2(leftlfloorfrac{n}{2} ight floor + 1)$

$= [fib(leftlfloorfrac{n}{2} ight floor)]^2+ [fib(leftlfloorfrac{n}{2} ight floor - 1)+fib(leftlfloorfrac{n}{2} ight floor)]^2$

下面是我前幾天寫的另外一段計算fibonacci(n)的代碼。因為不知道python是怎樣計算大整數加減乘除的，所以我不能簡單地說：上面那個時間複雜度為Ο(log(n))，下面這個是Ο(n)。

但你對比一下兩者的效率。比如，當n取很大時：10萬、100萬。前面一個應該會快不少。

def fibonacci(n): l, v = 0, 1 for i in range(1, n ,2): l += v v += l if n & 1: return v return l# 這個當然是最慢的了，能算完100萬就很不錯了

更新：

很多知友說上面的時間複雜的是 O(n)，自己後面分析一下似乎的確如此，但可能是因為python的某些機制，我最上面那段簡單的代碼盡然比O(log(n))的快速矩陣冪運算的那種演算法算來還要快很多，而且數據越大快的越多，大可自己去試一下。下面剛剛寫的O(log(n))的代碼，比前面遞歸實現的大概快一倍。代碼如下（還沒有系統地學python，這些都是上網搜然後套用的），以後有時間或許會補個注釋，不喜勿噴，歡迎理性的指正。如果你有更快的代碼，歡迎分享。初次在知乎上面寫文章，若有不到之出，請多多包涵。

import mathdef fibo_2(n): if n < 2: return n t = int(math.log2(n)) - 1 fibx, fiby, = 1, 0 while t > 0: last_fibx = fibx if (n >> t) & 0x1: fibx = fibx**2 + (fibx + fiby)**2 fiby = last_fibx * (last_fibx + 2 * fiby) else: fibx = fibx * (fibx + 2 * fiby) fiby = last_fibx**2 + fiby**2 t -= 1 if n & 0x1: return fibx**2 + (fibx + fiby)**2 return fibx * (fibx + 2 * fiby)

下面是網上找的矩陣快速冪運算的代碼：

def fibo_mat(n): lhm = [[0,1], [1,1]] rhm = [[0], [1]] em = [[1,0], [0,1]] # multiply two matrixes def matrix_mul(lhm, rhm): # initialize an empty matrix filled with zero result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))] # multiply loop for i in range(len(lhm)): for j in range(len(rhm[0])): for k in range(len(rhm)): result[i][j] += lhm[i][k] * rhm[k][j] return result def matrix_pow(mat, n): if n == 0: return em base = mat ans = em while n != 0: if(n & 0x1): ans = matrix_mul(ans, base) base = matrix_mul(base, base) n >>= 1 return ans return matrix_mul(matrix_pow(lhm, n), rhm)[0][0]

更新：網上找到的快速冪矩陣代碼是遞歸的，自己作死，改成了非遞歸的，反而變慢了很多，下面是原代碼（比非遞歸的快幾倍，但是依然沒有上面的fibo_1(n)和fibo_2(n)快，自己實驗一下就見分曉了）：

def fibo_mat(n): lhm = [[0,1], [1,1]] rhm = [[0], [1]] em = [[1,0], [0,1]] # multiply two matrixes def matrix_mul(lhm, rhm): # initialize an empty matrix filled with zero result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))] # multiply loop for i in range(len(lhm)): for j in range(len(rhm[0])): for k in range(len(rhm)): result[i][j] += lhm[i][k] * rhm[k][j] return result def matrix_square(mat): return matrix_mul(mat, mat) #quick transform def fib_pow(mat, n): if not n: return em elif(n & 0x1): return matrix_mul(mat,fib_pow(mat ,n - 1)) else: return matrix_square(fib_pow(mat, n >> 1)) return matrix_mul(fib_pow(lhm,n),rhm)[0][0]

這是測試用的代碼：

for i in range(0,100): mat = fibo_mat(i) if fibo_2(i) != mat or fibo_1(i) != mat: print("error !%d"%i)number = 10000000import timestart = time.clock()fibo_2(number)finish = time.clock()print("fibo_2(%d): Cost time : %f sec"%(number, finish - start))start = time.clock()fibo_1(number)finish = time.clock()print("fibo_1(%d): Cost time : %f sec"%(number, finish - start))start = time.clock()fibo_mat(number)finish = time.clock()print("fibo_mat(%d): Cost time : %f sec"%(number, finish - start))