【算法】斐波那契数列的计算方法

拼搏现实的明天。 2022-06-02 04:43 170阅读 0赞

**题目**：  
计算斐波那契数列。具体什么是斐波那契数列，那就是0，1，1，2，3，5，8，13，21，34，55，89，144，233。

**要求**：  
时间复杂度尽可能少

**分析**：  
给出了三种方法：

*  方法1：递归的方法，在这里空间复杂度非常大。如果递归层数非常多的话，在python里需要调整解释器默认的递归深度。默认的递归深度是1000。我调整了半天代码也没有调整对，因为递归到1000已经让我的电脑的内存有些撑不住了。
 *  方法2：将递归换成迭代，这样时间复杂度也在代码中标注出来了。
 *  方法3：这种方法利用了求幂的简便性，采用了位运算。但是代价在于需要建立矩阵，进行矩阵运算。所以，当所求的数列的个数较小时，该方法还没有第二种简便。但是当取的索引值n超级大时，这种方法就非常方便了。时间复杂度在代码中标注出来了。

**代码**：

#!usr/bin/python2.7
    # -*- coding=utf8 -*-
    # @Time   : 18-1-3 下午2:53
    # @Author : Cecil Charlie
    
    import sys
    import copy
    sys.setrecursionlimit(1000)  # 用来调整解释器默认最大递归深度
    
    
    class Fibonacci(object):
        def __init__(self):
            pass
    
        def fibonacci1(self, n):
            '''
                原始的方法，时间复杂度为 o(2**n)，因此代价较大
            :param n: 数列的第n个索引
            :return: 索引n对应的值
            '''
            if n < 1:
                return 0
            if n == 1 or n == 2:
                return 1
            return self.fibonacci1(n-1) + self.fibonacci1(n-2)
    
        @staticmethod
        def fibonacci2(n):
            """
                用循环替代递归，空间复杂度急剧降低，时间复杂度为o(n)
            """
            if n < 1:
                return 0
            if n == 1 or n == 2:
                return 1
            res = 1
            tmp1 = 0
            tmp2 = 1
            for _ in xrange(1, n):
                res = tmp1 + tmp2
                tmp1 = tmp2
                tmp2 = res
            return res
    
        def fibonacci3(self, n):
            """
                进一步减少迭代次数，采用矩阵求幂的方法，时间复杂度为o(log n)，当然了，这种方法需要额外计算矩阵，计算矩阵的时间开销没有算在内.其中还运用到了位运算。
            """
            base = [[1, 1], [1, 0]]
            if n < 1:
                return 0
            if n == 1 or n == 2:
                return 1
            res = self.__matrix_power(base, n-2)
            return res[0][0] + res[1][0]
    
        def __matrix_power(self, mat, n):
            """
                求一个方阵的幂
            """
            if len(mat) != len(mat[0]):
                raise ValueError("The length of m and n is different.")
            if n < 0 or str(type(n)) != "<type 'int'>":
                raise ValueError("The power is unsuitable.")
            product, tmp = [], []
            for _ in xrange(len(mat)):
                tmp.append(0)
            for _ in xrange(len(mat)):
                product.append(copy.deepcopy(tmp))
            for _ in xrange(len(mat)):
                product[_][_] = 1
            tmp = mat
            while n > 0:
                if (n & 1) != 0:  # 按位与的操作，在幂数的二进制位为1时，乘到最终结果上，否则自乘
                    product = self.__multiply_matrix(product, tmp)
                tmp = self.__multiply_matrix(tmp, tmp)
                n >>= 1
            return product
    
        @staticmethod
        def __multiply_matrix(mat1, mat2):
            """
                矩阵计算乘积
            :param m: 矩阵1，二维列表
            :param n: 矩阵2
            :return: 乘积
            """
            if len(mat1[0]) != len(mat2):
                raise ValueError("Can not compute the product of mat1 and mat2.")
            product, tmp = [], []
            for _ in xrange(len(mat2[0])):
                tmp.append(0)
            for _ in xrange(len(mat1)):
                product.append(copy.deepcopy(tmp))
            for i in xrange(0, len(mat1)):
                for j in xrange(0, len(mat2[0])):
                    for k in xrange(0, len(mat1[0])):
                        if mat1[i][k] != 0 and mat2[k][j] != 0:
                            product[i][j] += mat1[i][k] * mat2[k][j]
            return product
    
    
    f = Fibonacci()
    print f.fibonacci1(23)
    print f.fibonacci2(23)
    mat1 = [[2,4,5],[1,0,2],[4,6,9]]
    mat2 = [[2,9],[1,0],[5,7]]
    print f.fibonacci3(23)