python斐波那契數(shù)列的計算方法
題目:
計算斐波那契數(shù)列。具體什么是斐波那契數(shù)列,那就是0,1,1,2,3,5,8,13,21,34,55,89,144,233。
要求:
時間復雜度盡可能少
分析:
給出了三種方法:
方法1:遞歸的方法,在這里空間復雜度非常大。如果遞歸層數(shù)非常多的話,在python里需要調(diào)整解釋器默認的遞歸深度。默認的遞歸深度是1000。我調(diào)整了半天代碼也沒有調(diào)整對,因為遞歸到1000已經(jīng)讓我的電腦的內(nèi)存有些撐不住了。
方法2:將遞歸換成迭代,這樣時間復雜度也在代碼中標注出來了。
方法3:這種方法利用了求冪的簡便性,采用了位運算。但是代價在于需要建立矩陣,進行矩陣運算。所以,當所求的數(shù)列的個數(shù)較小時,該方法還沒有第二種簡便。但是當取的索引值n超級大時,這種方法就非常方便了。時間復雜度在代碼中標注出來了。
代碼:
#!usr/bin/python2.7 # -*- coding=utf8 -*- # @Time : 18-1-3 下午2:53 # @Author : Cecil Charlie import sys import copy sys.setrecursionlimit(1000) # 用來調(diào)整解釋器默認最大遞歸深度 class Fibonacci(object): def __init__(self): pass def fibonacci1(self, n): ''' 原始的方法,時間復雜度為 o(2**n),因此代價較大 :param n: 數(shù)列的第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): """ 用循環(huá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): """ 進一步減少迭代次數(shù),采用矩陣求冪的方法,時間復雜度為o(log n),當然了,這種方法需要額外計算矩陣,計算矩陣的時間開銷沒有算在內(nèi).其中還運用到了位運算。 """ 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: # 按位與的操作,在冪數(shù)的二進制位為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)
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
Python從list類型、range()序列簡單認識類(class)【可迭代】
這篇文章主要介紹了Python從list類型、range()序列簡單認識類(class),結合實例形式分析了list、range及自定義類等可迭代數(shù)據(jù)類型相關使用技巧,需要的朋友可以參考下2019-05-05mac系統(tǒng)下安裝pycharm、永久激活、中文漢化詳細教程
這篇文章主要介紹了mac系統(tǒng)下安裝pycharm、永久激活、中文漢化詳細教程,需要的朋友可以參考下2020-11-11用python監(jiān)控服務器的cpu,磁盤空間,內(nèi)存,超過郵件報警
這篇文章主要介紹了如果用python監(jiān)控服務器的cpu,磁盤空間,內(nèi)存,超過郵件報警,幫助大家更好的理解和使用python,感興趣的朋友可以了解下2021-01-01記一次pyinstaller打包pygame項目為exe的過程(帶圖片)
這篇文章主要介紹了記一次pyinstaller打包pygame項目為exe的過程,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-03-03