第二章 算法分析基礎

算法分析與設計主講：徐曉蓉郵箱：rortyrong@163.com所在院系：計算機科學與技術(shù)學院第2章算法分析基礎本章主要內(nèi)容:算法復雜度好算法的特征影響程序運行時間的因素如何分析算法的時間復雜度算法分析的漸進表示法使用遞推關(guān)系分析遞歸算法第2章算法分析基礎2.1算法復雜度

算法復雜度:是指運行一個算法所需的時間和空間資源的量.2.1.1什么是好的算法?一個好算法應該具備的特征:正確性:即滿足預先規(guī)定的功能和性能簡單性:算法思路清晰,層次分明,容易理解,易于編碼和測試.健壯性:當輸入不合法數(shù)據(jù)時,能適當處理而不引起嚴重錯誤高效率低存儲:算法應有效使用存儲空間,并具有高的時間效率.最優(yōu)性:算法的執(zhí)行時間已達到求解該類問題所需時間的下界.

第2章算法分析基礎2.1算法復雜度

算法復雜度:是指運行一個算法所需的時間和空間資源的量.2.1.1什么是好的算法?判斷一個算法是否最優(yōu)的方法:看算法的最壞時間復雜度是否與求解該類問題所需的時間下界相等.如:最大元問題任何通過元素之間的比較的方式來求解此問題的正確算法至少需要進行n-1次元素間的比較,而n-1次元素比較是求最大元問題所需時間的下界，故,任意在最壞情況下只需n-1次元素比較的算法，便是求解該問題的最優(yōu)算法最優(yōu)算法不唯一

第2章算法分析基礎2.1.2影響程序運行時間的因素程序的運行時間:是程序運行從開始到結(jié)束所需的時間.影響程序運行時間的因素算法問題規(guī)模特定的輸入計算機軟硬件環(huán)境(編譯程序,編程語言,CPU運算速度的快慢，內(nèi)存空間的大小，等等)第2章算法分析基礎2.1.3算法的時間復雜度定義:算法運行所需的時間分析方法事先分析:算法運行之前,對它的效率進行分析事后分析:通過運行程序,測試算法實際運行的時間要分析算法的時間復雜度，必須搞清楚以下兩個問題:用怎樣的一個量來度量算法的時間復雜度(量)給定一個算法,如何具體計算它的復雜性(計算)第2章算法分析基礎2.1.3算法的時間復雜度例1:已知整型數(shù)組A中含有n個互不相同且已按遞增順序排好序的整數(shù)，現(xiàn)要求在數(shù)組A中查找某一整數(shù)C,若找到，返回相應的下標，若未找到，返回-1.方法:順序查找法和二分法intsearch(intA[],intn,intC){inti=0;for(i=0;i<n;i++)if(A[i]==C)break; if(i==n)return-1;elsereturni; }算法1-1:順序查找分析:當C==A[0]時,只需做1次比較.當C==A[i]時,只需做i+1次比較.當C==A[n-1]時,只需做n次比較.故：最好情況下：Tbest(n)=1；

最壞情況下：Tworst(n)=n；

第2章算法分析基礎

算法1-2:二分查找(假定C是A的最后一元)分析:當C==A[mid]時，只需做1次比較.

當C==A[n-1]時,需做log2n+1次比較.故：最好情況下：Tbest（n）=1；最壞情況下：Tworst(n)=log2n+1；intb-search(intA[],intn,intC){intlow=0,high=n-1;intmid;while(low<=high){mid=(low+high)/2;if(A[mid]==C)returnmid;elseif(A[mid]<C)low=mid+1;elsehigh=mid-1;} return-1;}(1)算法時間復雜性的計量：用算法執(zhí)行基本運算的次數(shù)來表示算法的時間復雜度。所謂基本運算：是指算法中最主要最基本的運算與基本運算的次數(shù)相關(guān)的量：算法問題規(guī)模(n)特定輸入數(shù)據(jù)(I).時間復雜度T(n,I)：為基本運算的次數(shù)時間復雜度有三種:最壞時間復雜度:W(n)=最好時間復雜度B(n)=平均時間復雜度A(n)=

其中:Dn:規(guī)模為n的所有合法輸入的集合,I*:Dn中達到W(n)的輸入:Dn中達到B(n)的輸入,P(I):出現(xiàn)輸入為I的概率.第2章算法分析基礎(2)如何計算某一算法的時間復雜度？舉例：順序查找算法的平均時間復雜度1,確定基本運算為比較運算;2,計算基本運算的次數(shù):

假設C在數(shù)組A中,且C為數(shù)組A中每一個元素的概率都相等,則P(i)=1/n,i=0…n-1;

分析得:當C與A[i]相等時，算法進行了i+1次比較運算,即算法的運行時間T(i,n)=i+1那么,該算法的平均時間復雜度為

A(n)=T(0,n)/n+T(1,n)/n+…+T(n-1,n)/n=(1+2+….n)/n=(n+1)/2第2章算法分析基礎(2)如何計算某一算法的時間復雜度？舉例：兩個nxn的矩陣相乘:設矩陣A和B都是nxn的矩陣,現(xiàn)要求計算A和B的乘積C1,基本運算:兩數(shù)相乘2,基本運算的次數(shù):第2章算法分析基礎voidFunction(int**A,int**B,intn,int**C){inti,j,k;for(i=0;i<n;i++)for(j=0;i<n;j++){C[i][j]=0;for(k=0;k<n;k++)C[i][j]+=A[i][k]*B[k][j];}}(2)如何計算某一算法的時間復雜度？舉例：Hanoi塔問題:1,基本運算:盤子的移動2,基本運算的次數(shù):第2章算法分析基礎voidHanoi(intn,charX,charY,charZ){if(n){Hanoi(n-1,X,Z,Y);move(n,X,Z);Hanoi(n-1,Y,X,Z);}}(2)如何計算某一算法的時間復雜度？舉例：n個數(shù)累加問題:1,基本運算:加法2,基本運算的次數(shù):第2章算法分析基礎floatSum(floatlist[],intn){floattempsum=0.0;for(inti=0;i<n;i++)tempsum+=list[i];returntempsum;}floatRSum(floatlist[],intn){if(n)returnRSum(list,n-1)+list[n-1];return0;}第2章算法分析基礎2.1.5算法的空間復雜度定義:算法運行所需的存儲空間算法所需存儲空間的組成：固定空間程序代碼常量，簡單變量，結(jié)構(gòu)體變量可變空間數(shù)據(jù)額外空間:(1)工作單元（如工作棧，直接插入排序中的監(jiān)視哨，求某一矩陣時所需的單位矩陣所占空間;(2)某種數(shù)據(jù)結(jié)構(gòu)所需的附加存儲空間（如鏈表中的next域）減少存儲空間的方法:壓縮存儲,盡量使算法原地工作。第2章算法分析基礎2.2漸進表示法1)漸進性態(tài)設T(n)為算法A的時間復雜性函數(shù),則它是n的單增函數(shù),如果存在一個函數(shù)使得當n,有稱是T(n)當n

時的漸進性態(tài)或漸進復雜性.在數(shù)學上,T(n)與有相同的最高階項.可取為略去T(n)的低階項后剩余的主項.當n充分大時我們用代替T(n)作為算法復雜性的度量,從而簡化分析.

例如T(n)=3n2+4nlogn+7,則可以是3n2.

漸進分析適用于n充分大的情況,當問題的規(guī)模很小時,或比較的兩算法同階時,則不能做這種簡化.2).漸進性態(tài)的階例如3n=O(n),n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)

若存在正常數(shù)c和自然數(shù)N0，使得當N

N0時,有f(N)cg(N),則稱函數(shù)f(N)在N充分大時有上界,且g(N)是它的一個上界,記為f(N)=O(g(N)),稱為大O記號.

設f(N)和g(N)是定義在正整數(shù)集上的正函數(shù),(1)大O表示法(算法運行時間的上限)第2章算法分析基礎因為對n>1,有n2<=n3可選c=1,n0=1對于n>=n0n2<=n3,所以n2=O(n3)

對于給定的f，可有無數(shù)個g與之對應，在算法分析時，應當選擇最小的函數(shù)g作為f的上界.(2)大

表示法(算法運行時間的下限）如果正常數(shù)c和自然數(shù)N0使得當N

N0時,有f(N)cg(N)則稱函數(shù)f(N)在N充分大時有下限,且g(N)是它的一個下限,記為f(N)=(g(N))也稱f(N)的階不低于g(N)的階。第2章算法分析基礎例2-5f(n)=2n+3=

(n),f(n)=10n2+4n+2=