这些(几乎相同)条件之间的效率差异是什么

Question

我被朋友挑战,在python中构建一个高效的Fibonacci函数.所以我开始测试不同的递归方式(我没有很高的数学技能来考虑一个复杂的算法,请不要告诉我一个有效的Fibonacci函数,这不是问题).

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

解决方案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(几乎是两次!).

任何人都可以向我解释原因吗？那些基本上不一样吗？

Answer 1

(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),每个fibo(1)都会调用两个函数(to fibo(0)和fibo(-1))并对结果求和,相当多的操作!

Answer 2

那些基本上不一样吗？

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

>>> 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