analysisofalgorithms(2)-資料下載頁
2025-07-15 17:42本頁面
【正文】 /2. ? ∴ T(n)=Θ(n3). Idea of the Master method Proof (Case 1) ? n=bh, nloga=ah,nε=bεh. ? f(n)≤logaε=cah/bεh =f(bh)≤c(ah/bεh) ? T(n)=ahT(1)+∑akf(bhk),(∑: k=0,…,h1) ? T(n)≤ahT(1)+c∑ak(ahk/bε(hk)) =ahT(1)+cah∑(1/bε(hk)) ≤ ahT(1)+cah∑1≤k∞(1/bεk) ≤c’ah (因 b1,ε0,無 窮 和收 斂 ) ? 所以 T(n)=O(nloga)。 顯 然 , T(n)=?(nloga) Proof of Case2 ? f(n)=Θ(nloga lgkn), n=bh, nloga=ah ? f(n)≤cah(hlgb)k=cahhk(lgb)k ? T(n)≤ahT(1)+cah∑i i k (lgb)k≤ ahT(1)+c’ah hk+1 (lgb)k =ahT(1)+ c’ah hk+1 (lgb)k+1 /lgb=c’’(nlogalgk+1n) ? 上面推導中用到 : 1k+…+hk=Θ(hk+1) 裴波那契 (Fibonacci)序列 ?序列 F0=F1=1,Fi=Fi1+Fi2 (i1)稱為 Fibonacci序列 . 以下算法計算第 n個 Fibonacci數(shù) : proc F(n) if n≤1 return(1) else return( F(n1)+F(n2))。 end proc ?令 t(n)為算法執(zhí)行的加法次數(shù) ,有 : t(n)=0 for n=0,1 t(n)=t(n1)+t(n2)+1 特別 t(2)=1,t(3)=2 續(xù) ? 因為 t(n1)t(n2),有 t(n)2t(n1)+1,for n2. 用歸納法易證 : t(n)≤2n ? 又有 t(n)2t(n2)┅ 2k1t(2)=2k1 n=2k 2k1t(3)=2k n=2k+1 ? t(n)= ? t(n)= ? 算法有指數(shù)的時間復雜度 . ? 實際上這是因遞歸引起的大量的重復計算而非問題本身的難度所致 .可設(shè)計一非常簡單的線性時間復雜度的迭代算法 . )2( n?))2((
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1