關(guān)于斐波那契數(shù)列求值問題

斐波那契數(shù)列

斐波那契數(shù)列是一個(gè)經(jīng)典的數(shù)學(xué)問題，同時(shí)也是算法中的經(jīng)典案例莉擒，并且衍生出了很多類似的問題贿条，這個(gè)問題簡單來說就是當(dāng)前數(shù)列的元素是由前兩個(gè)數(shù)的和構(gòu)成粹懒。不如舉個(gè)栗子：

比如 F(0) = 0, F(1) = 1, 那么 F(2) = F(0) + F(1)，也就是說F(2) = 0 + 1 = 2勺像，依次循環(huán)得出相關(guān)的數(shù)列內(nèi)容障贸。

所以依據(jù)這樣的規(guī)律特點(diǎn)，我們可以寫出下面的遞推內(nèi)容：

F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
F(5) = F(4) + F(3)
F(6) = F(5) + F(4)
......

遞歸解法

這就明顯感覺是迭代求值的關(guān)系吟宦，所以依據(jù)這樣的特點(diǎn)篮洁，可以采用最基本的遞歸的方法去完成求值。實(shí)現(xiàn)內(nèi)容如下：

func fibRecurrence(_ n: Int) -> Int {
        if n == 0 {
            return 0
        }
        if n == 1 {
            return 1
        }
        return fib(n - 1) + fib(n - 2)
    }

但是仔細(xì)看一下當(dāng)前的時(shí)間復(fù)雜度殃姓，會(huì)發(fā)現(xiàn)是O(2^n)的袁波，效率略微有點(diǎn)差瓦阐。

正推法求值

遞歸的方法求值實(shí)際上是從n往0，反向遞推求其值篷牌，但是這樣有一個(gè)不好的地方在于重復(fù)計(jì)算了已經(jīng)算過的值睡蟋，例如在求解F(5)的時(shí)候內(nèi)容如下:

F(5) = F(4) + F(3)

再去求解F(4)的時(shí)候，你會(huì)發(fā)現(xiàn)F(3)重復(fù)計(jì)算了兩次枷颊，如下：

F(4) = F(3) + F(2)

按照此內(nèi)容推下去戳杀，計(jì)算就會(huì)增倍了。如果按照正向遞推的方式的話偷卧，就剛好解決了這樣的問題豺瘤，在求解F(5)的時(shí)候已經(jīng)正向求解F(4)與F(3)的結(jié)果了，所以直接累加即可得其結(jié)果听诸。所以按照這樣的思路坐求，我們可以正向遞推求值：

func fibCount(_ n: Int) -> Int {
        if n == 0 {
            return 0
        }
        if n == 1 {
            return 1
        }
        var curValue = 1
        var preValue = 0
        var resValue = curValue + preValue
        for _ in 2...n {
            resValue = curValue + preValue
            preValue = curValue
            curValue = resValue
        }
        return resValue
    }

這個(gè)時(shí)間復(fù)雜度是O(n)的。

矩陣乘法

真正的O(n)就是最優(yōu)解了嘛晌梨？答案是否定的桥嗤，因?yàn)橛袀€(gè)神級的解法，叫做升維跨越仔蝌，可以將其時(shí)間復(fù)雜度變成O(logn)的泛领，具體做法就是利用矩陣乘法。

矩陣推理

矩陣推理

所以經(jīng)過一系列的推倒敛惊，矩陣變換成了如下的內(nèi)容：

最終形式

所以這個(gè)遞推升維公式就成功的將F(n)的求解變成了二維矩陣的求冪問題渊鞋。

這里解釋一下為什么要將左邊的格式改成2x2的寫法？原因很簡單瞧挤，是為了保證與右邊的2x2保持對應(yīng)锡宋，這樣的話比較直觀，很快就能確定F(n)對應(yīng)于矩陣的哪個(gè)元素了特恬。比如這里的F(n)=Martrix[0][1]元素执俩。

矩陣求解問題轉(zhuǎn)換

此時(shí)如果把矩陣內(nèi)容看成一個(gè)元素x，那么右邊的內(nèi)容就變成了求解x的n次冪癌刽，這樣的話役首，我們可以通過計(jì)算x的n次冪來求的x的值了

關(guān)于求解x的n次冪問題
這里有兩種方式去計(jì)算x的n次冪。分別是拆分分治的方法與按位運(yùn)算取值显拜。

分治遞歸方法如下：

    /*
     使用拆分法衡奥，又叫分治歸并算法
     由于每次計(jì)算均為減半運(yùn)算 
     所以時(shí)間復(fù)雜度O(logn)
     */
    func powSplit(_ x: Int, _ n: Int) -> Int {
        if n == 0 {
            return 1
        }
        if n == 1 {
            return x
        }
        //偶數(shù)
        if n & 1 == 0 {
            return self.powSplit(x, n/2) * self.powSplit(x, n/2)
        }
        //奇數(shù)
        return self.powSplit(x, (n-1)/2) * self.powSplit(x, (n-1)/2) * x
    }

采用按位取值的方法如下：

func powByByte(_ x: Int, _ n: Int) -> Int {
        if x == 0 {
            return 0
        }
        if x == 1 {
            return x
        }
        var localN = n
        var localX = x
        var result = 1
        while localN != 0 {
            //當(dāng)前位有效，乘以權(quán)值
            if localN & 1 != 0 {
                result  = localX * result
            }
            //移位之前要按位加權(quán)
            localX = (localX * localX)
            localN = localN>>1
        }
        return result
    }

這里特別注意的一點(diǎn)是加權(quán)的時(shí)候远荠，需要當(dāng)前值的平方操作杰赛，如果按照二進(jìn)制進(jìn)行排列的話，當(dāng)前位置的平方是下一位權(quán)重的權(quán)值內(nèi)容矮台。例如：

image.png

所以這里要乘以當(dāng)前位的自身值乏屯，來確定下一個(gè)位的權(quán)重值內(nèi)容。將矩陣看成冪乘積之后瘦赫，會(huì)發(fā)現(xiàn)關(guān)于矩陣乘積的方法又涉及到矩陣相乘的問題辰晕。

矩陣乘法

矩陣乘法的概念這里就不多說了，直接看一下代碼實(shí)現(xiàn)确虱。

    /*
     矩陣乘法算法
     */
    func MartrixMutiply(_ leftMartrix: [[Int]], _ rightMartrix: [[Int]]) -> [[Int]] {
        var resMartrix = [[Int]]()
        var rowArr = [Int]()
        for row in 0..<leftMartrix.count{
            for col in 0..<rightMartrix[0].count{
                rowArr.append(self.countElementIndex(leftMartrix, row, rightMartrix, col))
            }
            resMartrix.append(rowArr)
            rowArr.removeAll()
        }
        return resMartrix
    }
    
    /*
     計(jì)算某行元素與某一列元素的乘積和
     */
    func countElementIndex(_ leftArray: [[Int]], _ rowIndex: Int, _ rightArray: [[Int]], _ colIndex: Int ) -> Int {
        
        //要符合兩個(gè)矩陣相乘的前提
        guard leftArray.count == rightArray[0].count else {
            return -1
        }
        
        var result = 0
        for index in 0..<leftArray.count {
            result = result + leftArray[rowIndex][index] * rightArray[index][colIndex]
        }
        
        return result
    }

最終我們通過將矩陣看成一個(gè)整體含友，對其內(nèi)容的求解轉(zhuǎn)變?yōu)榍蠼鈞的n次方的問題，所以可以實(shí)現(xiàn)如下的代碼：

    /*
     升冪運(yùn)算校辩，依據(jù)矩陣推倒公式窘问，相關(guān)的算法例如求解x的n次冪:x^n
     */
    func powMartrix(_ x: [[Int]], _ n: Int) -> [[Int]] {
        //先變成單位矩陣
        var result = [[1,0],[0,1]]
        var localN = n
        var localX = x
        while localN != 0 {
            if localN & 1 != 0{
                result = self.MartrixMutiply(localX, result)
            }
            localX = self.MartrixMutiply(localX, localX)
            localN = localN >> 1
        }
        
        return result
    }

依據(jù)公式F(n)對應(yīng)位置剛好在Martrix[0][1]的位置，所以直接返回當(dāng)前元素的值也即可得出F(n)的結(jié)果宜咒。如下：

    /*
     測試求值
     */
    func fibTestDemo(_ n: Int) -> Int {
        let res = self.fibMatrix(n)
        return res[0][1]
    }

利用矩陣來完成斐波那契的問題惠赫，是目前所能發(fā)現(xiàn)的算法的最優(yōu)解，時(shí)間復(fù)雜度位O(logn)故黑，這樣的優(yōu)質(zhì)解法我覺得還是有必要掌握一下的儿咱，畢竟屬于基本算法的范疇，值得深思與思考场晶，更能夠加強(qiáng)我們分析問題的能力混埠，這也是眾多公司要求開發(fā)者理解并且會(huì)適當(dāng)?shù)氖褂盟惴ǖ脑虬桑傊幔刻爝M(jìn)步一點(diǎn)點(diǎn)钳宪，何樂而不為呢~