2-算法效率分析基礎

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

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

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

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

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

6、算法的復雜性分析（1）算法輸入規(guī)模：可以用數(shù)組元素個數(shù)n度量（2）根本操作：比較與賦值兩種，選擇比較（3）比較操作只與輸入規(guī)模相關(guān)，不用考慮最壞、平均、最好情況（4）建立根本操作執(zhí)行次數(shù)求和表達式（5）確定增長的階17非遞歸算法的復雜性分析算法 UniqueElements(A0.n-1/驗證給定數(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非遞歸算法的復雜性分析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非遞歸算法的復雜性分析在最好情況下，ti=1, for 1 i n;在最壞情況下，ti i+1, for 1 i 0，（2）若 ， （3）若 ， 0，22遞歸算法的復雜性分析當f(n)為常數(shù)時當f(n) = cn時23遞歸算法的復雜性分析例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遞歸算法的復雜性分析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)有兩個獨立的整型變量m0和 n0，定義如下：當一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。32遞歸算法與非遞歸算法比較Ackerman函數(shù)A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)：m=0時，A(n,0)=n+2m=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2故A(n,1)=2nm=2時，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時，類似的可以推出A(n,3)=m=4時，A(n,4)的增