Python 不自己試試，還真猜不出遞回函式的時間復雜度！

如題，以斐波那契數列為例，寫以下三種遞回演算法進行測驗：

>>> def F1(n):
	if n<3: return 1
	return F1(n-1)+F1(n-2)

>>> def F2(n,n2=1,n1=1):
	if n<3: return 1
	if n==3: return n2+n1
	return F2(n-1,n1+n2,n2)

>>> def F3(n:int)->int:
	if n<3: return 1
	t=n//2
	if n%2: return F3(t)**2+F3(t+1)**2
	return F3(t)*(F3(t+1)+F3(t-1))

>>> for i in range(1,16):i,F1(i),F2(i),F3(i),F1(i)==F2(i)==F3(i)

(1, 1, 1, 1, True)
(2, 1, 1, 1, True)
(3, 2, 2, 2, True)
(4, 3, 3, 3, True)
(5, 5, 5, 5, True)
(6, 8, 8, 8, True)
(7, 13, 13, 13, True)
(8, 21, 21, 21, True)
(9, 34, 34, 34, True)
(10, 55, 55, 55, True)
(11, 89, 89, 89, True)
(12, 144, 144, 144, True)
(13, 233, 233, 233, True)
(14, 377, 377, 377, True)
(15, 610, 610, 610, True)
>>> 

F1 函式測驗：

增加一個全域變數count用于計算呼叫次數，

>>> def F1(n):
	global count
	count += 1
	if n<3: return 1
	return F1(n-1)+F1(n-2)

>>> for i in range(1,16):
	count=0; F1(i),count

	
(1, 1)
(1, 1)
(2, 3)
(3, 5)
(5, 9)
(8, 15)
(13, 25)
(21, 41)
(34, 67)
(55, 109)
(89, 177)
(144, 287)
(233, 465)
(377, 753)
(610, 1219)
>>> 
>>> count=0; F1(20),count
(6765, 13529)
>>> count=0; F1(25),count
(75025, 150049)
>>> count=0; F1(30),count
(832040, 1664079)
>>> 6765*2,75025*2,832040*2
(13530, 150050, 1664080)
>>> 6765*2-1,75025*2-1,832040*2-1
(13529, 150049, 1664079)
>>> 

結果真的有點出乎意料，F(n)的運行次數是 2*F(n)-1，這么巨大的數字，怪不得此函式算 F(40) 時電腦基本上就動不了，要知道 2*F(40)-1 = 204668309，兩億次的呼叫計算量可想而知，不只是兩億次的整數運算，

所以這個函式的時間復雜度應在立方級O(n3)和指數級O(2?)之間吧：

F2 函式測驗：

>>> def F2(n,n2=1,n1=1):
	global count
	count += 1
	if n<3: return 1
	if n==3: return n2+n1
	return F2(n-1,n1+n2,n2)

>>> for i in range(1,16):
	count=0; F2(i),count

	
(1, 1)
(1, 1)
(2, 1)
(3, 2)
(5, 3)
(8, 4)
(13, 5)
(21, 6)
(34, 7)
(55, 8)
(89, 9)
(144, 10)
(233, 11)
(377, 12)
(610, 13)
>>> 
>>> count=0; F2(100),count
(354224848179261915075, 98)
>>> count=0; F2(1000),count
(4346655768693745643568852767504062580256466051737178040248172\
90895365554179490518904038798400792551692959225930803226347752\
09689623239873322471161642996440906533187938298969649928516003\
704476137795166849228875, 998)
>>> 

明顯，經過尾遞回優化后的時間復雜度為線性級O(n)，但是，它計算到 F(1027) 時就報錯“超出了最大遞回深度”，估計演算法的空間復雜度已大到“記憶體占用”已到了堆疊限制上限了，

F3 函式測驗：

>>> def F3(n:int)->int:
	global count
	count += 1
	if n<2: return n
	if n==2: return 1
	t=n//2
	if n%2: return F3(t)**2+F3(t+1)**2
	return F3(t)*(F3(t+1)+F3(t-1))

>>> count=0; F3(100),count
(354224848179261915075, 462)
>>> count=0; F3(101),count
(573147844013817084101, 344)
>>> count=0; F3(200),count
(280571172992510140037611932413038677189525, 1131)
>>> count=0; F3(201),count
(453973694165307953197296969697410619233826, 807)
>>> 

這個函式的時間復雜應該接近線性對數級 O(nlogn) 的，并且當n是奇數時比偶數時計算的快，

函式的時間測驗

>>> def Fib(n):
    if n<3: return 1
    if n%2: return Fib(n//2)**2+Fib(n//2+1)**2
    return Fib(n//2)*(Fib(n//2+1)+Fib(n//2-1))

>>> from time import time
>>> t=time();n=Fib(2000000);print(time()-t)
111.7971076965332

斐波那切數列遞回函式的終極改進

綜合以上幾個函式的經驗作以下改進，改進后計算第500萬項只需80秒，比不作改進的計算200萬項還要快半分鐘，

>>> 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)**2+Fib(t+1)**2
    return Fib(t)*(Fib(t+1)+Fib(t-1))

>>> from time import time
>>> t=time();n=Fib(1000000);print(time()-t)
7.492823362350464
>>> t=time();n=Fib(2000000);print(time()-t)
18.6656014919281
>>> t=time();n=Fib(3000000);print(time()-t)
35.3787145614624
>>> t=time();n=Fib(4000000);print(time()-t)
46.64482545852661
>>> t=time();n=Fib(5000000);print(time()-t)
80.72290563583374
>>> 

--All done!