我几天前写的这篇文章,看起来效果不错,但速度很慢。费波纳契数列中的第一百万个数字用了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的初学者,所以我不会理解高级概念
您可以使用matrix exponention,它在
O(logn)
整数操作中完成,也可以使用closed form expression,这是以幂函数的速度完成的。(注意使用闭式表达式的numerical errors)。在我发现用卢卡斯的数字能让我更快地得到结果:
和矩阵指数一样,它有O(NlogN)复杂度,但它的常数成本较低,因此在“点”上胜过它:
^{pr2}$是的,速度是原来的两倍。在
我不能相信上面的实现,也不能把它与之比较的矩阵求幂算法;两者都列在literateprograms.org上。在
要计算第1000000个斐波纳契数,需要:
不到十分之一秒。在
严格来说,这不是一个答案,但新程序员的一个很常见的习惯是违反Separation of Concerns。在
最好是:
这使得fibonacci不会被用户界面代码弄得乱七八糟。在
相关问题 更多 >
编程相关推荐