python Fibonacci计算时间差

Question

我写了以下两个代码来计算Fibonacci序列的一个元素。在

def fib(n):
    zero, one = 0, 1
    k = 1
    while k < n:
        zero, one = one, zero + one
        k = k + 1
    return one, ls

def fib2(n, memo=None):
    if memo is None:
        memo = {}
    if n == 1 or n == 2:
        return 1
    if n in memo:
        return memo[n]
    else:
        memo[n-1] = fib2(n-1, memo)
        memo[n-2] = fib2(n-2, memo)
        return memo[n-1] + memo[n-2]


##import timeit
##
##print('Fibonacci 1:', timeit.timeit('fib(10000)', '''def fib(n):
##    zero, one = 0, 1
##    k = 1
##    while k < n:
##        zero, one = one, zero + one
##        k = k + 1
##    return one''', number=100))
##
##print('Fibonacci 2:', timeit.timeit('fib2(10000)', '''import sys; sys.setrecursionlimit(10001);
##def fib2(n, memo=None):
##    if memo is None:
##        memo = {}
##    if n == 0 or n == 1:
##        return 1
##    if n in memo:
##        return memo[n]
##    else:
##        memo[n-1] = fib2(n-1, memo)
##        memo[n-2] = fib2(n-2, memo)
##        return memo[n-1] + memo[n-2]''', number=100))

我在fib中使用一个简单的while循环，fib2是相同循环的递归实现。但事实证明fib2速度非常慢。我想知道为什么。是因为fib2创建了大量的帧吗？我是否正确地实现了fib2？在

谢谢。在

Answer 1

将此简化递归版本与原始迭代解决方案进行比较，首先将递归限制提高约1%到10%：

def fib2(n, memo={0: None, 1: 1, 2: 1}):
    if n in memo:
        return memo[n]

    previous = fib2(n - 1)  # implicitly computes fib2(n - 2)

    result = memo[n] = previous + memo[n - 2]

    return result

我没有将memo作为递归的参数传递，因为我利用了当默认参数设置为可以修改的结构时的“问题”。在

上面的解决方案比我机器上最初的迭代解决方案慢4.5倍。在第一次调用之后，记忆化就占了上风。我们可以在空间和时间上对此做一点改进，方法是将“内存”从字典更改为列表，因为所有键都是顺序整数：

^{pr2}$

在我的机器上，第一次调用的速度比迭代解决方案慢3倍。但是，我们可以使用递归实现更好的速度：

def fib4(n, res=0, nxt=1):
    if n == 0:
        return res
    return fib4(n - 1, nxt, res + nxt)

这只比迭代解慢2倍，而且/但没有记忆。在带有尾部调用优化的语言中（即不是Python），这很可能成为/tie迭代。在