Python教程

斐波那契数的好的递归算法和坏的递归算法【python】【代码】【图解】

本文主要是介绍斐波那契数的好的递归算法和坏的递归算法【python】【代码】【图解】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 先看一下坏的

def fbnc(n):
    if n<= 1:
        return n
    else:
        return fbnc(n-2)+fbnc(n-1)

print(fbnc(5))
print(fbnc(15))
print(fbnc(25))
print(fbnc(50))

那么时间复杂度不难看出是2的（n/2）次方

这就是指数级的，当n的数值大的时候就会很慢

比如上面的运行结果的fbnc(50)就等了很长时间（看看你的电脑是不是也温度上升了~~~~）

好的计算斐波那契数的递归算法

# def fbnc(n):
#     if n<= 1:
#         return n
#     else:
#         return fbnc(n-2)+fbnc(n-1)

def fbnc2(n):
    if(n<=1):
        return [1,0]
    else:
        [a,b] = fbnc2(n-1)
        return [a+b,a]

# print(fbnc(5))
# print(fbnc(15))
# print(fbnc(25))
print(fbnc2(50))
print(fbnc2(500))

 现在很快了吧

时间复杂度是O(n)

这篇关于斐波那契数的好的递归算法和坏的递归算法【python】【代码】【图解】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航