这个Python代码对于fibonacci序列的效率如何?

2024-03-28 18:19:24 发布

您现在位置:Python中文网/ 问答频道 /正文

我几天前写的这篇文章,看起来效果不错,但速度很慢。费波纳契数列中的第一百万个数字用了25秒。有没有办法让这更有效?在

def main():
    num1 = 0
    num2 = 1
    var = 0
    num = int(raw_input("What fibonacci number do you want to know? "))
    while 1:
        num3 = num1
        num1 = num1 + num2
        num2 = num3
        var+=1
        if var>=num:
            print num3
            return main()
        else:
            None

main()

请注意,我是python的初学者,所以我不会理解高级概念


Tags: inputrawmainvardef数字num速度
3条回答

您可以使用matrix exponention,它在O(logn)整数操作中完成,也可以使用closed form expression,这是以幂函数的速度完成的。(注意使用闭式表达式的numerical errors)。在

我发现用卢卡斯的数字能让我更快地得到结果:

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

和矩阵指数一样,它有O(NlogN)复杂度,但它的常数成本较低,因此在“点”上胜过它:

^{pr2}$

是的,速度是原来的两倍。在

我不能相信上面的实现,也不能把它与之比较的矩阵求幂算法;两者都列在literateprograms.org上。在

要计算第1000000个斐波纳契数,需要:

>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.09112384080886841

不到十分之一秒。在

严格来说,这不是一个答案,但新程序员的一个很常见的习惯是违反Separation of Concerns。在

最好是:

def fibonacci(n):
    ...

def main():
    num = int(raw_input("What fibonacci number do you want to know? "))
    print fibonacci(num)

这使得fibonacci不会被用户界面代码弄得乱七八糟。在

相关问题 更多 >