python中怎么計(jì)算斐波那契數(shù)列

這期內(nèi)容當(dāng)中小編將會給大家?guī)碛嘘P(guān)python中怎么計(jì)算斐波那契數(shù)列，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

題目：

計(jì)算斐波那契數(shù)列。具體什么是斐波那契數(shù)列，那就是0，1，1，2，3，5，8，13，21，34，55，89，144，233。

要求：

時(shí)間復(fù)雜度盡可能少

分析：

給出了三種方法：

方法1：遞歸的方法，在這里空間復(fù)雜度非常大。如果遞歸層數(shù)非常多的話，在python里需要調(diào)整解釋器默認(rèn)的遞歸深度。默認(rèn)的遞歸深度是1000。我調(diào)整了半天代碼也沒有調(diào)整對，因?yàn)檫f歸到1000已經(jīng)讓我的電腦的內(nèi)存有些撐不住了。

方法2：將遞歸換成迭代，這樣時(shí)間復(fù)雜度也在代碼中標(biāo)注出來了。

方法3：這種方法利用了求冪的簡便性，采用了位運(yùn)算。但是代價(jià)在于需要建立矩陣，進(jìn)行矩陣運(yùn)算。所以，當(dāng)所求的數(shù)列的個(gè)數(shù)較小時(shí)，該方法還沒有第二種簡便。但是當(dāng)取的索引值n超級大時(shí)，這種方法就非常方便了。時(shí)間復(fù)雜度在代碼中標(biāo)注出來了。

代碼：

#!usr/bin/python2.7
# -*- coding=utf8 -*-
# @Time  : 18-1-3 下午2:53
# @Author : Cecil Charlie

import sys
import copy
sys.setrecursionlimit(1000) # 用來調(diào)整解釋器默認(rèn)最大遞歸深度


class Fibonacci(object):
  def __init__(self):
    pass

  def fibonacci1(self, n):
    '''
      原始的方法，時(shí)間復(fù)雜度為 o(2**n)，因此代價(jià)較大
    :param n: 數(shù)列的第n個(gè)索引
    :return: 索引n對應(yīng)的值
    '''
    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)替代遞歸，空間復(fù)雜度急劇降低，時(shí)間復(fù)雜度為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):
    """
      進(jìn)一步減少迭代次數(shù)，采用矩陣求冪的方法，時(shí)間復(fù)雜度為o(log n)，當(dāng)然了，這種方法需要額外計(jì)算矩陣，計(jì)算矩陣的時(shí)間開銷沒有算在內(nèi).其中還運(yùn)用到了位運(yù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):
    """
      求一個(gè)方陣的冪
    """
    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ù)的二進(jìn)制位為1時(shí)，乘到最終結(jié)果上，否則自乘
        product = self.__multiply_matrix(product, tmp)
      tmp = self.__multiply_matrix(tmp, tmp)
      n >>= 1
    return product

  @staticmethod
  def __multiply_matrix(mat1, mat2):
    """
      矩陣計(jì)算乘積
    :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中怎么計(jì)算斐波那契數(shù)列了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。