……續(xù)上回Fibonacci數(shù)列高效解法大全及時間復(fù)雜度分析 連載【7】
之前的篇章把各種Fibonacci數(shù)列的基本算法討論過了
那么是否可以做到更快呢热幔，有什么加速手段
這篇來說下
首先第一個手段是改進算法的加速
16.? 快速平方的矩陣解法
在Fibonacci數(shù)列高效解法大全及時間復(fù)雜度分析 連載【5】這篇里說過矩陣解法
矩陣法雖然跟二進制模冪解法時間復(fù)雜度一樣闸迷，可算第100萬項斐波那契數(shù)用時是二進制模冪解法的10倍宣渗。這是因為這算法的時間常數(shù)項大
里面用到了矩陣乘法班巩，通用矩陣乘法算法的時間復(fù)雜度是階數(shù)n的O(n^3)蔓罚。也就是對一個二階矩陣竿奏，分解步驟中有8次乘法训裆，非常耗時眶根，造成矩陣解法時間常數(shù)項很大
之前程序是直接用的numpy庫做矩陣乘法，numpy庫里就是通用矩陣乘法算法
然而缭保，對斐波那契數(shù)的矩陣解法汛闸，只需對二階矩陣做運算。而其中的二階矩陣平方步驟是有更小時間復(fù)雜度算法的
二階矩陣快速平方算法的時間復(fù)雜度為階數(shù)2的O(2^(log2(5)))
也就是二階矩陣一次平方運算分解步驟中只用做5次乘法艺骂。比通用矩陣算法的8次降低了不少
但是诸老，對斐波那契數(shù)矩陣解法而言，矩陣乘法步驟是其中的時間常數(shù)項钳恕，縮短矩陣乘法用時只是降低整個算法的常數(shù)項别伏，可并不降低整個算法的時間復(fù)雜度
下面就是我寫的程序
import numpy
import gmpy2
def fast_power_of_second_order_matrix(input_matrix: 'matrix', exponential: int) -> 'matrix':
? ? assert isinstance(exponential, int), 'Exponential is an error of non-integer type.'
? ? assert exponential >= 0, 'The exponent cannot be negative.'
? ? assert input_matrix.shape == (2, 2), 'It can only be a second-order matrix'
? ? if numpy.min_scalar_type(input_matrix) in (numpy.dtype(bool), numpy.dtype(int), numpy.dtype(float), numpy.dtype(complex)):
? ? ? ? output_matrix = numpy.asmatrix(numpy.identity(2, dtype = numpy.min_scalar_type(input_matrix)))? #根據(jù)輸入矩陣的標量類型，把output_matrix初始化為相同類型的單位矩陣
? ? elif numpy.issubsctype(input_matrix, numpy.dtype(object)):
? ? ? ? for matrix_element in input_matrix.flat:
? ? ? ? ? ? if type(matrix_element) not in (type(gmpy2.mpz()), type(gmpy2.xmpz()), type(gmpy2.mpq()), type(gmpy2.mpfr()), type(gmpy2.mpc()), int, float):
? ? ? ? ? ? ? ? raise TypeError('The matrix can only be of Boolean or numeric type.')
? ? ? ? output_matrix = numpy.mat(((gmpy2.mpz(1), gmpy2.mpz(0)), (gmpy2.mpz(0), gmpy2.mpz(1))))? #初始化值為mpz類型的單位矩陣
? ? else:
? ? ? ? raise TypeError('The matrix can only be of Boolean or numeric type.')
? ? def square_of_second_order_matrix(input_second_order_matrix: 'matrix') -> 'matrix':
? ? ? ? output_second_order_matrix = numpy.copy(input_second_order_matrix)
? ? ? ? sum_of_main_diagonal = output_second_order_matrix[0, 0] + output_second_order_matrix[1, 1]
? ? ? ? product_of_antidiagonal = output_second_order_matrix[0, 1] * output_second_order_matrix[1, 0]
??????? output_second_order_matrix[0, 0] **= 2
? ? ? ? output_second_order_matrix[0, 0] += product_of_antidiagonal
? ? ? ? output_second_order_matrix[0, 1] *= sum_of_main_diagonal
? ? ? ? output_second_order_matrix[1, 0] *= sum_of_main_diagonal
? ? ? ? output_second_order_matrix[1, 1] **= 2
? ? ? ? output_second_order_matrix[1, 1] += product_of_antidiagonal
? ? ? ? return output_second_order_matrix
? ? intermediate_variable = numpy.copy(input_matrix)
? ? while True:
? ? ? ? if exponential & 1 == 1:
? ? ? ? ? ? output_matrix *= intermediate_variable
? ? ? ? ? ? if exponential == 1: break
? ? ? ? intermediate_variable = square_of_second_order_matrix(intermediate_variable)
? ? ? ? exponential >>= 1
? ? return output_matrix
import numpy.matlib
from gmpy2 import mpz
def Fibonacci_sequence_06 (n: int) -> int:? #參數(shù)n是表示求第n項Fibonacci數(shù)
? ? '返回單項的二階矩陣快速平方解法'
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? Use_threshold_of_fast_power = 100000
? ? if n >= 2:
? ? ? ? fib_matrix = numpy.mat(((mpz(1), mpz(1)), (mpz(1), mpz(0))))
? ? ? ? if n > Use_threshold_of_fast_power:
? ? ? ? ? ? fib_matrix = fast_power_of_second_order_matrix(fib_matrix, n - 1)
? ? ? ? else:
? ? ? ? ? ? fib_matrix **= n - 1
? ? ? ? return fib_matrix[0,0]
? ? elif n == 1:
? ? ? ? return 1
? ? elif n == 0:
? ? ? ? return 0
? ? else:
? ? ? ? return None
Fibonacci_sequence_06(1000000)
用算到第100萬項Fibonacci數(shù)來測量下用時
Total time: 0.036093秒
比之前用通用矩陣乘法庫的程序縮短了15%的時間
注意忧额，那么一大段程序是有基礎(chǔ)開銷的
所以在非大數(shù)的時候用這個反而會不如通用庫快
怎么辦呢
加一個閾值判別厘肮。當N大于閾值之后，才用這個二階矩陣快速平法算法睦番，數(shù)不大時就調(diào)用通用庫
搞定
------------------------
算Fibonacci數(shù)的快速算法已經(jīng)寫了4種类茂，算法時間復(fù)雜度皆為O(log n)，但常數(shù)項不同托嚣。
矩陣快速冪解法每步中兩個大整數(shù)乘法是8次
快速平方的矩陣解法每步中兩個大整數(shù)乘法是5次
二分解法每步中兩個大整數(shù)乘法是3次
二進制模冪解法每步中兩個大整數(shù)乘法是2次
有趣巩检，剛好是個Fibonacci數(shù)列
歡迎點贊、留言
未完待續(xù)……
