題目：

計算斐波那契數列。具體什么是斐波那契數列，那就是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)) != "":

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)

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

總結

以上是生活随笔為你收集整理的斐波那契的数列的计算python-python斐波那契数列的计算方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。