……續(xù)上回Fibonacci數(shù)列高效解法大全及時(shí)間復(fù)雜度分析 連載【4】
來(lái)看profile的記錄分析，看時(shí)間具體用在哪個(gè)部分了
一看前方，絕大部分時(shí)間耗在兩句results上了
看來(lái)主要都用來(lái)大整數(shù)運(yùn)算了
下面來(lái)試一下
把這程序里兩句“results = ”后面的大數(shù)運(yùn)算注釋掉，換成1。也就是兩句都成“results = 1”
再運(yùn)行計(jì)時(shí)看看
Total time: 0.000753秒
很驚人原在，去掉大數(shù)運(yùn)算后饭宾，運(yùn)行時(shí)間縮短成了原用時(shí)的1%。也就是99%時(shí)間消耗在Python內(nèi)置的大數(shù)運(yùn)算上了
下面試下用號(hào)稱地球上最好的大數(shù)運(yùn)算庫(kù)替換掉Python內(nèi)置的大數(shù)運(yùn)算
9.? 應(yīng)用GMP庫(kù)
全稱是GNU Multiple Precision Arithmetic Library凶异，即GNU高精度算術(shù)運(yùn)算庫(kù)蜀撑，這是一個(gè)C寫成的高效大數(shù)運(yùn)算庫(kù)
gmpy2是Python下對(duì)GMP庫(kù)的封裝
安裝很簡(jiǎn)單，在操作系統(tǒng)下打命令pip install gmpy2剩彬，就安裝好了
應(yīng)用到程序也很簡(jiǎn)單
把上面的二分迭代解法程序開(kāi)頭添加一行
from gmpy2 import mpz
再把程序里
child_nodes = (n, 1)
child_nodes = (n, 0)
改成
child_nodes = (n, mpz(1))
child_nodes = (n, mpz(0))
就可以了
運(yùn)行看一下用時(shí)
Total time: 0.00689297秒
是原用Python內(nèi)置大數(shù)運(yùn)算用時(shí)的9%
效果顯著酷麦。可見(jiàn)Python內(nèi)置大數(shù)運(yùn)算效率確實(shí)不怎么樣
相關(guān)大整數(shù)乘法高效算法的介紹可參見(jiàn)這篇《【算法】大數(shù)乘法問(wèn)題及其高效算法》
極大整數(shù)乘法的時(shí)間復(fù)雜度為O(n*log n)喉恋，簡(jiǎn)記為mul(n)
前面二分解法本身時(shí)間復(fù)雜度是O(log n)
現(xiàn)在把大數(shù)因素考慮進(jìn)去沃饶。大數(shù)時(shí)間復(fù)雜度的n可以用二進(jìn)制位數(shù)表示
第n項(xiàng)斐波那契數(shù)的二進(jìn)制位數(shù)k跟n是線性關(guān)系，n*10瀑晒，那位數(shù)k也是*10
二分解法時(shí)間復(fù)雜度是O(log n)绍坝，也就是迭代log2(n)輪
現(xiàn)在把極大整數(shù)乘法時(shí)間復(fù)雜度代入
每輪參與乘法的數(shù)字二進(jìn)制位數(shù)大致為2^i，也就是mul(2^i)
也就是在大數(shù)情況下二分解法的總體時(shí)間復(fù)雜度為O(n*(log n))
注：看這篇《為什么算法漸進(jìn)復(fù)雜度中對(duì)數(shù)的底數(shù)總為2》
10.? 矩陣解法
斐波那契數(shù)列和矩陣的關(guān)系推導(dǎo)我看到GoCalf Blog里寫的一段非常清晰苔悦，特在此引用
這解法就是求矩陣的n-1次冪轩褐。矩陣冪運(yùn)算也能根據(jù)下面公式迭代二分加速
就是所謂的矩陣快速冪
Python里庫(kù)很豐富，大名鼎鼎的numpy就是一個(gè)有關(guān)矩陣的庫(kù)玖详。這庫(kù)是有優(yōu)化的把介，算矩陣冪就不用個(gè)人再寫什么矩陣快速冪函數(shù)了
用numpy庫(kù)就能很簡(jiǎn)單的寫出來(lái)
因?yàn)閚umpy沒(méi)有大數(shù)支持，大數(shù)運(yùn)算還是要用GMP庫(kù)
import numpy.matlib
from gmpy2 import mpz
def Fibonacci_sequence_06 (n: int) -> int:? #參數(shù)n是表示求第n項(xiàng)Fibonacci數(shù)
? ? '返回單項(xiàng)的矩陣解法'
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? if n>=0:
? ? ? ? fib_matrix = numpy.mat(((mpz(1), mpz(1)), (mpz(1), mpz(0))))
? ? ? ? fib_matrix **= n-1
? ? ? ? return fib_matrix[0,0]
? ? else:
? ? ? ? return None
Fibonacci_sequence_06(1000000)
同上測(cè)用時(shí)
Total time: 0.042466秒
這冪運(yùn)算是二分加速的蟋座，時(shí)間復(fù)雜度為O(log n)
對(duì)于固定階矩陣相乘拗踢，乘的次數(shù)是個(gè)常數(shù)，也就是O(1)向臀。雖然這個(gè)常數(shù)比較大^_*
代入大數(shù)時(shí)間復(fù)雜度巢墅，總體復(fù)雜度也是O(n*(log n))
這兒來(lái)解釋下為何矩陣快速冪比二分遞歸解法時(shí)間常數(shù)大
我們?cè)賮?lái)仔細(xì)看看斐波那契數(shù)列的矩陣形式：
會(huì)發(fā)現(xiàn) z 和 y 必然相等，z 沒(méi)必要再計(jì)算一遍券膀。
t = x - y君纫，因此 t 也沒(méi)必要再計(jì)算一遍。
只需要計(jì)算矩陣第一列的那兩個(gè)元素即可：
矩陣快速冪中兩個(gè)矩陣相乘實(shí)際可分解為8次兩個(gè)大整數(shù)乘法芹彬，而二分遞歸中只需要3次兩個(gè)大整數(shù)乘法蓄髓。所以二分遞歸時(shí)間常數(shù)小。
這兒提一下通項(xiàng)公式解法
其實(shí)與矩陣快速冪是等價(jià)的舒帮，見(jiàn)《幾種計(jì)算Fibonacci數(shù)列算法的時(shí)間復(fù)雜度分析》
未完待續(xù)……
