改进思路
上一篇《不自己试试，还真猜不出递归函数的时间复杂度》中写了一个递归函数求斐波那契数列的某一项的值，号称它是终极改进了，但它有一个缺点：偶数项比奇数项算得慢。今天实然想到应该把偶数项也转换成奇数项来算，就会成倍提高运算速度：
原理是这样的：
F(2n)=F(n)*(F(n+1)+F(n-1)) ; F(2n+1)=F²(n+1)+F²(n)
偶数项需要三个项递归计算，奇数项只有两个项要递归。但是想到另外有公式可以把偶数项转换成奇数项：
∵ F(2n)=F(2n+1)-F(2n-1)
∴ F(2n)=F²(n+1)+F²(n) - (F²(n)+F²(n-1))=F²(n+1)-F²(n-1)
之前版本的时间测试，奇数项比偶数项计算快：
>>> def Fib(n:int,n1=34,n2=55): if n<11: return [0,1,1,2,3,5,8,13,21,34,55][n] if n==11: return n1+n2 if n<1001:return Fib(n-1,n2,n1+n2) t=n//2 if n%2: return Fib(t+1)**2+Fib(t)**2 return Fib(t)*(Fib(t+1)+Fib(t-1)) >>> for i in range(1,6): t=time();n=Fib(i*1000000);print(time()-t) t=time();n=Fib(i*1000000+1);print(time()-t) 7.499995231628418 5.33894419670105 19.355664014816284 15.778117656707764 37.201030254364014 25.430164575576782 >>> t=time();n=Fib(5000000);print(time()-t) 77.2153069972992 >>> t=time();n=Fib(5000000+1);print(time()-t) 53.111284017562866 >>>
改进一：偶数项改奇数项
>>> def Fib(n:int,n1=34,n2=55): if n<11: return [0,1,1,2,3,5,8,13,21,34,55][n] if n==11: return n1+n2 if n<1001: return Fib(n-1,n2,n1+n2) t=n//2 if n%2: return Fib(t+1)**2+Fib(t)**2 return Fib(t+1)**2-Fib(t-1)**2 >>> from time import time >>> for i in range(1,7): t=time();n=Fib(i*1000000);print(f'Fib({i*1000000})::{time()-t}') t=time();n=Fib(i*1000000+1);print(f'Fib({i*1000000+1})::{time()-t}') Fib(1000000)::1.2499959468841553 Fib(1000001)::1.2343709468841553 Fib(2000000)::3.0624945163726807 Fib(2000001)::3.062493324279785 Fib(3000000)::5.203120470046997 Fib(3000001)::5.218744993209839 Fib(4000000)::7.812499523162842 Fib(4000001)::7.8281190395355225 Fib(5000000)::10.343748092651367 Fib(5000001)::10.343748331069946 Fib(6000000)::13.65624475479126 Fib(6000001)::13.671867370605469
用了新版公式后，不管奇数还是偶数项，耗时不再是起伏的而是单调递增且相邻的项用时基本相等，而且函数的运算速度也都成倍提高了。计算第500万项时，从原来的80秒减少到10秒了；计算第2000万项也只要80秒，而第1000万项只要半分钟就够了！
>>> from time import time >>> t=time();n=Fib(10000000);print(time()-t) 27.9345383644104 >>> t=time();n=Fib(10000000+1);print(time()-t) 28.794012784957886 >>> t=time();n=Fib(20000000);print(time()-t) 77.22278428077698 >>>
改进二：前面的项改用循环获取
把前面的项(比如前600项，具体定哪个值最优没有细测)用循环来获取，提速效果明显。
>>> def fib(n): if n<600: n1 = n2 = 1 for _ in range(2,n): n1,n2 = n1+n2,n1 return n1 t = n//2 if n%2: return fib(t+1)**2 + fib(t)**2 else: return fib(t+1)**2 - fib(t-1)**2 >>> t=time();n=fib(10000000);print(time()-t) 3.8922224044799805 >>> t=time();n=fib(10000001);print(time()-t) 3.8972229957580566 >>> t=time();n=fib(20000000);print(time()-t) 11.089634418487549 >>> t=time();n=fib(50000000);print(time()-t) 45.387596130371094 >>>
计算第5000万项：45秒；第2000万项：11秒；第1000万项：4秒钟！
--All done!
附录
斐波那契数列重要恒等式
数列通项公式：
F(1)=F(2)=1;
F(n)=F(n-1)+F(n-2), n>2.
通项公式的前一项是：
F(n-1)=F(n-2)+F(n-3)
前一项代入通项中，得：
F(n)=2*F(n-2)+F(n-3)
再把更前一项F(n-2)=F(n-3)+F(n-4)代入上式，得：
F(n)=3*F(n-3)+2*F(n-4)
...以此类推：
F(n)=5*F(n-4)+3*F(n-5)
F(n)=8*F(n-5)+5*F(n-6)
F(n)=13*F(n-6)+8*F(n-7)
......
等号右边的系数又分别都是斐波那契数列，
两个新数列的函数自变量刚好差1，
且F(7)=13,F(6)=8，F(5)=5...可得：
F(n)=F(m)F(n-m+1)+F(m-1)F(n-m) --公式①
先用m+n替换公式①中的n,得:
F(m+n)=F(m)*F(n+1)+F(m-1)*F(n) --公式②
令m=n,代入公式②,得:
F(2n)=F(n)*F(n+1)+F(n-1)*F(n) --公式③
再令m=n+1,代入公式②,得:
F(2n+1)=F(n+1)*F(n+1)+F(n)*F(n)
表示成平方和形式：
F(2n+1)=F²(n+1)+F²(n) --公式④
公式④自变量减一，得：
F(2n-1)=F²(n)+F²(n-1) --公式④'
公式④自变量增一，得：
F(2n+3)=F²(n+2)+F²(n+1)
上式与公式④相减：
F²(n+2)-F²(n)=F(2n+3)-F(2n+1)
而 F(2n+3)=F(2n+2)+F(2n+1)，所以：
F(2n+2)=F²(n+2)-F²(n) --公式⑤
还有一个公式：
F(n+1)*F(n-1)-F²(n)=(-1)ⁿ --公式⑥
