5

一位朋友向我提出了一个挑战，要在 python 中构建一个高效的斐波那契函数。所以我开始测试不同的递归方式（我没有很高的数学技能来思考复杂的算法，请不要给我看一个有效的斐波那契函数，这不是问题）。

然后我尝试了两种不同的解决方案：

解决方案1：

def fibo(n):
    if n > 1:
        return fibo(n-1)+fibo(n-2)
    return 1

解决方案2：

def fibo(n):
    if n < 1:
        return 1
    return fibo(n-1)+fibo(n-2)

然后，我为每个运行了这个：

res = map(fibo, range(35))
print res

现在，我怀疑可能存在效率差异（我不能确切地说出为什么）。但我预计会有一个小的差异。结果完全让我震惊。差别很大。第一个耗时 7.5 秒，而第二个耗时 12.7 秒（几乎是两倍！）。

谁能向我解释为什么？那些本质不是一样的吗？

4

2 回答 2

13

(not n > 1)是(n <= 1)，重新运行第二个代码，<=你会看到你得到类似的时间：

In [1]: def fibo(n):
   ....:    if n <= 1:
   ....:        return 1
   ....:    return fibo(n-1)+fibo(n-2)
   ....: 

In [2]: %timeit map(fibo, range(10))
10000 loops, best of 3: 29.2 us per loop

In [3]: def fibo(n):
   ....:    if n > 1:
   ....:        return fibo(n-1)+fibo(n-2)
   ....:    return 1
   ....: 

In [4]: %timeit map(fibo, range(10))
10000 loops, best of 3: 29.9 us per loop

如果您想知道为什么这会产生如此巨大的差异，那么当您运行时，map(fibo, range(35))您会14930351调用fibo(1). 使用(n < 1), eachfibo(1)将进行两个函数调用（tofibo(0)和fibo(-1)）并对结果求和，相当多的操作！

于 2013-09-08T21:08:15.980 回答
8

那些本质不是一样的吗？

第二个函数是计算一个更高的斐波那契数，所以自然需要更长的时间：

>>> def fibo(n):
...     if n > 1:
...         return fibo(n-1)+fibo(n-2)
...     return 1
... 
>>> fibo(10)
89
>>> def fibo(n):
...     if n < 1:
...         return 1
...     return fibo(n-1)+fibo(n-2)
... 
>>> fibo(10)
144

您可能希望n <= 1在第二个片段中：

>>> def fibo(n):
...     if n <= 1:
...         return 1
...     return fibo(n-1)+fibo(n-2)
... 
>>> fibo(10)
89
于 2013-09-08T21:09:21.110 回答