【正文】 ? ????? ? ? ??? ? ? ? ? ????遞歸算法的數(shù)學分析 ?例：對于任意非負整數(shù) n，計算 F(n)=n!的值。每次循環(huán)時， 每種操作均被執(zhí)行一次，所以任選一種作為基本操作均可，因它們的 執(zhí)行次數(shù)相同。 注 2 當比較兩個算法的效率時 ,若兩個算法是同階的 ,必須進一步考察階的常數(shù)因子才能辨別優(yōu)劣。 直接分析法 統(tǒng)計或者假設隨機輸入的概率分布，以推導基本操作的平均次數(shù)。 最差時間效率 —— 若鍵位于表中，比較次數(shù)不定。 一個算法有許多操作，決定算法耗時的是那些 最費時 的操作， 因此，只需統(tǒng)計這些最費時的操作稱為 基本操作 。 Time is Important 不是所有能計算的都有價值，不是所有有價值的都能被計算 ——阿爾伯特 .愛因斯坦 算法分析 ?需解決的問題 ?度量一個算法的時間效率 (時間費用 ) ?度量一個算法的空間效率 (空間費用 ) ?優(yōu)化算法 ?最小化一個算法的時間效率或空間效率 ?途徑 ?理論分析 ?經(jīng)驗分析 分析框架 —— 輸入規(guī)模度量 ?輸入規(guī)模度量 ?算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量。因為 t 減少 10 倍， C(n) 不變。 實際中考慮該最差效率是否可以接受。 后續(xù)章節(jié)中，除特別說明外，都采用最差時間效率。 4. 建立一個算法基本操作執(zhí)行次數(shù)的求和表達式。 F(n)= n(n1)! , n1 1 , n=1 1 ,n=0 算法 F(n) //遞歸計算 n! //輸入：非負整數(shù) n //輸出： n!的值 if n=0 retuen 1 else return F(n1)*n M(n)= M(n1)+1 , n≥1 0 ,n=0 M(n)=M(n1)+1 =[M(n2)+1]+1=M(n2)+2 =[M(n3)+1]+2=M(n3)+3 …… =[M(nn)+1]+n1=n f u n (5 ) d 1 :f u n (4 ) d 2 :f u n (3 ) d 3 :f u n (2 ) d 4 :f u n (1 ) 返回 1 f u n (2 )=2 f u n (3 )=6 f u n (4 )=2 4 f u n (5 )=1 2 0 求解 5!的過程如下： 分析遞歸算法效率的通用方案 ?決定用哪個參數(shù)作為輸入規(guī)模的度量 ?找出算法的基本操作 ?檢查對相同規(guī)模的輸入，基本操作的執(zhí)行次數(shù)是否相同，如果不同，必須對最差、平均及最優(yōu)效率單獨研究 ?建立一個遞推關(guān)系式及相應的初始條件 ?求解這個遞歸關(guān)系式，或者至少確定解的增長次數(shù) 漢諾塔 M(n)= 2M(n1)+1 , n1 1 ,n=1 M(n)=2n1 我們應該謹慎使用遞歸算法，因為他們的簡潔可能會掩蓋他們的低效率。 基本操作： 最內(nèi)層循環(huán)有三種操作：乘法、加法、賦值。1logli m li m 02 l g1o2nnnnnnennnne? ? ? ?? ? ? ??? ? ?常 數(shù)— — 羅 必 塔 法 則【 例 3】 !2 nn比 較 和 的 增 長 次 數(shù)2 ( )!li m li m22li m 2 li m 2 ( )22nnnnnnnnnnnnnn ennee???? ? ? ?? ? ? ??? ? ? ?— — 史 特 林 公 式基本的效率類型 常量 (1)、對數(shù) (logn)、線性(n)、 nlogn、平方 (n2)、立方 (n3)、指數(shù) (2n)、階乘 (n!) 關(guān)于漸進時間效率： 注 1 對規(guī)模較小的問題 ,決定算法工作效率的可能是算法的簡單性而不是算法執(zhí)行的時間。 —— 平均效率不是最優(yōu)和最差效率的平均值。 最優(yōu)時間效率 —— 若鍵位于表尾或不存在，比較 n 次。 問： 統(tǒng)計算法 每步操作執(zhí)行次數(shù) 作為算法的時間度量，如何？ 答： 無此必要，且分析復雜困難（若干變量）。 ?對于所有的算法，對于規(guī)模更大的輸入都需要運行更長的時間。 2 設 ，輸入規(guī)模 n 翻倍，算法運行時間如何變化？ 1( ) ( 1 )2C n n n??221 1 1 1( ) ( 1 )2 2 2 2C n n n n nn? ? ? ? ? （ n 不太小如 n = 100） 221( 2 )( 2 ) ( 2 )2 ()1( ) (4)2nT n tC nT n tC n n? ? ? ? 倍不考慮每個操作步在機器上具體的執(zhí)行時間 t ，則時間耗費為： ( ) ( )T n C n? 時間耗費即基本操作數(shù)，是輸入規(guī)模 n 的函數(shù) n , n2 —— 線性、二次增長率 , 2n —— 指數(shù)增長率 11 分析框架 —— 增長次數(shù) ?增長次數(shù) ?小規(guī)模輸入在運行時間上的差別不足以將高效的算法和低效的算法區(qū)分開來。 【 例 】 順序查找