……續(xù)上回Fibonacci數(shù)列高效解法大全及時間復(fù)雜度分析 連載【6】
前面說的都是計算一個斐波那契數(shù)列中的數(shù)
這篇來談?wù)勆伸巢瞧鯏?shù)列前n項及探討下時間復(fù)雜度
13.? 生成數(shù)列的for迭代解法
先給出程序
import numpy
from gmpy2 import mpz
def Fibonacci_sequence_11 (n: int) -> list:? #參數(shù)n是表示求n項Fibonacci數(shù)列
? ? '返回列表的for迭代解法'
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? if n>=2:
? ? ? ? fib_list = numpy.empty(n + 1, numpy.object)
? ? ? ? fib_list[0] = mpz(0); fib_list[1] = mpz(1)
? ? ? ? for i in range(2, n+1):
? ? ? ? ? ? fib_list[i] = fib_list[i - 1] + fib_list[i - 2]
? ? ? ? return fib_list
? ? elif n==1:
? ? ? ? return numpy.array([mpz(0), mpz(1)])
? ? elif n==0:
? ? ? ? return numpy.array([mpz(0)])
? ? else:
? ? ? ? return None
生成數(shù)列前n項，那算法時間復(fù)雜度的下限就是O(n)
這迭代解法是不是呢
從表面上看這算法時間復(fù)雜度是O(n)朗徊，循環(huán)N次兩個數(shù)的加法
然而
但是由缆，一旦數(shù)的范圍擴展到大數(shù)豪墅，就不能認(rèn)為兩數(shù)相加是個常數(shù)時間復(fù)雜度了
兩大數(shù)相加會被分段相加界睁，大整數(shù)二進制位長為k，那么大整數(shù)相加時間復(fù)雜度也就是O(k)
如前篇所說辕近，第n項斐波那契數(shù)的二進制位長k跟n是線性關(guān)系
帶入上面的迭代解法，那這迭代解法的時間復(fù)雜度就是O(n^2)
好好的O(n)算法迹冤，遇上大數(shù)就悲劇了讽营，成了至少O(n^2)時間復(fù)雜度
那下面再看之前最快的兩種生成斐波那契數(shù)算法在生成數(shù)列效率如何
14.? 生成數(shù)列的GMP內(nèi)置fib2函數(shù)解法
import gmpy2
def Fibonacci_sequence_19 (n: int) -> list:? #參數(shù)n是表示求n項Fibonacci數(shù)列
? ? '返回列表的GMP內(nèi)置fib函數(shù)解法'
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? if n>=0:
? ? ? ? fib_list = []
? ? ? ? for i in range(n, 0, -2):
? ? ? ? ? ? fib_list.extend(gmpy2.fib2(i))
? ? ? ? if n & 1 == 0:
? ? ? ? ? ? fib_list.append(gmpy2.mpz(0))
? ? ? ? fib_list.reverse()
? ? ? ? return fib_list
? ? else:
? ? ? ? return None
因fib2的時間復(fù)雜度是O(n*(log n))
那代入這O(n)循環(huán)，此解法時間復(fù)雜度為O(n^2*(log n))
15.? 生成數(shù)列的二分遞歸解法
大數(shù)運算部分用了gmpy2庫
from gmpy2 import mpz
def Fibonacci_sequence_17 (n: int) -> list:? #參數(shù)n是表示求n項Fibonacci數(shù)列
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? cache = dict()
? ? def Calculate_Fibonacci_sequence (n: int) -> int:
? ? ? ? '返回列表的二分遞歸解法'
? ? ? ? nonlocal cache
? ? ? ? if n in cache:
? ? ? ? ? ? return dict.get(cache, n)
? ? ? ? else:
? ? ? ? ? ? if n >= 2:
? ? ? ? ? ? ? ? one_half_n = n >> 1
? ? ? ? ? ? ? ? one_half_fib_n = Calculate_Fibonacci_sequence(one_half_n)
? ? ? ? ? ? ? ? if n & 1 == 0:? #當(dāng)n為偶數(shù)項
? ? ? ? ? ? ? ? ? ? one_half_fib_n_minus_one = Calculate_Fibonacci_sequence(one_half_n - 1)
? ? ? ? ? ? ? ? ? ? results = (one_half_fib_n_minus_one * 2 + one_half_fib_n) * one_half_fib_n
? ? ? ? ? ? ? ? else:? #當(dāng)n為奇數(shù)項
? ? ? ? ? ? ? ? ? ? one_half_fib_n_add_one = Calculate_Fibonacci_sequence(one_half_n + 1)
? ? ? ? ? ? ? ? ? ? results = one_half_fib_n ** 2 + one_half_fib_n_add_one ** 2
? ? ? ? ? ? ? ? cache.update({n: results})
? ? ? ? ? ? ? ? return results
? ? ? ? ? ? elif n == 1:
? ? ? ? ? ? ? ? cache.update({1: mpz(1)})
? ? ? ? ? ? ? ? return mpz(1)
? ? ? ? ? ? elif n == 0:
? ? ? ? ? ? ? ? cache.update({0: mpz(0)})
? ? ? ? ? ? ? ? return mpz(0)
? ? if n >= 0:
? ? ? ? for i in range(n, 1, -1):
? ? ? ? ? ? if i not in cache:
? ? ? ? ? ? ? ? Calculate_Fibonacci_sequence(i)
? ? ? ? fib_list=[None] * (n + 1)
? ? ? ? for i in range(n+1):
? ? ? ? ? ? fib_list[i] = dict.get(cache, i)
? ? ? ? return fib_list
? ? else:
? ? ? ? return None
時間復(fù)雜度分析叁巨，最外層循環(huán)是O(n)斑匪，內(nèi)層調(diào)用Calculate_Fibonacci_sequence因為被全局緩存，在外層n次調(diào)用完成不會超過n次锋勺，所以是O(1)蚀瘸，大整數(shù)運算是O(n*log n)
這解法時間復(fù)雜度就為O(n^2*log n)
比用GMP內(nèi)置fib函數(shù)生成數(shù)列時間復(fù)雜度更低
我算法課學(xué)得不好，以上如果有錯誤還望大佬們給指出
歡迎點贊庶橱、留言
未完待續(xù)……
