2-算法效率分析基礎(chǔ)

1、 2-算法效率分析基礎(chǔ)College of Software and Microelectronics算法設(shè)計(jì)與分析Introduction to the Design and Analysis of Algorithms 08 July 2022Northwestern Polytechnical University1Lecture Overview1. 算法效率的度量 2. 函數(shù)的漸進(jìn)的界3. 算法的根本復(fù)雜性類型4.算法復(fù)雜性分析的根本方法5. 非遞歸算法的復(fù)雜性分析6. 遞歸算法的復(fù)雜性分析7. 遞歸算法與非遞歸算法比較8. 經(jīng)驗(yàn)分析方法9. 算法可視化2算法效率的度量算法效率的上下

2、表達(dá)在運(yùn)行該算法所需要消耗資源的多少，對(duì)于計(jì)算機(jī)來講，最重要的資源是時(shí)間和空間，因此，算法效率又可分為時(shí)間效率和空間效率。分別用N，I和A表示要解決問題的規(guī)模、算法的輸入和算法本身，用C表示復(fù)雜性，那么，應(yīng)該有C = F(N, I, A)。如果吧時(shí)間復(fù)雜性與空間復(fù)雜性分開，分別用T和S表示，則T = F(N, I, A)，S = F(N, I, A)。T = T(N, I)，S = S(N, I)。3算法效率的度量計(jì)算機(jī)存儲(chǔ)容量的開展使得算法空間復(fù)雜性已經(jīng)不再是關(guān)注的重點(diǎn)，但時(shí)間復(fù)雜性仍然十分重要。因此，我們后續(xù)也將主要討論算法的時(shí)間復(fù)雜性，但是所討論的方法對(duì)于空間復(fù)雜性分析也是適用的。根據(jù)T

3、 = T(N, I)的概念，它應(yīng)該是算法在一臺(tái)“抽象的計(jì)算機(jī)上運(yùn)行所需要的時(shí)間。4算法效率的度量設(shè)該“抽象的計(jì)算機(jī)所提供的元運(yùn)算有k種，分別記為O1,O2,Ok，又設(shè)每執(zhí)行一次這些元運(yùn)算所消耗的時(shí)間分別為t1,t2,tk。對(duì)于給定算法A，統(tǒng)計(jì)其執(zhí)行過程中用到的元運(yùn)算Oi的次數(shù)，記為ei，i=1,2,k。ei = ei (N, I)。其中，ti是與N和I無關(guān)的常數(shù)。5算法效率的度量我們不可能對(duì)規(guī)模為N的每一種合法輸入I都去統(tǒng)計(jì)ei(N, I)，i=1,2,k。關(guān)于攤銷效率6函數(shù)的漸進(jìn)的界函數(shù)的漸進(jìn)的界設(shè)f 和g 是定義域?yàn)樽匀粩?shù)集N上的函數(shù)(1) f(n)=O(g(n)若存在正數(shù)c和n0使得對(duì)一

4、切nn0有0f(n)cg(n)(2) f(n)= (g(n)若存在正數(shù)c和n0使得對(duì)一切nn0有0cg(n) f(n)(3) f(n)=o(g(n)對(duì)任意正數(shù)c存在n0使得對(duì)一切nn0有0f(n)cg(n)(4) f(n)=(g(n)對(duì)任意正數(shù)c存在n0使得對(duì)一切nn0有0cg(n)1和0，logbn=o(n)，n=o(bn)。n!=o(nn)，n!= (2n)，log(n!)= (nlogn)12算法的根本復(fù)雜性類型13算法復(fù)雜性分析的根本方法（1）決定表示輸入規(guī)模的參數(shù)。（2）找出算法的根本操作。（3）檢查根本操作的執(zhí)行次數(shù)是否只依賴于輸入規(guī)模。如果還依賴于輸入的其它特性，考慮最差、平均以

5、及最優(yōu)情況下的復(fù)雜性。（4）對(duì)于非遞歸算法，建立算法根本操作執(zhí)行次數(shù)的求和表達(dá)式；對(duì)于遞歸算法，建立算法根本操作執(zhí)行次數(shù)的遞推關(guān)系及其初始條件。（5）利用求和公式和法則建立一個(gè)操作次數(shù)的閉合公式，或者求解遞推關(guān)系式，確定增長的階。14非遞歸算法的復(fù)雜性分析對(duì)于等差數(shù)列ak，對(duì)于等比數(shù)列aqk，對(duì)于調(diào)和級(jí)數(shù)1/k，對(duì)數(shù)求和，15非遞歸算法的復(fù)雜性分析例算法 MaxElement(A0.n-1/求給定數(shù)組中的最大元素/輸入：實(shí)數(shù)數(shù)組A0.n-1/輸出：A中的最大元素maxval A0for i 1 to n-1 do if Ai maxval maxval Aireturn maxval16非遞歸

6、算法的復(fù)雜性分析（1）算法輸入規(guī)模：可以用數(shù)組元素個(gè)數(shù)n度量（2）根本操作：比較與賦值兩種，選擇比較（3）比較操作只與輸入規(guī)模相關(guān)，不用考慮最壞、平均、最好情況（4）建立根本操作執(zhí)行次數(shù)求和表達(dá)式（5）確定增長的階17非遞歸算法的復(fù)雜性分析算法 UniqueElements(A0.n-1/驗(yàn)證給定數(shù)組中的元素是否全部唯一/輸入：實(shí)數(shù)數(shù)組A0.n-1/輸出：如果A中的元素全部唯一，返回“true，否則，返回“falsefor i1 to n-2 do for ji +1 to n-1 do if Ai = Aj return falsereturn true18非遞歸算法的復(fù)雜性分析templa

7、tevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4 sum of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum of (ti-1) aj+1=key; / c7 n-1 19非遞歸算法的復(fù)雜性分析在最好情況下，ti=1, for 1 i n;在最壞情況下，ti i+1, for 1 i 0，（2）若 ， （3）若 ， 0，22遞歸算法的復(fù)雜性分析當(dāng)f(n)為常數(shù)時(shí)當(dāng)f(n) = cn時(shí)23遞歸算法的復(fù)雜性分析例i

8、nt hanoi(int n, int a, int b, int c) if (n = 1) move(a, c); else hanoi(n-1, a, c, b); move(a, c); hanoi(n-1, b, a, c); 24遞歸算法的復(fù)雜性分析T(n)= T(n/3)+ T(2n/3)+n25遞歸算法與非遞歸算法比較階乘問題26遞歸算法與非遞歸算法比較int factorial(int n) if(n=0) return 1; return n*factorial(n-1);int factorial(int n) int fn=1; for(int i=2; i=n; i+

9、) fn=fn*i; return fn;27遞歸算法與非遞歸算法比較Fibonacci數(shù)列邊界條件遞歸方程int fibonacci(int n) if (n = 1) return n; return fibonacci(n-1)+fibonacci(n-2);28遞歸算法與非遞歸算法比較29遞歸算法與非遞歸算法比較static int Fibonacci2(int n)int a = new intn;a0 = 1;a1 = 1;for (int i = 2; i n; i+)ai = ai - 1 + ai - 2;return an - 1;30遞歸算法與非遞歸算法比較31遞歸算法與

10、非遞歸算法比較并非所有遞歸算法都有非遞歸定義。Ackerman函數(shù)Ackerman函數(shù)A(n, m)有兩個(gè)獨(dú)立的整型變量m0和 n0，定義如下：當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。32遞歸算法與非遞歸算法比較Ackerman函數(shù)A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：m=0時(shí)，A(n,0)=n+2m=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2故A(n,1)=2nm=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n。m=3時(shí)，類似的可以推出A(n,3)=m=4時(shí)，A(n,4)的增