斐波那契数快速算法

定义

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