擅长:python、mysql、java
<p>我发现用卢卡斯的数字能让我更快地得到结果:</p>
<pre><code>def powLF(n):
if n == 1: return (1, 1)
L, F = powLF(n//2)
L, F = (L**2 + 5*F**2) >> 1, L*F
if n & 1:
return ((L + 5*F)>>1, (L + F) >>1)
else:
return (L, F)
def fib(n):
if n & 1:
return powLF(n)[1]
else:
L, F = powLF(n // 2)
return L * F
</code></pre>
<p>和矩阵指数一样,它有O(NlogN)复杂度,但它的常数成本较低,因此在“点”上胜过它:</p>
^{pr2}$
<p>是的,速度是原来的两倍。在</p>
<p>我不能相信上面的实现,也不能把它与之比较的矩阵求幂算法;两者都列在<a href="http://en.literateprograms.org/Fibonacci_numbers_%28Python%29" rel="nofollow">literateprograms.org</a>上。在</p>
<p>要计算第1000000个斐波纳契数,需要:</p>
<pre><code>>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.09112384080886841
</code></pre>
<p>不到十分之一秒。在</p>