算法之矩陣計算斐波那契數列

算法之矩陣計算斐波那契數列

本節內容

1. 斐波那契介紹
2. 普通方式求解斐波那契
3. 矩陣概念
4. 矩陣求冪
5. 矩陣求解斐波那契

1.斐波那契介紹

斐波那契數列有關十分明顯的特點，那是：前面相鄰兩項之和，構成了后一項。即f(n)=f(n-1)+f(n-2),f(0)=0,f(1)=f(2)=1,推導下去f(3)=2,f(4)=3,f(5)=5。。。。。。

2.普通方式求解斐波那契

按照上面提供的推導公式，普通方式求解斐波那契數列代碼如下：

def normal(n):
    a,b,c=0,1,1
    while n:
        a,b,c=b,c,b+c
        n-=1
    return a

?

使用上面的方式求解第n項斐波那契數列的時間復雜度為O(n),也就是說，時間復雜度隨著n的增長而線性增長。

3.矩陣概念

開始，先來介紹一下矩陣的概念：在數學中，矩陣（Matrix）是一個按照長方陣列排列的復數或實數集合，最早來自于方程組的系數及常數所構成的方陣。

這里不介紹矩陣的各方面知識了，如果那樣的話。。。就是一篇數學筆記了。。。這里只講解矩陣相乘的概念。

矩陣相乘：矩陣相乘最重要的方法是一般矩陣乘積。它只有在第一個矩陣的列數（column）和第二個矩陣的行數（row）相同時才有意義。一般單指矩陣乘積時，指的便是一般矩陣乘積。一個m×n的矩陣就是m×n個數排成m行n列的一個數陣。由于它把許多數據緊湊的集中到了一起，所以有時候可以簡便地表示一些復雜的模型。

設A為m*p的矩陣，B為p*n的矩陣，那么稱m*n的矩陣C為矩陣A與B的乘積，記作C=AB：

4.矩陣求冪

上面已經介紹過了矩陣相乘的概念了，那么，斐波那契該怎么由矩陣標示呢？

從第三項開始，每一項都是前兩項之和。 F(n)=F(n?1)+F(n?2), n?3 把斐波那契數列中 相鄰的兩項F(n)和F(n?1)寫成一個2×1的矩陣。

斐波那契數列用矩陣推導如下：

求F(n)等于求二階矩陣的n - 1次方，結果取矩陣第一行第一列的元素。

問題轉換為二階矩陣的n次冪。

而計算二階矩陣的N次冪運算，由于二階矩陣乘法滿足結合律，這樣，可以快速計算二階矩陣的n次冪運算。

假設A為一個二階矩陣，則A的冪運算滿足下面的條件：

A**6=A**3?A**3

A**7=A**3?A**3?A**1=A**4*A**2*A**1

在這里，我們可以類似地把A看做是二進制中的2，2**7=2**4*2**2*2**1也就是說可以把矩陣的冪轉換成二進制來表示。從而可以將n次冪拆解成長度為logn的二進制數來表示：7=111(二進制)。

這就是快速求二階矩陣的核心方法。

5. 矩陣求解斐波那契

前戲做足了，下面就該秀代碼了。

def multi(a,b):  # 計算二階矩陣的相乘
    c=[[0,0],[0,0]]  # 定義一個空的二階矩陣
    for i in range(2):
        for j in range(2):
            for k in range(2):  # 新二階矩陣的值計算
                c[i][j]=c[i][j]+a[i][k]*b[k][j]
    return c


def matrix(n):
    base=[[1,1],[1,0]]  # 元矩陣，這里可以把元矩陣看做是2**0=1
    ans=[[1,0],[0,1]]  # 結果矩陣  最開始的結果矩陣也可以看做是1，因為這個矩陣和任意二階A矩陣相乘結果都是A
    while n:
        if n&1:  # 取n的二進制的最后一位和1做與運算，如果最后一位是1，則進入if體內部
            ans=multi(ans,base)  # 如果在該位置n的二進制為1，則計算ans和base矩陣
        base=multi(base,base)  # base矩陣相乘，相當于初始base矩陣的冪*2
        n>>=1  # n的二進制往右移一位
    return ans[0][1]  # 最后獲取到的二階矩陣的[0][1]即f(n)的值

?

最后把例子的完整代碼貼出來：

import time


def multi(a,b):
    c=[[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j]=c[i][j]+a[i][k]*b[k][j]
    return c


def matrix(n):
    base=[[1,1],[1,0]]
    ans=[[1,0],[0,1]]
    while n:
        if n&1:
            ans=multi(ans,base)
        base=multi(base,base)
        n>>=1
    # for i in range(2):
    #     print(ans[i])
    return ans[0][1]

def normal(n):
    a,b,c=0,1,1
    while n:
        a,b,c=b,c,b+c
        n-=1
    return a

n=int(input(">>>"))
start=time.time()
print("Normal:",normal(n))
print("use:",time.time()-start)
start=time.time()
print("Matrix:",matrix(n))
print("use:",time.time()-start)
#計算結果
>>>65536
Normal: 731992144602......
use: 0.07219505310058594
Matrix: 731992144602......
use: 0.023076772689819336

?

可以看出來當n的值越來越大的時候，兩種方式計算出結果的時間差距將越來越大，正常的計算時間復雜度是O(n),矩陣求值的時間復雜度是O(logn)。

后記：

由此可以看出，使用推導式f(n)=f(n-1)+f(n-2)求斐波那契的第n項的算法復雜度極限為O(n)，這是一維世界下的極限。將其從一維上升到二維，用二階矩陣推導斐波那契數列時，計算的算法復雜度為O(logn)，也就是說，使用升維的手段將一維空間進行扭曲從而將距離縮短，可以更快的計算出結果。

由此推導出如果人來要突破光速的極限，需要將現有的三維空間升級到四維空間，扭曲空間從而縮短距離，達到突破光速的目的。