面试题10.1：斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

知识点

递归，循环

---

Qiang的思路V1

提及斐波那契数列，马上能够想起它的公式：

接着，对应的递归实现方法也就出现在了脑海里。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1:
            return 1
        return self.Fibonacci(n-1)+self.Fibonacci(n-2)

但是，使用递归的时候存在很大的一个问题，就是从0到n的这些项需要重复计算好几次，这也就导致了时间的高开销。

由于递归能解决的问题循环基本都能解决，所以使用循环解决该问题的方法也就呼之欲出了。

---

Qiang的思路V2

因为我们要计算的是第n项的值，他需要前两项的和，前一项又需要再前两项的和……，所以我们可以反着来，先求第0和1项，然后第2项，第3项……，直到第n项。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1:
            return 1
        before1=1
        before2=0
        for i in range(2,n):
            before=before1
            before1+=before2
            before2=before
        return before1+before2

使用循环之后，对于每一项的值只需要计算一个即可，其时间复杂度为O(n)，大大加快了效率。

---

Book中的思路

在书中，作者又给提供了一种非常牛逼的解法。给出了斐波那契数列的一个矩阵形式的计算公式：

作者书中没有给出证明过程，我在这里稍微写一下其证明过程

大体一写，大家勉强看一下啊，应该还是能看懂的吧。

根据这个公式我们就能够知道斐波那契数列可以通过矩阵乘法的方式求得。但是如果直接这样进行代码编写，因为需要从0求到n的值，所以还是O(n)的时间复杂度。

进一步，由于乘方运算具有如下特点：

类似于折半，可以通过递归的形式将其实现。

# -*- coding:utf-8 -*-
class Solution:
    def mulMatrix(self, matrix1, matrix2):
        matrix=[[0 for i in range(2)] for j in range(2)]
        matrix[0][0]=matrix1[0][0]*matrix2[0][0]+matrix1[0][1]*matrix2[1][0]
        matrix[0][1]=matrix1[0][0]*matrix2[0][1]+matrix1[0][1]*matrix2[1][1]
        matrix[1][0]=matrix1[1][0]*matrix2[0][0]+matrix1[1][1]*matrix2[1][0]
        matrix[1][1]=matrix1[1][0]*matrix2[0][1]+matrix1[1][1]*matrix2[1][1]
        return matrix
        
    def getResult(self, matrix, n):
        if n==1:
            return matrix
        _matrix=self.getResult(matrix, int(n/2))
        matrix_=self.mulMatrix(_matrix, _matrix)
        if n%2==0:
            return matrix_
        return self.mulMatrix(matrix_, matrix)
        
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1:
            return 1
        matrix=[[1,1],[1,0]]
        return self.getResult(matrix, n-1)[0][0]

该算法的时间复杂度为O(logn)。但是对于这种方法，每次需要进行矩阵的方法，所以其隐含的时间常数还是比较大的。但总体来说，这真的是一个非常神奇的解法。

---

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。