<p>函数返回第X个斐波那契数,其中X=log(n)+3。因为获得第X个Fibonacci数有一个O(X)性能,我们提供log(n)。这将提供<em>O(log(n))</em>性能,与记忆版本类似,但使用更简单的操作。所以函数应该运行得更快:</p>
<pre><code>def fibo(n):
a,b=1,1
for _ in range(n-1): a,b = b,a+b
return a
from math import log
def rec2(n) :
return fibo(int(log(n,2)+3))
print(rec2(12345678987654321)) # 225851433717
</code></pre>
<p>对于n=12345678987654321,它的执行速度大约是原始rec()函数的记忆版本的5倍。你知道吗</p>
<p>您还可以通过在每次迭代中不进行两次递归调用来获得性能增益。这将需要返回两个值,以便n//4(下一次迭代)可以被带到调用函数。你知道吗</p>
<pre><code>def rec3(n):
if n<1 :return 1,1
a,b = rec3(n//2)
return a+b,a
rec3(12345678987654321)[0] # 225851433717
</code></pre>
<p>这比斐波那契方法慢,但仍然比记忆的原始方法快。你知道吗</p>
<p>1000次运行的测试结果(2.9 GHz Intel Core i9笔记本电脑):</p>
<pre><code>rec(12345678987654321) 0.027 sec (Memoized on lru_cache, cleared each run)
rec2(12345678987654321) 0.005 sec (Fibonacci)
0.002 sec (fastFibo, see EDIT below)
rec3(12345678987654321)[0] 0.013 sec (Single Recursion)
</code></pre>
<p><strong>编辑
如果要使Fibonacci方法更快(2x),可以使用此非迭代<code>fastFibo()</code>函数获取第n个Fibonacci数:</p>
<pre><code>from math import sqrt
sqrt5 = sqrt(5)
golden_ratio = (1 + sqrt5) / 2
def fastFibo(n):
approx = (golden_ratio**n - (1 - golden_ratio)**n) / sqrt5
return int(round(approx))
</code></pre>
<p>这将允许您将函数编写为纯数学公式,没有迭代/递归,性能为O(1):</p>
<pre><code>from math import log,sqrt
sqrt5 = sqrt(5)
golden_ratio = (1 + sqrt5) / 2
def rec4(n):
n = int(log(n,2)+3)
result = (golden_ratio**n - (1 - golden_ratio)**n) / sqrt5
return int(round(result))
</code></pre>
<p><em>注意<code>fastFibo()</code>是一个近似值(好到70),所以这个<code>rec4()</code>解在n=2^67(147573952589676412928)</em></p>