斐波那契数列(python实现)

斐波那契数列的形式如下:
f(0)=0,f(1)=1,f(2)=1,当n>=3时,f(n)=f(n-1)+f(n-2)
分析可以发现:n大于等于3时,每次计算都会使用到最近的前面连个元素,如果直接使用递归的方式计算的话,时间复杂度太高,所以这里可以使用一个两元素的列表,用于交替存储每次计算后的结果,最后根据n的奇偶性输出列表中的对应元素即为最终的结果。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #if n <= 1:
        #    return n
        #return self.Fibonacci(n-1) + self.Fibonacci(n-2)   #计算复杂度为2^n,太高
        if n <=1:
            return n
        else:
            a = [1,1]
            for i in range(3,n+1):
                if i % 2 != 0:
                    a[0] = a[0] + a[1]
                else:
                    a[1] = a[0] + a[1]
            if n % 2 == 0:
                return a[1]
            else:
                return a[0]

时间复杂度为:O(n)

全部评论

相关推荐

一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:10
码农索隆:成年人最直白的答复:已读不回
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务