遞歸方程求解方法綜述

《遞歸方程求解方法綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、遞歸方程求解方法綜述摘要：隨著計(jì)算機(jī)科學(xué)的逐步發(fā)展，各種各樣的算法相繼出現(xiàn)，我們需要對算法進(jìn)行分析，以選擇性能更好的解決方案。算法分析中計(jì)算復(fù)雜度常用遞歸方程來表達(dá)，因此遞歸方程的求解有助于分析算法設(shè)計(jì)的好壞。闡述了常用的3種求解遞歸方程的方法：遞推法、特征方程法和生成函數(shù)法。這3種方法基本上可以解決一般規(guī)模遞歸方程的求解問題。關(guān)鍵詞：遞歸；遞推法；特征方程；生成函數(shù)0引言尋求好的解決方案是算法分析的主要目的，問題的解決方案可能不只一個(gè)，好的方案應(yīng)該執(zhí)行時(shí)間最短，同時(shí)占有存儲(chǔ)空間最小，故算法分析一般考慮時(shí)間復(fù)雜性、空間復(fù)雜性兩方面的參數(shù)。在算法分析

2、時(shí)我們采用時(shí)間耗費(fèi)函數(shù)來表示時(shí)間參數(shù)，用當(dāng)問題規(guī)模充分大時(shí)的時(shí)間耗費(fèi)函數(shù)的極限表示時(shí)間復(fù)雜度。一般算法對應(yīng)的時(shí)間耗費(fèi)函數(shù)常用遞歸方程表示，找出遞歸方程的解，就可以表示其對應(yīng)算法復(fù)雜度的漸進(jìn)階，從而比較算法的優(yōu)劣。因此研究遞歸方程的解法意義重大。下文將分析并給出常用遞歸方程的3種解法。1遞歸方程的解法遞歸方程是對實(shí)際問題求解的一種數(shù)學(xué)抽象,遞歸的本質(zhì)在于將原始問題逐步劃分成具有相同解題規(guī)律的子問題來解決,原始問題與子問題僅在規(guī)模上有大小區(qū)別,并且子問題的規(guī)模比原始問題的規(guī)模要小。對于規(guī)模為n的原始問題,我們通常會(huì)尋找規(guī)模n的問題與規(guī)模n-1或者規(guī)模n

3、/2的問題之間存在的聯(lián)系,從而進(jìn)一步推導(dǎo)出具有遞歸特性的運(yùn)算模型。根據(jù)遞歸方程的一般形式，常用的解法有三種，分別是遞推法、公式法及生成函數(shù)法。下面就分別來分析其求解過程。1.1遞推法當(dāng)遞歸方程形式簡單且階數(shù)較低時(shí)，一般可以采用遞推法求解，根據(jù)一步一步遞推找到方程的遞推規(guī)律，得到方程的解。下面舉例說明：t(1)=0t(n)=2t(n/2)+n2(n≥2)t(n)=2t(n/2)+n2=2(2t(n/22)+(n/2)2)+n2=22t(n/2)2+2n2/22+n2=22(2t(n/23)+(n/22)2)+2n2/22+n2=23(2t(n/23)

4、+22n2/(22)2)+2n2/(22)1+n2…=2kt(n/2k)+∑k-1i=02in2(22)i遞推到這里我們就可以發(fā)現(xiàn)遞歸規(guī)律，找到遞歸出口，t(1)=0，令n=2k則可以得到如下結(jié)果：t(n)=2kt(1)+∑k-1i=0n2(1/2)i)=n2(1-(1/2)k1-1/2)=2n2-2n上面得到方程的解，我們來分析其對應(yīng)算法復(fù)雜性的漸進(jìn)階，根據(jù)漸進(jìn)階定理有：設(shè)有函數(shù)f(n)，g(n）均是規(guī)模n的函數(shù)，則o(f(n))+o(g(n))=o(max(f(n),g(n)))。故有t(n)=o(n2)。1.2公式法對所需求解的遞歸方程進(jìn)行觀

5、察，如果它是符合以下形式的常系數(shù)齊次線性方程，可用公式法求解。f(0)=b0;f(1)=b1;……f(k-1)=bk-1;f(n)=a1f(n-1)+a2f(n-2)+…+akf(n-k)在此，常系數(shù)是指a1、a2、……ak是常數(shù)，線性指所有的f均為一次冪，齊次指無常數(shù)項(xiàng)。解這類方程，可由f(n)項(xiàng)得出：f(n)-a1f(n-1)-a2f(n-2)-…-akf(n-k)=0;尋找形如f(n)=xn的解。令xn-a1xn-1-a2xn-2-…-akxn-k=0；xn-k(xk-a1xk-1-…-ak)=0；即xk-a1xk-1-…-ak=0；由此，我

6、們得到了這類遞歸方程的特征方程，它有n個(gè)特征根，設(shè)為x1,x2,…,xk；其線性組合是f(n)的通解。即c1x1n+c2x2n+…+ckxkn=f(n)；其中c1,c2,…,ck可由k個(gè)初始條件得到的線性方程組解出。例如，常系數(shù)齊次線性方程組f(0)=0;f(1)=1;f(n)=4f(n-2);(n＞1)令f(n)=xn；則xn=4xn-2；xn-4xn-2=0；x2-4=0；（特征方程）x1=2；x2=-2；（特征根）設(shè)有c1,c2使f(n)=c1x1n+c2x2n；由初始條件f(0)=c1x10+c2x20=c1+c2=0;f(1)=c1x11

7、+c2x21=2c1-2c2=1；即c1+c2=0;2c1-2c2=1解得c1=1/4；c2=-1/4；∴f(n)=2n/4-(-2)n/4即為以上遞歸方程的解。1.3生成函數(shù)法第三種方法是利用生成函數(shù)的方法，即已知一個(gè)數(shù)列a0,a1,a2,…,an,定義它的生成函數(shù)為一個(gè)形式冪級數(shù)：f(x)=a0+a1x1+a2x2+…+anxn+…我們尋找an的代數(shù)式。有了生成函數(shù)f(x),無需知道a0,a1,a2,…,an的各項(xiàng)就可以設(shè)法找出它的生成函數(shù)的解析式，再將其展開成一個(gè)冪級數(shù)，則xn項(xiàng)的系數(shù)即為要求得的an。以漢諾(hanoi)塔問題的遞歸方程為例

8、：t(1)=1;t(n)=2t(n-1)+1;(n≥2)該序列的生成函數(shù)為：t(x)=t(1)x+t(2)x2+t(3)x