斐波那契数列两种时间复杂度

契数列

概述:

  斐波那契数列,又称黄金分割数列,指的是这样一个数列: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 递归算法


1

2

3

4

5

6

7

8

9

10

11

12

#!/usr/bin/env python

# -*- coding:utf-8 -*-

def fibonacci(n):

    if == 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 非递归算法


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#!/usr/bin/env python

# -*- coding:utf-8 -*-

def fibonacci(n):

    if == 0:

        return 0

    elif n <= 2:

        return 1

    else:

        num1 = 1

        num2 = 1

        for 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)

原文地址:https://www.cnblogs.com/chengjian-physique/p/8563014.html

时间: 03-13

斐波那契数列两种时间复杂度的相关文章

斐波那契的两种实现方式

斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1960年代起出版了<斐波纳契数列>季刊,专门刊载这方面的研究成果. #include<stdio.h> /* 解决斐波那契数列问题: 斐波那契数列指的是这样一个数列 0, 1,

斐波拉契数列加强版——时间复杂度O(1),空间复杂度O(1)

对于斐波拉契经典问题,我们都非常熟悉,通过递推公式F(n) = F(n - 1) + F(n - 2),我们可以在线性时间内求出第n项F(n),现在考虑斐波拉契的加强版,我们要求的项数n的范围为int范围内的非负整数,请设计一个高效算法,计算第n项F(n).第一个斐波拉契数为F(0) = 1. 给定一个非负整数,请返回斐波拉契数列的第n项,为了防止溢出,请将结果Mod 1000000007. 斐波拉契数列的计算是一个非常经典的问题,对于小规模的n,很容易用递归的方式来获取,对于稍微大一点的n,为

实现斐波那契数列的三种方式

首先说说斐波那契数列:从文字上说,费波那西数列由0和1开始,之后的斐波那契系数就由之前的两数相加,数列形式如下:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,………………在数学上,是以递归的方法来定义:F(0)=0F(1)=1F(n)= F(n-1)+ F(n-2) 实现需求:输入序号n返回得到对应斐波那契数程序实现1——函数迭代 public int fnType1(int n)thro

【Java】斐波那契数列(Fibonacci Sequence、兔子数列)的3种计算方法(递归实现、递归值缓存实现、循环实现)

斐波那契数列:0.1.1.2.3.5.8.13………… 他的规律是,第一项是0,第二项是1,第三项开始(含第三项)等于前两项之和. > 递归实现 看到这个规则,第一个想起当然是递归算法去实现了,于是写了以下一段: public class RecursionForFibonacciSequence { public static void main(String[] args) { System.out.println(recursion(10)); } public static double

c语言:写一个函数,输入n,求斐波拉契数列的第n项(5种方法,层层优化)

写一个函数,输入n,求斐波拉契数列的第n项. 斐波拉契数列:1,1,2,3,5,8...,当n大于等于3时,后一项为前面两项之和. 解:方法1:从斐波拉契数列的函数定义角度编程 #include<stdio.h> int fibonacci(int n) { int num1=1, num2=1, num3=0,i; if (n <= 2) { printf("斐波拉契数列的第%d项为:%d\n",n,num1); } else { for (i = 2; i <

求斐波那契数列的相邻两项的比值,精确到小数后三位。

未完成,只能假设知道是9和10代入. 代码如下: package zuoye; import java.math.BigDecimal; /* * 求斐波那契数列的相邻两项的比值,精确到小数后三位. * p1,p2,p3......pi,pj,...求pi/pj * 1 1 2 3 5 8 13 * 5/8,8/13,...收敛 */ public class Test { static double feibo(int x){ if(x==1||x==2) return 1; return f

c语言:编辑程序实现斐波拉契数列:1,1,2,3,5,8...;后一项为前面两项之和

程序: //斐波拉契数列:1,1,2,3,5,8... //f(n)={[(1+5^0.5)/2]^n - [(1-5^0.5)/2]^n}/(5^0.5) #include<stdio.h> int main() { int i=0, n = 0; int num1 = 1; int num2 = 1; int num3 = 0; scanf("%d", &n); if (n <= 2) { printf("%d\n", num1); }

斐波纳契数列

查找斐波纳契数列中第 N 个数. 所谓的斐波纳契数列是指: 前2个数是 0 和 1 . 第 i 个数是第 i-1 个数和第i-2 个数的和. 斐波纳契数列的前10个数字是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 样例 给定 1,返回 0 给定 2,返回 1 给定 10,返回 34 虽然这道题是一道入门级的题目,可是在第一遍做的时候并没有多想,直接使用的递归,然后数据通过95%,显示的到47的时候就溢出了.经过学习前辈的经验,该题的收获如下: 方法1:使用递归解,

【剑指offer】斐波那契数列

题目1描述: 写一个函数,输入n,求斐波那契数列的第n项.斐波那契数列的定义如下: f(n) = 0 (n = 0);  f(n) = 1 (n = 1);  f(n) = f(n-1)+f(n-2) (n > 1); 分析描述: 在大多数的C语言教科书中,一般会用递归求斐波那契数列.代码如下: long long Fibonacci(unsigned int n) { if(n <= 0) return 0; if(n <= 1) return 1; return Fibonacci(

斐波那契数列和反向计算问题

反向计算:编写一个函数将一个整型转换为二进制形式 反向计算问题,递归比循环更简单 分析:需要理解,奇数的二进制最后一位是1,偶数的二进制最后一位一定是0,联想记忆,这个和整型的奇偶性是一致的,1本身就是奇数,0本身是偶数. 十进制整数转换为二进制整数采用"除2取余,逆序排列"法. 具体做法是:用2整除十进制整数,可以得到一个商和余数,再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列