算法分析與設(shè)計第2章

1、 每節(jié)一經(jīng)典計算機科學(xué)是問題驅(qū)動的科學(xué)純數(shù)學(xué)是理論驅(qū)動的科學(xué)算法分析的目的（1）深入準確理解問題本質(zhì)及可能的求解技術(shù)（2）探討某種具體算法適用于解決哪類問題，或某類問題宜采用哪種算法算法評價指標體系 運行時間 存貯空間 易理解 易編碼 易調(diào)試 易維護第2章 算法分析基礎(chǔ)時間復(fù)雜度估算 算法執(zhí)行時間=（原操作的執(zhí)行次數(shù)原操作的執(zhí)行時間） 語句頻度：指語句重復(fù)執(zhí)行的次數(shù) 一個算法中所有語句的頻度之和構(gòu)成了該算法的運行時間。例1. for(j=1;j=n;j=j+1) for(k=1;k=n;k=k+1) x=x+1語句 x=x+1,k=n,k=k+1的頻度分別均是n2; 總頻度是：3n2語句 j=

2、1的頻度是1語句 k=1,j=n,j=j+1的頻度均為n；總頻度：3n因此，算法運行時間(語句總頻度)為：3n2 +3n+1第2章 算法分析基礎(chǔ)時間復(fù)雜度估算 如果算法比較復(fù)雜，通常選擇一種對于所研究的問題來說最基本的原操作，以它在算法中重復(fù)執(zhí)行的次數(shù)作為算法運行時間的衡量標準。 這個原操作多數(shù)情況下是最深層循環(huán)體內(nèi)語句中的操作。例2.2. 矩陣乘法算法：for(i=1;i=n;i=i+1) for(j=1;j=n;j=j+1) ci,j=0； for(k=1;k=n;k=k+1) ci,j=ci,j+ai,k*bk,j; 第2講 算法分析基礎(chǔ)該算法最重要的基本操作是語句 ci,j=ci,j+

3、ai,k*bk,j由于它在三重循環(huán)之內(nèi)，所以它的頻度是n3. 我們稱該算法的時間復(fù)雜度是O(n3).大O表示法 例2.3 當(dāng)一個算法的運行時間為表達式3n4+n2+1時，由于當(dāng)n足夠大時，表達式的值約等于n4,我們說該表達式與n4的數(shù)量級相等，稱n4為這個算法的漸近時間復(fù)雜度，簡稱算法的時間復(fù)雜度，記作：T(n)=O(n4). 其中，O是Order的首字母，表示數(shù)量級。兩個表達式f(n)與g(n)的數(shù)量級相等定義如下：定義2.1 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，如果存在一個常數(shù)C,使極限則稱f(n)和g(n)是相同數(shù)量級的函數(shù)。第2講 算法分析基礎(chǔ)常用算法時間復(fù)雜度表示形式 O(

4、1): 常數(shù)級，如 3； O(logn): 對數(shù)級，如log3n；O(n): 線性級，如5n; O(nc): 多項式級,如n3; O(cn): 指數(shù)級，如2n ; O(n！): 階乘級,如3n!以上時間復(fù)雜度的大小排列如圖所示。對復(fù)雜算法，可以把它分隔成容易估算的幾個部分，然后再利用O的求和原則得到算法總的時間復(fù)雜度。T(n)=T1(n)+ T2(n)+ Tm(n) =O(max(f1(n), f2(n), fm(n) 第2講 算法分析基礎(chǔ)算法時間復(fù)雜度上、下界復(fù)雜度上、下界是用來估計解決某個問題所需資源（時間、空間）的復(fù)雜程度的界限函數(shù)。注意：算法復(fù)雜度與問題復(fù)雜度的區(qū)別。如果找到解決某問題

5、的算法，算法復(fù)雜度為u(n),則u(n)是問題本身復(fù)雜度的一個上界。如果對解決某個問題的所有算法而言， 算法復(fù)雜度均大于l(n),則l(n)是該問題復(fù)雜度的一個下界。算法所需的時間總量的上界用符號O表示，定義為：定義2.2 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，如果存在兩個正整數(shù)c和n0,對 于所有的nn0,有|f(n)|c|g(n)|,則記作 f(n)=O(g(n)。算法所需的時間總量的下界用符號表示，定義為：定義2.3 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，如果存在兩個正整數(shù)c和n0,對 于所有的nn0,有|f(n)|c|g(n)|,則記作 f(n)=(g(n)。第2講 算

6、法分析基礎(chǔ)小o和表示法定義2.4 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，當(dāng)f(n)=O(g(n)，f(n)=(g(n)）時f(n)和g(n)同階，記作f(n)=(g(n)定義2.5 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，如果對任意0，都存在非負整數(shù)n0,使得當(dāng)nn0時, 有f(n)g(n)）,則稱當(dāng)n充分大時，f(n)比g(n)低階，記作 f(n)=o(g(n).定義2.6 設(shè)f(n)和g(n)是一個關(guān)于正整數(shù)n的函數(shù)，如果對任意0，都存在非負整數(shù)n0,使得當(dāng)nn0時, 有g(shù)(n) (f(n)）,則稱當(dāng)n充分大時，f(n)比g(n)高階，記作 f(n)= (g(n). 可以看出

7、，o對O, 對第2講 算法分析基礎(chǔ)最好情況下的時間復(fù)雜性 指時間復(fù)雜度下界，記作Tmax最壞情況下的時間復(fù)雜性 指時間復(fù)雜度上界，記作Tmin平均情況下的時間復(fù)雜性 指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。 記作Tavg. 我們關(guān)注的重點是： Tmin第2講 算法分析基礎(chǔ)算法空間復(fù)雜性 （1）輸入數(shù)據(jù)所占空間：與問題本身有關(guān)，與算法無關(guān)。 （2）算法（程序）本身所占空間：大小相對固定。 （3）輔助變量所占空間：不同算法空間數(shù)量可能不同。算法空間復(fù)雜性：指算法在執(zhí)行過程中所占輔助存貯空間的大小，記為S(n)， S(n)=O(f(n)表示隨著問題規(guī)模n的增大，算法運行所需要

8、的存貯空間數(shù)量的增長率與f(n)的增長率相同。第2講 算法分析基礎(chǔ)問題分類（不是算法分類） P問題：對一個問題p而言，存在多項式時間算法能夠解決該問題，那么稱問題p為P問題。也稱為易求解問題。 P類問題：所有的P問題的集合。 P類問題是易解問題，非P類問題是難解問題。 NP問題：能夠在多項式時間內(nèi)驗證一個解是否正確的問題，稱為NP問題。也稱為易驗證問題。 NP類問題：所有的NP問題的集合。 NP完全類問題：NP類問題中復(fù)雜性最高的一個子類，稱為NP完全類問題。第2講 算法分析基礎(chǔ)P類問題、NP類問題、NP完全類問題之間的關(guān)系 重要結(jié)論： 定理2.1 任取NP類中的一個問題np,再任取NP完全類

9、中的一個問題npc,則一定存在一個具有多項式時間復(fù)雜性的算法，可以把NP問題np轉(zhuǎn)變成NPC問題npc. 求解問題 判定問題定理1表明，只要能夠證明NP完全類中有一個問題是屬于P類的，也就證明了NP類中的所有問題都是P類的，即P=NP. P=NP ？不幸的是，這是一個世界一級難題！第2講 算法分析基礎(chǔ)P類問題NP類問題NP完全類問題？存在多項式算法：把一個NP問題轉(zhuǎn)化為NP完全問題NP完全類問題是最難解的一類問題 可以使用的方法： 近似算法:多項式近似算法，求近似解來代替最優(yōu)解。 啟發(fā)式算法：利用啟發(fā)式策略，如螞蟻算法求最優(yōu)解或近似解。方法有效，但很難說清它的道理。 概率分析方法,動態(tài)規(guī)劃方法

10、，分支限界方法等.第2講 算法分析基礎(chǔ)算法分析實例 （1）非遞歸算法分析 1）依賴于問題規(guī)模的時間復(fù)雜度 T(n)=O(1): 如果算法的執(zhí)行時間不是隨問題規(guī)模n的增加而增長，即使算法中有成千上萬條語句，其執(zhí)行時間仍然是一個較大的常數(shù)，即f(n)=C,則稱此類算法的時間復(fù)雜度是O(1）。 例2.1 temp=i i=j j=temp 則上述三個算法的時間復(fù)雜度均為T(n)=O(1)第2講 算法分析基礎(chǔ)i=1J=2K=3H=4S=i+j+k+hi=1J=2K=3H=4S=i*j+k*h算法分析實例例2.2 循環(huán)次數(shù)直接依賴問題規(guī)模n以上算法中頻度最大的語句是: y=y+1,其頻度f(n)=n2,

11、所以，該算法的時間復(fù)雜度是：T(n)=O(n2)例2.3 循環(huán)次數(shù)間接依賴問題規(guī)模n以上算法中頻度最大的語句是: x=x+1,其頻度需要從內(nèi)循環(huán)向外循環(huán)逐層計算： 第2講 算法分析基礎(chǔ)x=0;y=0;For(k=1;k=n;k=k+1) x=x+1;For(i=1;i=n;i=i+1) For(j=1;j=n;j=j+1) y=y+1;x=1;Input(n);For(i=1;i=n;i=i+1) For(j=1;j=i;j=j+1) For(k=1;k=j;k=k+1) x=x+1; 則f(n)=n3/6, 所以T(n)=O(n3). 2）依賴于輸入實例的初始狀態(tài) 例2.4 在數(shù)組a0.n-

12、1中查找給定值k的算法為： 12, 23, 34, 80, 21, 38, 40, 2 a0 a1 a7把循環(huán)語句while中的比較操作aik作為主要操作。這是因為比較操作比i=i+1更復(fù)雜。算法的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例數(shù)組a0.n-1的元素取值及k值有關(guān)： 第2講 算法分析基礎(chǔ)i=n-1;While (i=0 and aik) i=i+1;Return i 若數(shù)組a中沒有等于k值的元素，則語句2的頻度f(n)=n,這是最壞情形。 若數(shù)組a的最后一個元素等于k，則語句2的頻度f(n)=1,這是最好情形。 一般情形下需要求平均復(fù)雜度。 假設(shè)在n個元素中每個元素被查找的概率P是相同

13、的（1/n），則所有元素被查找的總次數(shù)(算法的平均復(fù)雜度)為： （2）遞歸算法分析 1)遞歸模型 例2.5 求階乘 n!=? 先看一個簡單實例： 5！=5*4！=5*4*3！=5*4*3*2！=5*4*3*2*1！=120, 這里，0！=1！=1, 歸納階乘公式：n!=n*(n-1)!=n*(n-1)*(n-2)!=第2講 算法分析基礎(chǔ) 因此，求階乘 n!算法如下： fact(int n) (1) if (n=0 or n=1) (2) return (1); (3) else (4) return(n*fact(n-1); (5) 遞歸算法需要數(shù)據(jù)結(jié)構(gòu)“棧(stack)”來存貯中間結(jié)果，再回

14、溯求解。第2講 算法分析基礎(chǔ)當(dāng)n=5時，算法計算5！過程如下：執(zhí)行語句1：轉(zhuǎn)語句(3)-(4)， 結(jié)果得到：5*fact(4);再調(diào)用函數(shù)fact(4):執(zhí)行語句1：轉(zhuǎn)語句(3)-(4),結(jié)果得到：5*4*fact(3);再調(diào)用函數(shù)fact(3):執(zhí)行語句1：轉(zhuǎn)語句(3)-(4),結(jié)果得到：5*4*3*fact(2);再調(diào)用函數(shù)fact(2):執(zhí)行語句1：轉(zhuǎn)語句(3)-(4),結(jié)果得到：5*4*3*2*fact(1);此時，由于fact(1)=1,即1！=0，結(jié)果得到： 5*4*3*2*1最后把上述式子累乘，得到5！=120求階乘 n!算法復(fù)雜度分析：例2.6：假設(shè)n=4 4!=4*3!.T(

15、4)=T(3)+O(1) 3!=3*2!.T(3)=T(2)+O(1) 2!=2*1!.T(2)=T(1)+O(1) 1!=1 T(1)=O(1)因此，T(4)=O(1)+O(1)+O(1)+O(1)推廣：n!=n*(n-1)! T(n)=T(n-1)+O(1) =n*(n-1)*(n-2)! =T(n-2)+O(1)+O(1) =n*(n-1)*(n-2)*1 =O(1)+O(1)+O(1) (共n項）因此，T(n)=n*O(1)=O(n).迭代法第2講 算法分析基礎(chǔ)歸納：遞歸算法復(fù)雜度分析方法之一迭代法基本思想：先將遞歸算法簡化為對應(yīng)的遞歸方程，然后通過反復(fù)迭代，將遞歸方程右端變成為一個級數(shù)，最后求級數(shù)的和，再估計和的漸近復(fù)雜度。或者，不求級數(shù)的和，直接估計級數(shù)的漸近復(fù)雜度。遞歸方程：利用遞歸算法中的關(guān)系寫出遞歸方程，然后迭代地展開右端，變成為一個非遞歸的求和式子，然后對和式估計，從而對方程解進行估計。T(n)=2T(n/2)+O(n)=2(T(n/4)+O(n/2)+O(n)=2T(n/4)+O(n)+O(n)=k*O(n)=O(k*n)第2講 算法分析基礎(chǔ)如何提高算法質(zhì)量（1）設(shè)計算法時，優(yōu)先考慮算法的正確性、可靠性、穩(wěn)健性、可讀性；（2）其次考慮算法時空效率。 1）提高全局