使用Python计算斐波那契数列

Question

使用Python计算斐波那契数列

pythonpython-2.7fibonacciseriesmemoization

3

在解决欧拉计划第25题时，我使用了多种技术来计算第n个斐波那契数。其中记忆化似乎是最快的方法，并且直觉上，我预期记忆化要比从下向上创建列表更快。

两个函数的代码如下：

def fib3(n): #FASTEST YET
    fibs= [0,1] #list from bottom up
    for i in range(2, n+1):
        fibs.append(fibs[-1]+fibs[-2])
    return fibs[n]

def fib4(n, computed= {0:0, 1:1}): #memoization
    if n not in computed:
        computed[n]= fib4(n-1, computed)+ fib4(n-2, computed)
    return computed[n]
print fib3(1000)
print fib4(1000)

fib3比fib4快约8倍。我无法弄清楚背后的原因。本质上，它们都会在计算时存储值，一个存储在列表中，另一个存储在字典中，以便稍后可以将它们作为“缓存”访问。为什么有如此大的差异呢？

- nerd2617

1

天啊...谁踩了这个问题？？？深呼吸，冷静一下！或者至少解释一下你的行为。 - Julien

3

fib4是递归的（调用自身）。递归很耗费资源。 - Klaus D.

1

最佳的记忆化使用出现在您多次重复函数调用的情况下。如果您反复调用fib3/fib4，您会发现fib4会更快。 - Asish M.

@Wolf 那个链接中的示例很少使用递归，因此递归对运行时间的影响很小。 - Klaus D.

@KlausD。是的，但只适用于一些参数 ;) - Wolf

显示剩余3条评论

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Julien · Answer 1

在sonyman101上开发：my_list[i]可以立即访问元素，而my_dict[key]需要计算哈希函数并检查冲突，然后才能查看桶中的内容。此外，您的记忆化设置了一些潜在的深度递归堆栈，这也有一些成本。

更快的方法（前提是您不需要重新计算多个值，我知道对于欧拉问题不是这种情况 :)）是仅跟踪最后2个术语。因此，您不会浪费任何列表管理成本。

- Santanu Dey · Answer 2

你在fib4函数中使用了递归，这会导致时间复杂度呈指数级增长。

在有人说记忆化可以使fib4变成线性之后进行编辑：

但实际上并不是这样的。

记忆化只能减少重复调用时的计算时间。对于第一次计算一个数字n的斐波那契值，仍然需要使用递归。

你可以自己试一下。

import timeit

setup ='''
def fib3(n): #FASTEST YET
    fibs= [0,1] #list from bottom up
    for i in range(2, n+1):
        fibs.append(fibs[-1]+fibs[-2])
    return fibs[n]

def fib4(n, computed= {0:0, 1:1}): #memoization
    if n not in computed:
        computed[n]= fib4(n-1, computed)+ fib4(n-2, computed)
    return computed[n]

'''

print (min(timeit.Timer('fib3(600)', setup=setup).repeat(3, 1)))

print (min(timeit.Timer('fib4(600)', setup=setup).repeat(3, 1)))

这将显示fib4需要更长时间。

0.00010111480978441638
0.00039419570581368307
[Finished in 0.1s]

如果您更改最后两行，即将每个重复100次，则结果会发生变化。现在，fib4变得更快，好像不仅没有递归，而且几乎没有额外的计算时间。

print (min(timeit.Timer('fib3(600)', setup=setup).repeat(3, 100)))

print (min(timeit.Timer('fib4(600)', setup=setup).repeat(3, 100)))

50次重复的结果

0.00501430622506104
0.00045805769094068097
[Finished in 0.1s]

100次重复的结果

0.01583016969421893
0.0006815746388851851
[Finished in 0.2s]

- Mridul Kashyap · Answer 3

看一下这个stackoverflow问题。

正如你所看到的，斐波那契算法（使用递归）的复杂度大约为O(2^n)。

而对于fib3，它将是O(n)。

现在你可以计算，如果你的输入大小为3，fib3的复杂度将为O(3)，但fib4的复杂度将为O(8)。

你可以看到，这就是为什么它更慢。