Fibonacci数列高效解法大全及时间复杂度分析 连载【6】
在数学上，斐波那契数列是以递归的方法来定义
……续上回Fibonacci数列高效解法大全及时间复杂度分析 连载【5】
在GMP库里就有斐波那契数和数列的单独函数
11. GMP内置fib函数解法
这直接引用就可以了
import gmpy2
def Fibonacci_sequence_09 (n: int) -> int: #参数n是表示求第n项Fibonacci数
'返回单项的GMP内置fib函数解法'
assert isinstance(n, int), 'n is an error of non-integer type.'
if n>=0:
return gmpy2.fib(n)
else:
return None
Fibonacci_sequence_09(1000000)
看一下耗时多少，同上例
Total time: 0.004522秒
算第100万项Fibonacci数用时只有二分递归解法的65.6%。果然更快速一些
GMP和Mathematica内置算Fibonacci数的函数都是用的同一种快速算法
是一种叫二进制模幂算法，让我们来看看是什么样
https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm
引自GMP官网上的资料，用的是这个递推式
把n分解为n的二进制表示形式，然后直接迭代递推。递推迭代是O(log n)，大整数乘方是O(n*log n))，那么整个算法时间复杂度也是O(n*(log n)^2)的
那为什么表现的比同样O(n*(log n)^2)的二分迭代解法更快呢
可以看这篇《为什么算法渐进复杂度中对数的底数总为2》解释
12. 二进制模幂解法
好，不用GMP那C写Fibonacci数库函数，用Python实现一遍这个二进制模幂解法（当然大数运算还是用到GMP）
我来写出来
import gmpy2
def Fibonacci_sequence_10 (n: int) -> int: #参数n是表示求第n项Fibonacci数
assert isinstance(n, int), 'n is an error of non-integer type.'
def Calculate_Fibonacci_sequence (n: int) -> int:
'返回单项的二进制模幂解法'
if n >= 1 :
add_on = (2, -2) #就是 2*(-1)^k 这项
prev_num, current_num = gmpy2.mpz(1), gmpy2.mpz(1) #设prev_num为F[1]，current_num为F[2]
for i in range(gmpy2.bit_length(n) - 1, 0, -1): #从最高位开始遍历除末位外的每个二进制位
if gmpy2.bit_test(n, i): #注意bit_test的i参数0就是第一位（二进制表示的最末尾一位）
prev_num = current_num - prev_num #prev_num = F[2k] = F[2k+1] - F[2k-1]，current_num就是等于F[2k+1]
else:
current_num = current_num - prev_num #prev_num就是等于F[2k-1]，current_num = F[2k] = F[2k+1] - F[2k-1]
sq_prev_num = prev_num ** 2; sq_current_num = current_num ** 2
prev_num = sq_prev_num + sq_current_num #F[2k-1] = F[k]^2 + F[k-1]^2
current_num = sq_current_num * 4 - sq_prev_num + add_on[1 if gmpy2.bit_test(n, i) else 0] #F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
if n & 1 == 0: #迭代完成，再对末位做个判断
current_num = current_num - prev_num
return current_num
elif n == 0:
return 0
if n >=0:
return Calculate_Fibonacci_sequence(n)
else:
return None
Fibonacci_sequence_10(1000000)
看耗时多少，同上例
Total time: 0.005285秒
只比纯C库实现的慢了不到1ms，Python还是不错的
未完待续……
