python斐波那契数列的计算方法

yipeiwu_com5年前Python基础

题目:

计算斐波那契数列。具体什么是斐波那契数列,那就是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)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

学习python 之编写简单乘法运算题

实现代码: #! /usr/bin/python //处理程序 #filename jiafa.py //文件名 import sys import r...

Python面向对象之类的封装操作示例

本文实例讲述了Python面向对象之类的封装操作。分享给大家供大家参考,具体如下: 承接上一节《Python面向对象之类和实例》,学了Student类的定义及实例化,每个实例都拥有各自的...

Python中设置变量作为默认值时容易遇到的错误

思考一下下面的代码片段:   def foo(numbers=[]): numbers.append(9) print numbers 在这里,我们定义了一个...

Python:Numpy 求平均向量的实例

如下所示: >>> import numpy as np >>> a = np.array([[1, 2, 3], [3, 1, 2]]) >...

12步入门Python中的decorator装饰器使用方法

装饰器(decorator)是一种高级Python语法。装饰器可以对一个函数、方法或者类进行加工。在Python中,我们有多种方法对函数和类进行加工,比如在Python闭包中,我们见到函...