斐波那契數快速算法

定義

f i b ( n ) = { 0 i f    n = 0 1 i f    n = 1 f i b ( n − 2 ) + f i b ( n − 1 ) o t h e r w i s e fib(n)=\left\{\begin{matrix} 0&if\;n=0 \\1&if \;n=1 \\fib(n-2)+fib(n-1)&otherwise \end{matrix}\right. fib(n)=⎩⎨⎧​01fib(n−2)+fib(n−1)​ifn=0ifn=1otherwise​

一般計算方法

直接用遞歸實作

def fib(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fib(n-2) + fib(n-1)
           

時間複雜度為 O ( φ n ) O(\varphi^n) O(φn)，空間複雜度為 O ( n ) O(n) O(n)，其中 φ \varphi φ為黃金分割率。

使用疊代實作

（1）

def fib(n):
	a, b = 0, 1
	for i in range(n):
		a, b = b, a + b
	return a
           

（2）

def fib(n):
	a, b = 0, 1
	while n:
		a, b = b, a + b
		n -= 1
	return a
           

時間複雜度為 O ( n ) O(n) O(n)，空間複雜度為 O ( n ) O(n) O(n)。

高效算法

考慮上面的疊代計算過程，疊代計算的核心思想是狀态變換。

初始狀态

a = 0 a=0 a=0

b = 1 b=1 b=1

狀态更新

a ← b a\leftarrow b a←b

b ← a + b b\leftarrow a+b b←a+b

狀态更新 n n n次即可得到 f i b ( n ) fib(n) fib(n)和 f i b ( n + 1 ) fib(n+1) fib(n+1)。

這種狀态更新形式事實上是線性變換，是以可用矩陣乘法表示。

( b a ) ← [ 1 1 1 0 ] ( b a ) \begin{pmatrix} b\\a \end{pmatrix} \leftarrow \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{pmatrix} b\\a \end{pmatrix} (ba​)←[11​10​](ba​)

其中

T = [ 1 1 1 0 ] T=\begin{bmatrix}1&1\\1&0\end{bmatrix} T=[11​10​]

為線性變換矩陣。

令

s n = ( f i b ( n + 1 ) f i b ( n ) ) s_n=\begin{pmatrix}fib(n+1)\\fib(n)\end{pmatrix} sn​=(fib(n+1)fib(n)​)

則

s 0 = ( 1 0 ) s_0=\begin{pmatrix}1\\0\end{pmatrix} s0​=(10​)

s n = T n s 0 s_n=T^ns_0 sn​=Tns0​

可根據此事實設計高效算法

s n = T n s 0 = { ( T 2 ) n 2 s 0 i f    n   i s   e v e n T n − 1 ( T s 0 ) i f    n   i s   o d d s_n=T^ns_0=\left\{\begin{matrix} (T^2)^{\frac{n}{2}}s_0&if\;n\,is\,even \\T^{n-1}(Ts_0)&if\;n\,is\,odd \end{matrix}\right. sn​=Tns0​={(T2)2n​s0​Tn−1(Ts0​)​ifnisevenifnisodd​

def fib(n)
	s0, s1 = 0, 1				#fib(0),fib(1)
	a, b, c, d = 1, 1, 1, 0		#變換矩陣
	while n:
		if n % 2 == 0:
			#n為偶數時，T<----T^2
			a, b, c, d = a**2 + b*c, b*(a + d), c*(a + d), b*c + d**2 
			n \= 2
		else:
			s0, s1 = c*s1 + d*s2, a*s1 + b*s2
			n -= 1
	return s0			
           

該算法的時間複雜度為 O ( l o g n ) O(logn) O(logn)，空間複雜度為 O ( 1 ) O(1) O(1)。

這裡共使用了7個狀态變量：n, s0, s1, a, b, c, d。考慮到變換矩陣 T T T為實對稱矩陣，有b=c，是以可以減少一個狀态變量。

def fib(n)
	s0, s1 = 0, 1				#fib(0),fib(1)
	a, b, c = 1, 1, 0		#變換矩陣
	while n:
		if n % 2 == 0:
			#n為偶數時，T<----T^2
			a, b, c = a**2 + b**2, b*(a + c), b**2 + c**2 
			n \= 2
		else:
			s0, s1 = b*s1 + c*s2, a*s1 + b*s2
			n -= 1
	return s0			
           

再考慮到， c = a − b c=a-b c=a−b，變換矩陣隻用兩個變量a,b表示即可。

def fib(n)
	s0, s1 = 0, 1				#fib(0),fib(1)
	a, b = 1, 1		#變換矩陣
	while n:
		if n % 2 == 0:
			#n為偶數時，T<----T^2
			a, b= a**2 + b**2, b*(a + (a - b))
			n \= 2
		else:
			s0, s1 = b*s1 + (a-b)*s2, a*s1 + b*s2
			n -= 1
	return s0