算法效率分析

算法效率分析算法是一系列解決問題的明確指令，對于一定符合規(guī)范的輸入，能夠在有限時間內(nèi)獲得要求的輸出。從實際問題的提出到設(shè)計合適的算法再到正確性的分析以及算法效率的分析，最后為算法編寫代碼，一步步得到問題的解決方案。間迎輸入X"ccmptiM">廚出圖1.算法的概念圖2.算法設(shè)計分析過程對算法效率的分析，需要指出有兩種算法效率：時間效率和空間效率，分指算法運行速度和需要的額外空間。由于技術(shù)革新，對于大多數(shù)問題，速度上效率的提高遠大于空間上的提高。在研究算法效率上提出一般性框架。定義1：如果存在正常數(shù)c和氣使得當N5。時T(N)<cf(N)，則記為T(N)=0(f(N))。定義2:如果存在正常數(shù)c和n。使得當N5。時T(N)>cg(N)，則記為T(N)=。(g(N))。定義3：T(N)=&(h(N))當且僅當T(N)=0(h(N))且T(N)=Q(h(N))。定義4：如果T(N)=0(p(N))且T(N)^0(p(N))，則T(N)=o(p(N))。定義的目的實在函數(shù)之間建立相對的級別?？芍庇^的理解為T(N)增長率小于等于f（N）,T（N）增長率大于等于g（N）,T（N）增長率等于h（N）,T（N）增長率小于p（N）。法則1：如果T(N)=0(f(N))且T(N)=0(g(N))，那么12T(N)+T(N)=max(0(f(N)),0(g(N)))T1(N)xT(N)=0(f(N)xg(N))法則2：如果T(N)是k次多項式，則T(N)=0(Nk)法則3：對任意常數(shù)k，logkN=0(N)下面以最大子序列和問題的四種解決方法來分析算法的效率問題。最大子序列和：給定整數(shù)今氣，...An（可能含負數(shù)），求兄Ak最大值（若所有整數(shù)為k=1負，則最大子序列和為0）算法1234時間O(N3)O(N2)O(NlogN)O(N)輸入大小/mN=100.001030.000450.000660.00034N=1000.470150.011120.004860.00063N=1000448.771.12330.058430.00333N=10000NA111.130.686310.03042N=100000NANA8.01130.29832%上0~40~'~~SO~~9Ci~~100各種計算最大子序列和的算法（橫坐標為N,縱坐標為毫秒）圖】，口A\e2.04N1)ffW)2(X)0】，口A\e2.04N1)ffW)2(X)0JOOC4000500<J60007CKW預(yù)KJO9000lOOOU3.Ct⑶心i方法一、窮舉嘗試所有可能，含有3重for循環(huán)。第一循環(huán)大小為N,第二循環(huán)大小為N-i，第三循環(huán)大小為j-i+1?？紤]最差時間效率，第二循環(huán)第三循環(huán)大小均為N。總數(shù)為O(N3)。可精確分析，第三循環(huán)時間必坡-1j1i=0j=ik=iintMaxSubsequenceSum(constintA[],intN){intThisSum,MaxSum,i,j,k;MaxSum=0;for(i=0;i<N;i++)for(j=i;j<N;j++){ThisSum=0;for(k=i;k<=j;k++)ThisSum+=A[k];if(ThisSum>MaxSum)云Y如1=云云(j-i+1)i=0j=ik=ii=0j=i=Y1(N-i+1)(N-i)i=0=6(N3+3N2+2N)

方法二、在方法一的基礎(chǔ)上去掉三重循環(huán)，復(fù)雜度降為O(N2)方法三、使用一種遞歸的方法，使復(fù)雜度降為O(NlogN)。當問題無法找到O(N)復(fù)雜度的線性解法前，該方法很好的體現(xiàn)遞歸的強力。方法使用“分治”策略。將問題“分割”成兩個大致相等的子問題，再將兩個子問題的解合并，再做少量工作使問題解決。假設(shè)測試序列:前半部后半部4-35-2-126-2Q前半部最大子序列和為6(A1+A2+A3)，后半部最大子序列和為8(A6+A7)@前半部包含最后元素最大和為4(A+A+A+A)，后半部第一元素最大和1234為7(A5+A6+A)Q兩部分最大和11(A+A+A+A+A+A+A)1234567算法3比前兩種需要更多代碼量，但在運行時間上，特別是大數(shù)據(jù)量的運算時間，會比前兩種方法節(jié)省更多時間。方法四、極為簡潔而且更加的有效。打破了第二循環(huán)和第三循環(huán)，使運行時間變?yōu)榫€性。intMaxSubsequenceSum(constintA[],intN){intThisSum,MaxSum,j;MaxSum=ThisSum=0;for(j=0;j<N;j++){ThisSum+=A[j];if(ThisSum>MaxSum)M