Fibonacci的递归实现和循环实现 （Python语言、牛客网剑指Offer）

题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

递归调用的指数级复杂度

递归调用实现Fibonacci数列采用的自顶向下的算法模式，利用
f(n) = f(n-1) + f(n-2),每次递归调用上一次的两个Fibonacci()函数。递归算法对前n-2次所得数列中的数据不具有记忆性，故而导致其指数级算法复杂度。

代码如下

class Solution:
    def Fibonacci(self, n):
        
        # 如果是按照递归来写的话， 时间复杂度就是随着n的变化 增长率是 2^n
        
        #递归实现
        # n = 0 f(0) = 0
        if n == 0:
            return 0
        # n = 1 f(1) = 1
        if n == 1:
            return 1
        # if n > 1  f(n) = f(n-1) + f(n-2)
        if n > 1:
            num = self.Fibonacci(n-1) + self.Fibonacci(n-2)
            return num

        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

循环调用的常数级复杂度

循环调用使用的是自下而上的编程思想，定义每一次参与加法运算的Fibonacci数列中的两项，记录较大的一项和此次加法运算的和，作为求Fibonacci数列中下一项的两个加法项，避免了递归调用时的多次重复运算，极大提高了算法的运行效率。

简单描述算法思想

1.有a和b两个初始数据，假设a始终是较大的一个数，b始终是较小的一个数。
2.若第n-1项的数值为a，n-2项的数值为b，根据Fibonacci数列中各项的性质，第n项的数值ret=a + b。
3.递归调用时，每次计算第n项的值时，重新计算a和b的数值，而循环方法规定每次运算时较大的数作为a，方便计算下一项时直接获取加法的其中的一项数据。即通过a、b和ret三者计算所需第n项的数据。
1
2
3

算法流程

代码如下

class Solution:
    def Fibonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        a = 1
        b = 0
        for i in range(0,n-1):
            ret = a+b 
            b = a 
            a = ret
        return ret
        #在线测试代码，在IDE中运行时需要加输入输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注

相关材料源于网上视频