2第二章 算法效率分析基礎(chǔ)

1、算法分析與設(shè)計 Analysis and Design of Computer Algorithms 第二章 算法效率分析基礎(chǔ)1算法效率分析基礎(chǔ)算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。Time is Important不是所有能計算的都有價值，不是所有有價值的都能被計算 阿爾伯特.愛因斯坦2 School of Computer Science and Technology, SWUST 教學(xué)內(nèi)容算法效率分析框架算法效率的表示符號非遞歸算法的效率分析遞歸算法的效率分析算法的經(jīng)驗分析要求掌握算法中近似時間的表示、非遞歸、遞歸算法的效率分析方法，了解算法的經(jīng)驗分析3 Schoo

2、l of Computer Science and Technology, SWUST 分析框架輸入規(guī)模度量輸入規(guī)模度量算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量。對于所有的算法，對于規(guī)模更大的輸入都需要運行更長的時間。經(jīng)常使用一個輸入規(guī)模n為參數(shù)的函數(shù)來研究算法的效率。選擇輸入規(guī)模的適宜量度，要受到所討論算法的操作細(xì)節(jié)影響。4 School of Computer Science and Technology, SWUST 分析框架運行時間的度量單位運行時間的度量單位用算法的根本操作（算法中最重要的操作）的執(zhí)行次數(shù)來度量算法的時間效率。根本操作通常是算法最內(nèi)層循環(huán)中最費時的操作。算法

3、運行時間的估計：T(n) copC(n)n是該算法的輸入規(guī)模cop是特定計算機上一個算法根本操作的執(zhí)行時間C(n)是該算法需要執(zhí)行的根本操作的次數(shù)5 School of Computer Science and Technology, SWUST 分析框架增長次數(shù)增長次數(shù)小規(guī)模輸入在運行時間上的差異缺乏以將高效的算法和低效的算法區(qū)分開來。一個需要指數(shù)級操作次數(shù)的算法只能用來解決規(guī)模非常小的問題6 School of Computer Science and Technology, SWUST 分析框架算法的最優(yōu)、最差和平均效率算法的最優(yōu)、最差和平均效率最差效率是指在輸入規(guī)模為n時，算法在最壞情

4、況下的效率。最優(yōu)效率是指在輸入規(guī)模為n是，算法在最優(yōu)情況下的效率。平均效率是指在“典型或“隨機輸入的情況下，算法具有的行為（效率）。攤銷效率是指對于同樣的數(shù)據(jù)結(jié)構(gòu)執(zhí)行屢次操作，然后分?jǐn)偟矫恳淮紊稀? School of Computer Science and Technology, SWUST 漸進符號算法效率的主要指標(biāo)是根本操作次數(shù)的增長次數(shù)。為了對這些增長次數(shù)進行比較和歸類，計算機科學(xué)家們使用了3種符號：O（讀“O）：上界（讀omega）：下界（讀theta）：近似8 School of Computer Science and Technology, SWUST 符號O定義1 對于足夠

5、大的n，t(n)的上界由g(n)的常數(shù)倍來確定，即：記為t(n) O(g(n)t(n) cg(n)，c為常數(shù)n O(n2)100n+5 O(n2)n(n-1)/2 O(n2)9 School of Computer Science and Technology, SWUST 符號定義2 對于足夠大的n，t(n)的下界由g(n)的常數(shù)倍來確定，即：記為t(n) (g(n)t(n) cg(n)，c為常數(shù)n3 (n2)n(n+1) (n2)4n2+5 (n2)10 School of Computer Science and Technology, SWUST 符號定義3 對于足夠大的n，t(n)的

6、上界和下界由g(n)的常數(shù)倍來確定，即：記為t(n) (g(n)c2g(n) t(n) c1g(n)，c1,c2為常數(shù)n2+3n+2 (n2)n(n-1)/2 (n2)4n2+5 (n2)11 School of Computer Science and Technology, SWUST 漸進符號的有用特性定理 如果t1(n) O(g1(n)并且t2(n) O(g2(n)，則 t1(n)+ t2(n) O(max(g1(n), g2(n)對于符號和，該定理也成立。該定理說明：當(dāng)算法由兩個連續(xù)執(zhí)行局部組成時，該算法的整體效率由具有較大增長次數(shù)的那局部所決定。12 School of Compu

7、ter Science and Technology, SWUST 利用極限比較增長次數(shù)前兩種情況意味著t(n) O(g(n)后兩種情況意味著t(n) (g(n)第二種情況意味著t(n) (g(n)13 School of Computer Science and Technology, SWUST 根本的效率類型常量(1)、對數(shù)(logn)、線性(n)、nlogn、平方(n2)、立方(n3)、指數(shù)(2n)、階乘(n!)14 School of Computer Science and Technology, SWUST 非遞歸算法的數(shù)學(xué)分析Example 1：討論下面這個算法（從n個元素中查

8、找最大元素問題）的效率。算法 MaxElement(A0.n-1/求給定數(shù)組中的最大元素/輸入：實數(shù)數(shù)組A0.n-1/輸出：A中的最大元素maxval A0for i 1 to n-1 do if Ai maxval maxval Aireturn maxval 考慮：循環(huán)中的操作有比較和賦值，取哪一個作為根本操作？輸入規(guī)模是多少？基本操作為：比較運算輸入規(guī)模就是數(shù)組長度n算法的效率為：15 School of Computer Science and Technology, SWUST 分析非遞歸算法效率的通用方案決定用那些參數(shù)作為輸入規(guī)模的度量。找出算法的根本操作。檢查根本操作的執(zhí)行次數(shù)是

9、否只依賴輸入規(guī)模。建立一個算法根本操作執(zhí)行次數(shù)的求和表達式。利用求和運算的標(biāo)準(zhǔn)公式和法則來建立一個操作次數(shù)的閉合公式，或者至少確定它的增長次數(shù)。16 School of Computer Science and Technology, SWUST Example 考慮下面算法的效率Example 2 元素唯一性問題算法 UniqueElements(A0.n-1)/驗證給定數(shù)組的元素是否全部唯一/輸入：實數(shù)數(shù)組A0.n-1/輸出：如果唯一，返回True，否則Falsefor i0 to n-2 do for ji+1 to n-1 do if Ai=Aj return Falsereturn

10、True Example 3 兩個n階方陣乘法算法 MatrixMuti(A0.n-1,0.n-1,B0.n-1,0.n-1)/根據(jù)定義計算兩個n階矩陣的乘積/輸入：兩個n階矩陣/輸出：矩陣C=ABfor i0 to n-1 do for j0 to n-1 do Ci,j 0.0 for k 0 to n-1 do Ci,j = Ci,j + Ai,k * B k,jreturn C 17 School of Computer Science and Technology, SWUST 遞歸算法的數(shù)學(xué)分析例：對于任意非負(fù)整數(shù)n，計算F(n)=n!的值。F(n)=n(n-1)! , n11 ,

11、 n=11 ,n=0算法 F(n)/遞歸計算n!/輸入：非負(fù)整數(shù)n/輸出：n!的值if n=0 retuen 1else return F(n-1)*nM(n)=M(n-1)+1 , n10 ,n=0M(n)=M(n-1)+1 =M(n-2)+1+1=M(n-2)+2 =M(n-3)+1+2=M(n-3)+3 =M(n-n)+1+n-1=n18 School of Computer Science and Technology, SWUST 分析遞歸算法效率的通用方案決定用哪個參數(shù)作為輸入規(guī)模的度量找出算法的根本操作檢查對相同規(guī)模的輸入，根本操作的執(zhí)行次數(shù)是否相同，如果不同，必須對最差、平均及

12、最優(yōu)效率單獨研究建立一個遞推關(guān)系式及相應(yīng)的初始條件求解這個遞歸關(guān)系式，或者至少確定解的增長次數(shù)19 School of Computer Science and Technology, SWUST 漢諾塔M(n)=2M(n-1)+1 , n11 ,n=1M(n)=2n-1我們應(yīng)該謹(jǐn)慎使用遞歸算法，因為他們的簡潔可能會掩蓋他們的低效率。20 School of Computer Science and Technology, SWUST 斐波那契數(shù)列F(n)=F(n-1)+F(n-2) , n11 , n=10 ,n=00,1,1,2,3,5,8,13,21,34,21 School of Co

13、mputer Science and Technology, SWUST 算法的經(jīng)驗分析對算法效率做經(jīng)驗分析的通用方案了解試驗的目的決定用來度量效率的量度M和度量單位（單位時間內(nèi)的操作次數(shù)）決定輸入樣本的特性為實驗準(zhǔn)備算法的程序?qū)崿F(xiàn)生成輸入樣本對輸入樣本進行計算，并記錄觀察到的實驗數(shù)據(jù)分析獲得的實驗數(shù)據(jù)22 School of Computer Science and Technology, SWUST 23 School of Computer Science and Technology, SWUST 算法可視法通過使用圖形來傳達關(guān)于算法的一些有用信息。算法可視法的種類：靜態(tài)算法可視法動態(tài)算法可視法(算法動畫, Algorithm Animation)24 School of Computer Science and Technology, SWUST 靜態(tài)算法可視法25 School of Computer Science and Technology, SWUST 靜態(tài)算法可視法26 School of Computer Science and Technology, SWUST 動態(tài)算法可視法27 School of Computer Science a