Python开发【算法】:斐波那契数列两种时间复杂度

综合编程 2018-03-13

斐波那契数列

概述:

斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

求解:

求解斐波那契数列的F(n)有两种常用算法:递归算法和非递归算法。试分析两种算法的时间复杂度。

1 递归算法

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def fibonacci(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

fibonacci(100)

时间复杂度:求解F(n),必须先计算F(n-1)和F(n-2),计算F(n-1)和F(n-2),又必须先计算F(n-3)和F(n-4)。。。。。。以此类推,直至必须先计算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的结果,从而得到F(n)要计算很多重复的值,在时间上造成了很大的浪费,算法的时间复杂度随着N的增大呈现指数增长,时间的复杂度为O(2^n),即2的n次方

2 非递归算法

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def fibonacci(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        num1 = 1
        num2 = 1
        for i in range(2,n-1):
            num2 = num2 + num1
            num1 = num2 - num1
        return num1 + num2
print(fibonacci(100))

算法复杂度:从n>2开始计算,用F(n-1)和F(n-2)两个数相加求出结果,这样就避免了大量的重复计算,它的效率比递归算法快得多,算法的时间复杂度与n成正比,即算法的时间复杂度为O(n)

您可能感兴趣的

Pages are not found for an application Main url file: from django.conf.urls import patterns, include, url from django.contrib import adminurlpatterns = patterns('', url(r'^$', inclu...
ToolCover-自动为你的命令行程序加上UI github项目点 这里 。 欢迎fork/star/issue/PR。 以网页的形式,旨在用最简单的方式为所有命令行程序提供一个跨平台、美观的交互方案。 基于flask + bootstrap,python3。 目前只支持linux与mac系统。 灵感 ...
饿了吗上面原来有这么多无证店铺!还是大Python比较牛逼!... 先看一下抓取的截图,竟然有这么多店没有营业执照。 二、运行环境 python3 pymongo requests 三、分析 首先访问饿了么主页,输入想搜寻的区域,页面随即返回附近区域店铺。 ...
Introduction to fountain codes: LT Codes with Pyth... In 1998, Michael Luby published the Luby Transform Code (LT Code), an error correction algorithm belonging to the “ fountain ” code class, a type ...
未来五年最具前景的一门编程语言是什么?... 作者:stormzhang 之前我的知识星球内有人问过这么一个问题,当时做了一个回答,今天在知乎上也看到一个类似的问题,看到很多人的答案都模棱两可,给你说一大堆套话,新手如果可以理解的话就不是新手了,对于新手来说,最需要的是直接有效的答案,故怒答一记,也顺便...
0
Python_博客园

责编内容来自:Python_博客园 (本文源链)
阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。