1、算法分析理論 -遞歸程序的復雜性分析宮秀軍天津大學計算機科學與技術學院http:/ 遞歸遞歸: Recurrences RelationnRecurrences RelationqA recurrence relation is an equation which is defined in terms of itself. nSolving RecurrencesqRecursion treeqIteration methodqSubstitution methodqMaster methodMerge-SortMerging two sorted arraysMerge-Sort Anal

2、ysis假定n=2h ,h0,上式變為2T(n/2)Recurrence for merge sortn隱含假定n=2h.n以cn代替(n),不影響漸近分析的結果.n“If n=1”,更一般的情形是“if nn0, T(n)=(1)”：q可找到足夠大常數c1,使得 T(n)c1 if n 0 為常數.n遞歸展開到T(n0),會導致推導的麻煩.所以展開到T(1).然后在從前n0個T(n)的值確定漸近分析的常數.Recursion treenSolve T(n) = 2T(n/2) + cn, where c 0 is constant.Recursion treenSolve T(n) = 2T

3、(n/2) + cn, where c 0 is constant.Recursion treeMerge Sort 小結n ( (n n lg lg n n) )比比(n n2 2) )增增長長的慢的慢.n所以所以,merge sort 漸近漸近(asymptotically)優于插優于插入排序入排序.n實際上實際上, merge sort 優于優于 insertion sort 僅當僅當 n 30 or so.n1000*nlogn算法當算法當n比較小時未必比比較小時未必比n2算法要算法要快快. n足夠大時前者才能看出優勢足夠大時前者才能看出優勢.迭代法 1nT(n)=2T(n/2)+cn

4、 =2(2T(n/22)+cn/2)+cn =22T(n/22)+cn+cn =2hT(n/2h)+hcn當 2h=n, then =nT(1)+logn*cn =(nlogn)當當n2hn2hn n= ( (2h), h= ( (logn)nT(2h) T(n) T(2h+1).n所以所以,(h2h)T(n)(h+1)2h+1)n(h+1)2h+1)=(h2h+1+2h+1) =(h2h+1)=(h2h) n所以所以T(n)=(h2h)=(nlogn)迭代法 2nT(n)=4T(n/2)+n =4(4T(n/22)+n/2)+n =42T(n/22)+n+2n =43T(n/23)+n+2n

5、+22n =4hT(n/2h)+n(1+2+2h-1) =n2T(1)+n(2h-1) =(n2) 較一般的遞歸式較一般的遞歸式n較一般的遞歸較一般的遞歸:T(n)=aT(n/b)+cn, a,b是大于1的整數的整數,遞歸樹方法仍可使用遞歸樹方法仍可使用.n首先考慮首先考慮n=bh情形情形: T(n)=ahT(1)+cn(1+(a/b)+(a/b)h-1) = ahT(1)+cah(1+(a/b)+(a/b)h-1) n當當bhn h= ( (logn)n遞歸樹等價于迭代展開遞歸樹等價于迭代展開n很多遞歸式用遞歸樹解不出來很多遞歸式用遞歸樹解不出來,但遞歸樹能提供直覺但遞歸樹能提供直覺,幫助我

6、們用歸納法求解幫助我們用歸納法求解(Guess 歸納假設歸納假設).Substitution methodsnThe most general method:1. Guess the form of the solution.2. Verify by induction.3. Solve for constants.Example1nT (n) = 4T (n/2) + n （n=2h）nAssume that T (1)=(1).nGuess O(n3) :歸納假定為T (n)cn3. c是待定常數.n應用假定有:T (k) ck3 for k n .n歸納證明: T (n) cn3 并確定

7、常數c.Example (continued)nT(n)=4T(n/2)+n 4c(n/2)3+n =(c/2)n3+n =cn3-(c/2)n3-n) cncn3 3 取取 c2 and n1,不等式不等式(c/2)n3n0成立成立Example (continued)n還要檢驗初始條件是否滿足歸納假設還要檢驗初始條件是否滿足歸納假設.n初始條件為初始條件為: T(n)= = ( (1),當當 nn0 ,n0為常數為常數.n因為有常數因為有常數n0-1個T的值的值:T(1),T(n0-1)n所以我們可取所以我們可取c足夠大足夠大,使得使得T(n)cn3, 對對nn0 成立成立.nThis b

8、ound is not tight!Example (continued)nWe shall prove that T(n)=O(n2).nAssume that T(k)ck2 for kn:nT(n)=4T(n/2)+n 4c(n/2)2+n =cn2+nn歸納不能往下進行！歸納不能往下進行！ ContinuednIDEA: Strengthen the inductive hypothesis.nSubtract a low-order term.nInductive hypothesis: T(k)c1k2 c2k for k1Continued nFor 1n 0 T(n) = (n

9、logb a).qf(n) = (nlogb a) T(n) = (nlogb a lg n).qf(n) = (nlogb a + ), for 0,and a f(n / b) c f(n),for c 0,為某一常數某一常數 f(n)的增長漸近地慢于的增長漸近地慢于nloga (慢慢 n 倍倍).nSolution: T(n)=(nloga) .The Master Method:情形情形2n情形情形2: f(n)= (nloga lgkn) k0 為某一常數為某一常數.nf(n) 和和 nloga 幾乎有相同的漸近增長率幾乎有相同的漸近增長率.因為因為nloga lgkn=O(n+lo

10、ga) , for any 0.nSolution: T(n)= (nloga lgk+1n) .The Master Method:情形情形3n情形情形3nf(n)=(nloga +) 0為一常數為一常數. f(n)多項式地快于多項式地快于nloga (by an n factor),nf(n) 滿足以下規則性條件滿足以下規則性條件: af(n/b)cf(n), 0cf(bh)c(ah/bh) )nT(n)=ahT(1)+akf(bh-k),(: k=0,h-1)nT(n)ahT(1)+ca ak k( (ah-k/b(h-k) =ahT(1)+cah(1 1/b(h-k) ahT(1)+c

11、ah1k1,0,無窮和收斂) n所以T(n)=O(nloga); 顯然, T(n)=(nloga)Proof of Case2nf(n)= (nloga lgkn), n=bh, nloga=ahnf(n)cah(hlgb)k=cahhk(lgb)k nT(n)ahT(1)+cahi i k (lgb)k ahT(1)+cah hk+1 (lgb)k =ahT(1)+ cah hk+1 (lgb)k+1 /lgb=c(nlogalgk+1n)n上面推導中用到上面推導中用到: 1k+hk= (h(hk+1k+1) )裴波那契(Fibonacci)序列n序列F0=F1=1,Fi=Fi-1+Fi-2

12、 (i1)稱為Fibonacci序列. 以下算法計算第n個Fibonacci數: proc F(n) if n1 return(1) else return( F(n-1)+F(n-2); end procn令t(n)為算法執行的加法次數,有: t(n)=0 for n=0,1 t(n)=t(n-1)+t(n-2)+1 特別t(2)=1,t(3)=2 續n因為t(n-1)t(n-2),有 t(n)2. 用歸納法易證: t(n)2n n又有t(n)2t(n-2)2k-1t(2)=2k-1 n=2k 2k-1t(3)=2k n=2k+1nt(n)=nt(n)=n算法有指數的時間復雜度.n實際上這是因遞歸引起的大量的重復計算而非問題本身的難度所致.可設計一非常簡單的線性時間復雜度的迭代算法. )2(n)2(nAPT Topics on Algorithm PerformancenDo performance analysis on algorithms from your per