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

1、1第一章第一章 算法概述算法概述第二章第二章 遞歸與分治策略遞歸與分治策略第三章第三章 動態(tài)規(guī)劃動態(tài)規(guī)劃第四章第四章 貪心算法貪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 隨機(jī)化算法隨機(jī)化算法算法設(shè)計與分析算法設(shè)計與分析 目錄目錄21.11.1 算法與程序算法與程序1.21.2 算法復(fù)雜度分析算法復(fù)雜度分析1.31.3 NPNP完全性理論完全性理論算法設(shè)計與分析算法設(shè)計與分析 第一章第一章 目錄目錄3“算法是任何定義好的計算程式，它取某些值算法是任何定義好的計算程式，它取某些值或值的集合作為輸入，并產(chǎn)生某些值或值的集或值的集合作為輸入，并產(chǎn)生某些值或值的集合

2、作為輸出。合作為輸出。”1.11.1 算法與程序算法與程序 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述算法算法: : 是將問題的輸入轉(zhuǎn)化為輸出的一系列是將問題的輸入轉(zhuǎn)化為輸出的一系列 計算或操作步驟計算或操作步驟. .1 1 算法定義及其特性算法定義及其特性 4 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述例：求兩個不全為例：求兩個不全為0的非負(fù)整數(shù)的非負(fù)整數(shù)m, n的最大公約數(shù)的最大公約數(shù) gcd(m,n)的的歐幾里德算法描述歐幾里德算法描述: 1.如果如果n=0,返回返回m的值作為結(jié)果，過程結(jié)束；的值作為結(jié)果，過程結(jié)束； 否則，進(jìn)入第二步；否則，進(jìn)入第

3、二步； 2.用用n去除去除m，將余數(shù)賦給，將余數(shù)賦給 r; 3.將將n的值賦給的值賦給m，將，將r的值賦給的值賦給n,返回第一步。返回第一步。算法描述舉例5計算機(jī)算法與人工算法計算機(jī)算法與人工算法 算法概述算法概述例如例如 求定積分求定積分: : s= 人工處理步驟為人工處理步驟為找出找出f(x)的源函數(shù)的源函數(shù)F(x)利用牛利用牛-萊公式萊公式:s=F(b)-F(a)dxxfba)(算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述有些問題沒有計算機(jī)算法有些問題沒有計算機(jī)算法. .有些問題計算機(jī)算法與人工算法不同有些問題計算機(jī)算法與人工算法不同. .計算機(jī)算法：計算定積分采用數(shù)值積分的方計算機(jī)算

4、法：計算定積分采用數(shù)值積分的方法法, ,得到一個近似解得到一個近似解. . 6算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述算法的定義因看待的角度不同而不同算法的定義因看待的角度不同而不同哲學(xué)家：算法是解決一個問題的抽象行為哲學(xué)家：算法是解決一個問題的抽象行為序列。序列。碼農(nóng)：算法是一個計算過程，它接受一些碼農(nóng)：算法是一個計算過程，它接受一些輸入，并產(chǎn)生某些輸出。輸入，并產(chǎn)生某些輸出。高大上：算法是解決一個精確定義的計算高大上：算法是解決一個精確定義的計算問題的工具。問題的工具。核心：算法是解決問題的辦法和法則，算法必核心：算法是解決問題的辦法和法則，算法必須能夠讓人一步一步照著執(zhí)行。須能夠讓

5、人一步一步照著執(zhí)行。7算法的特征算法的特征1.1.有窮性有窮性 一個算法須在執(zhí)行有限個運(yùn)算步后終止一個算法須在執(zhí)行有限個運(yùn)算步后終止, ,每一步必須每一步必須在有限時間內(nèi)完成在有限時間內(nèi)完成. .實(shí)際應(yīng)用中實(shí)際應(yīng)用中, ,算法的有窮性應(yīng)該包括算法的有窮性應(yīng)該包括執(zhí)行時間的合理性執(zhí)行時間的合理性. . 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述 程序程序是算法的程序設(shè)計語言的具體實(shí)現(xiàn)是算法的程序設(shè)計語言的具體實(shí)現(xiàn). .可不滿足性質(zhì)可不滿足性質(zhì)1.1. 一個算法面向一個問題，而不是僅僅求解一個問題的實(shí)例一個算法面向一個問題，而不是僅僅求解一個問題的實(shí)例 操作系統(tǒng)程序：是一個在無

6、限循環(huán)中執(zhí)操作系統(tǒng)程序：是一個在無限循環(huán)中執(zhí)行的程序，而不是一個算法。行的程序，而不是一個算法。8 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述例如例如 計算分段函數(shù)計算分段函數(shù) f(x) =算法描述：輸入變量算法描述：輸入變量x, 1 x100 0 x10若若x大于大于100的數(shù)，輸出的數(shù)，輸出1;若若x小于小于10的數(shù)，輸出的數(shù)，輸出0.輸入輸入10=x 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述5.5.輸出輸出 算法產(chǎn)生至少有一個輸出項算法產(chǎn)生至少有一個輸出項10 1. 1.問題的陳述問題的陳述 理解問題，并用科學(xué)規(guī)范的語言把所求解問題進(jìn)行準(zhǔn)理解問題

7、，并用科學(xué)規(guī)范的語言把所求解問題進(jìn)行準(zhǔn)確的描述確的描述, ,包括所有已知條件和輸出要求包括所有已知條件和輸出要求. . 2. 2.建立數(shù)學(xué)模型建立數(shù)學(xué)模型 通過對問題分析通過對問題分析, ,找出其中所有操作對象以及對象之找出其中所有操作對象以及對象之間的關(guān)系間的關(guān)系, ,并用數(shù)學(xué)語言加以描述并用數(shù)學(xué)語言加以描述. . 對非數(shù)值型解法來說對非數(shù)值型解法來說, ,數(shù)學(xué)模型通常是鏈表數(shù)學(xué)模型通常是鏈表, ,樹樹, ,圖圖, ,集合等數(shù)據(jù)結(jié)構(gòu)集合等數(shù)據(jù)結(jié)構(gòu). 2. 2.算法設(shè)計過程算法設(shè)計過程( (程序設(shè)計過程程序設(shè)計過程) )算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述113.3.算法設(shè)計算法設(shè)計

8、 根據(jù)數(shù)據(jù)模型根據(jù)數(shù)據(jù)模型, , 給出求解問題的一系列步驟給出求解問題的一系列步驟, ,且這些步驟可通過計算機(jī)的各種操作來實(shí)現(xiàn)且這些步驟可通過計算機(jī)的各種操作來實(shí)現(xiàn).4.4.算法的正確性證明算法的正確性證明 算法的正確性算法的正確性: :對一切合法的輸入對一切合法的輸入, ,算法均能算法均能在有限次的計算后產(chǎn)生正確的輸出在有限次的計算后產(chǎn)生正確的輸出. . 算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述 5. 5.算法的程序?qū)崿F(xiàn)算法的程序?qū)崿F(xiàn) 將一個算法描述正確地編寫成機(jī)器語言程序?qū)⒁粋€算法描述正確地編寫成機(jī)器語言程序. .12問題的求解過程問題的求解過程 算法概述算法概述6.6.算法分析算法

9、分析 對執(zhí)行該算法所消耗的計算機(jī)對執(zhí)行該算法所消耗的計算機(jī)資源資源進(jìn)行估進(jìn)行估算算, ,對數(shù)值型算法還需分析算法的對數(shù)值型算法還需分析算法的穩(wěn)定性穩(wěn)定性和和誤差誤差等等問題問題. .計算機(jī)資源中最重要的是計算機(jī)資源中最重要的是時間和空間時間和空間資源資源, ,執(zhí)行一個算法程序需要的時間和占用的內(nèi)存空執(zhí)行一個算法程序需要的時間和占用的內(nèi)存空間分別稱為間分別稱為算法的時間復(fù)雜度和空間復(fù)雜性算法的時間復(fù)雜度和空間復(fù)雜性 . .算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述13 描述算法的方式一般有三種描述算法的方式一般有三種:自然語言自然語言,流程圖流程圖,偽代碼語言。偽代碼語言。 偽代碼描述介于自

10、然語言與程序偽代碼描述介于自然語言與程序設(shè)計語言之間。設(shè)計語言之間。3. 3.算法的描述算法的描述 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述144. 算法結(jié)構(gòu)算法結(jié)構(gòu) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述任何算法都可由順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)這任何算法都可由順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)這三塊三塊“積木積木”通過組合和嵌套表達(dá)出來，遵循這種方通過組合和嵌套表達(dá)出來，遵循這種方法的程序設(shè)計，即為結(jié)構(gòu)化程序設(shè)計法的程序設(shè)計，即為結(jié)構(gòu)化程序設(shè)計。15數(shù)值型算法數(shù)值型算法: :算法中的基本運(yùn)算為算術(shù)運(yùn)算算法中的基本運(yùn)算為算術(shù)運(yùn)算. .非數(shù)值型算法非數(shù)值

11、型算法: :算法中的基本運(yùn)算為邏輯運(yùn)算算法中的基本運(yùn)算為邏輯運(yùn)算. .串行算法串行算法: :串行計算機(jī)上執(zhí)行的算法串行計算機(jī)上執(zhí)行的算法. .并行算法并行算法: :并行計算機(jī)上執(zhí)行的算法并行計算機(jī)上執(zhí)行的算法. .從處理方式上從處理方式上5. 算法分類算法分類從解法上從解法上 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述本課程主要介紹非數(shù)值型的串行算法本課程主要介紹非數(shù)值型的串行算法. .16l算法的復(fù)雜性算法的復(fù)雜性:指執(zhí)行算法所消耗或占用的資指執(zhí)行算法所消耗或占用的資源的數(shù)量源的數(shù)量l一個算法所需資源越多一個算法所需資源越多, ,我們就說它的復(fù)雜性我們就說它的復(fù)雜性越高越

12、高, ,反之則低反之則低. . 算法復(fù)雜性分析算法復(fù)雜性分析 時間復(fù)雜性時間復(fù)雜性空間復(fù)雜性空間復(fù)雜性算法的復(fù)雜性算法的復(fù)雜性1.2 算法的復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述17考慮考慮空間復(fù)雜性空間復(fù)雜性的理由的理由在多用戶系統(tǒng)中運(yùn)行時，需指明分給該程序在多用戶系統(tǒng)中運(yùn)行時，需指明分給該程序的內(nèi)存大??；的內(nèi)存大??；需預(yù)先知道計算機(jī)系統(tǒng)是否有足夠的內(nèi)存來需預(yù)先知道計算機(jī)系統(tǒng)是否有足夠的內(nèi)存來運(yùn)行該程序；運(yùn)行該程序；一個問題可能有若干個不同的內(nèi)存解決方案一個問題可能有若干個不同的內(nèi)存解決方案，從中擇取，從中擇??；用空間復(fù)雜性估計一個程序可能解決的問題用空間

13、復(fù)雜性估計一個程序可能解決的問題的最大規(guī)模的最大規(guī)模。算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述18 算法復(fù)雜性分析算法復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述考慮考慮時間復(fù)雜性時間復(fù)雜性的理由的理由某些計算機(jī)用戶需要提供程序運(yùn)行時間的上限某些計算機(jī)用戶需要提供程序運(yùn)行時間的上限（用戶可接受的）；（用戶可接受的）；所開發(fā)的程序需要提供一個滿意的實(shí)時反應(yīng)。所開發(fā)的程序需要提供一個滿意的實(shí)時反應(yīng)。19 算法復(fù)雜性分析算法復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述算法分析:(漸進(jìn)算法分析):對執(zhí)行算法所消對執(zhí)行算法所消耗或占用的資

14、源進(jìn)行估算耗或占用的資源進(jìn)行估算, ,給出算法耗費(fèi)的給出算法耗費(fèi)的限界函數(shù)限界函數(shù). .需解決兩個問題需解決兩個問題: : 如何度量復(fù)雜性如何度量復(fù)雜性? ? 如何分析復(fù)雜性如何分析復(fù)雜性? ?20 算法的復(fù)雜性算法的復(fù)雜性: : 算法運(yùn)行所需的時間和空間的數(shù)量算法運(yùn)行所需的時間和空間的數(shù)量. 它與算法求解問題的問題的規(guī)模規(guī)模n n,算法的輸入數(shù)輸入數(shù)I 及算法本身算法本身有關(guān). 例如例如 在數(shù)組中找分量在數(shù)組中找分量c, n:數(shù)組中分量的個數(shù)數(shù)組中分量的個數(shù) 兩個矩陣相乘兩個矩陣相乘, n:矩陣的維數(shù)矩陣的維數(shù) 表中排序表中排序, n:數(shù)組中分量的個數(shù)數(shù)組中分量的個數(shù) 遍歷一棵樹遍歷一棵樹,

15、 n:樹中節(jié)點(diǎn)數(shù)樹中節(jié)點(diǎn)數(shù)1.復(fù)雜性的計量 算法復(fù)雜性分析算法復(fù)雜性分析問題的規(guī)模問題的規(guī)模n: :指問題的輸入數(shù)據(jù)或初始數(shù)據(jù)的量指問題的輸入數(shù)據(jù)或初始數(shù)據(jù)的量. 在不同的問題中在不同的問題中, n有不同的表現(xiàn)形式：有不同的表現(xiàn)形式： 復(fù)雜性的計量復(fù)雜性的計量 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述21算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述 算法效率與計算機(jī)的性能有關(guān)，但此因素對所有算法算法效率與計算機(jī)的性能有關(guān)，但此因素對所有算法的影響相同。的影響相同。5*5的矩陣相乘與的矩陣相乘與10*10矩陣的矩陣相乘所需時間矩陣的矩陣相乘所需時間空間均不相同空間均不相同

16、； 找找c在數(shù)組在數(shù)組A中的位置中的位置,c=A(1),與與c=A(100),所需時間所需時間顯然也顯然也不同不同 順序查找還是折半查找速度也是不一樣的順序查找還是折半查找速度也是不一樣的. 算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述22令令 n: n: 問題規(guī)模問題規(guī)模 I: I: 輸入數(shù)據(jù)輸入數(shù)據(jù) A: A: 算法本身算法本身 C: C: 算法的復(fù)算法的復(fù)雜性雜性, , 則則 C=f ( n, I, A )C=f ( n, I, A ) 將時間復(fù)雜性和空間復(fù)雜性分別考慮將時間復(fù)雜性和空間復(fù)雜性分別考慮, ,并用并用T T和和S S表示表示. . 則有則有: : T=T(n, I, A)

17、 S=S (n, I, A) T=T(n, I, A) S=S (n, I, A)將算法將算法A A 隱含在函數(shù)名中隱含在函數(shù)名中, ,不同函數(shù)名代表不同算法不同函數(shù)名代表不同算法, , 則簡化為則簡化為 T=T( n, I ) S=S( n, I ) T=T( n, I ) S=S( n, I ) 算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述23k1I)(n,etiii設(shè)一臺抽象計算機(jī)提供的元運(yùn)算有設(shè)一臺抽象計算機(jī)提供的元運(yùn)算有k種種, 記作記作 O1 ,Ok ;設(shè)這些元運(yùn)算每執(zhí)行一次所需時間分別為設(shè)這些元運(yùn)算每執(zhí)行一次所需時間分別為 t1 , tk ;設(shè)在算法設(shè)在算法A中用到中用到Oi的

18、次數(shù)為的次數(shù)為 ei , i =1,k, 則則 ei = ei ( n, I ) T=T(n,I)= T=T(n,I)= 當(dāng)問題的規(guī)模當(dāng)問題的規(guī)模 n和算法確定后和算法確定后,T是輸入變元是輸入變元 i 的函數(shù)的函數(shù).僅以時間復(fù)雜性為例將復(fù)雜性函數(shù)具體化僅以時間復(fù)雜性為例將復(fù)雜性函數(shù)具體化. . 算法復(fù)雜性分析算法復(fù)雜性分析 復(fù)雜性的計量復(fù)雜性的計量 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述24說明：說明：我們不可能對規(guī)模為我們不可能對規(guī)模為n的每一種合法輸?shù)拿恳环N合法輸入入I都計算都計算ei次，次，因為輸入可能是無窮集合因為輸入可能是無窮集合,我們只能對規(guī)模為我們只能對

19、規(guī)模為n的問題的的問題的某類具有代表某類具有代表性性的合法輸入統(tǒng)計相應(yīng)的的合法輸入統(tǒng)計相應(yīng)的ei. . 算法復(fù)雜性分析算法復(fù)雜性分析 復(fù)雜性的計量復(fù)雜性的計量 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述25最好情況最好情況: :T Tminmin(n) = T(n,I)= (n) = T(n,I)= = = = =kiiiInet1, )(kiiiInet1, )(kiiiInet1, )()(InT,kiiiInet1, )(nDImaxkiiiInet1*,)(NDIIPI)T(n,)()(*,InTnDIIP)(nDImin最壞情況最壞情況:T:Tmaxmax(n)

20、= T(n,I) =(n) = T(n,I) = = = = =平均情況平均情況:T:Tavgavg(n) = = (n) = = 其中 Dn :規(guī)模為n的所有合法輸入的集合D Dn n中達(dá)到中達(dá)到T Tmin min (n)(n)的一個輸入的一個輸入. .D Dn n中達(dá)到中達(dá)到Tmax (n)Tmax (n)的一個輸入的一個輸入. .P(I): P(I): 出現(xiàn)輸入為出現(xiàn)輸入為I I的概率的概率nDImaxnDImin 算法復(fù)雜性分析算法復(fù)雜性分析 復(fù)雜性的計量復(fù)雜性的計量 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述26 算法復(fù)雜性分析算法復(fù)雜性分析漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算

21、法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述當(dāng)一個問題的輸入規(guī)模很大時,算法的結(jié)構(gòu)又很復(fù)雜時,采用前面介紹的精確分析就顯得過于繁瑣,為降低算法分析的代價,同時又保證估算的精確度,引入一個簡化的計算模型來評估算法的開銷.稱為漸進(jìn)分析稱為漸進(jìn)分析.漸進(jìn)分析是對問題的規(guī)模充分大的算法問題的規(guī)模充分大的算法開銷的估算。1. 1. T(n)的漸進(jìn)復(fù)雜性的漸進(jìn)復(fù)雜性( (漸進(jìn)表達(dá)式漸進(jìn)表達(dá)式) :) : (T(n) - ) / T(n)0，n 時時2.2.漸進(jìn)階漸進(jìn)階: : O, O, , , )(nT T)(nT T272.復(fù)雜性的漸進(jìn)性態(tài)如果存在一個函數(shù)如果存在一個函數(shù) 使得當(dāng)使得當(dāng)n

22、 ,有有 (T(n) - ) / T(n)0稱稱 是是T(n)當(dāng)當(dāng) n 時的時的漸進(jìn)性態(tài)漸進(jìn)性態(tài) 或或 漸進(jìn)復(fù)雜性漸進(jìn)復(fù)雜性 算法復(fù)雜性分析算法復(fù)雜性分析1.1.漸進(jìn)性態(tài)漸進(jìn)性態(tài))(nT T)(nT T)(nT T漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述設(shè)設(shè)T(n)為算法為算法A的時間復(fù)雜性函數(shù)的時間復(fù)雜性函數(shù)(輸入值固定輸入值固定. 如如Tmax, Tmin, Tavg ), 則它是則它是n 的單增函數(shù)。的單增函數(shù)。28當(dāng)當(dāng)n充分大時用充分大時用 代替代替T(n)作為算法復(fù)雜性的度量作為算法復(fù)雜性的度量,以以簡化分析簡化分析 例如例如 T(n)=3n2

23、+4nlogn+7, 則則 可以是可以是3n2 算法復(fù)雜性分析算法復(fù)雜性分析漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述在數(shù)學(xué)上在數(shù)學(xué)上, ,T(T(n) )與與 有相同的最高階項有相同的最高階項. .可取可取 為為略去略去T(T(n) )的的低階項后剩余的主項低階項后剩余的主項. .)(T n 比較兩個算法時，如果他們的階不同，就可分出效率高比較兩個算法時，如果他們的階不同，就可分出效率高低。故此時只需關(guān)心低。故此時只需關(guān)心 最高限的階即可。可忽略最高最高限的階即可?？珊雎宰罡唔椣禂?shù)或低階項。項系數(shù)或低階項。)(nT T)(nT T)(nT T)(T n

24、292.2.漸進(jìn)性態(tài)的階例如例如3n=O(n),n+1024=O(n),n2=O(n3) ?n3=O(n2) ?2n2+11n-10=O(n2)若若 正常數(shù)正常數(shù)c c和和 自然數(shù)自然數(shù)NN0 0 使得當(dāng)使得當(dāng) n n NN0 0 時時, ,有有f( f(n n) ) cg cg ( (n n) ) 則稱函數(shù)則稱函數(shù) f( f(n n) )在在n n充分大時有充分大時有上界上界, , 且且 g g( (n n) )是它一個上界是它一個上界. .記為記為 f( f(n n) =O() =O(g g ( (n n) , ) , 也稱也稱 f( f(n n) ) 的的階階不高于不高于g g ( (n

25、 n) ) 的的階階. . 設(shè)設(shè)f(n)和和 g (n) 是定義在正整數(shù)集上的正函數(shù)是定義在正整數(shù)集上的正函數(shù),(1)大大O O表示法表示法 (算法運(yùn)行時間的上限 ) 算法復(fù)雜性分析算法復(fù)雜性分析漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述30 算法復(fù)雜性分析算法復(fù)雜性分析漸進(jìn)性態(tài)漸進(jìn)性態(tài)三點(diǎn)注意三點(diǎn)注意:1 用來作比較的函數(shù)用來作比較的函數(shù) g(n)應(yīng)該盡量接近應(yīng)該盡量接近 f(n). 例如 3n+2=O(n2) 松散的界限；3n+2=O(n) 較好的界限2 不要產(chǎn)生錯誤界限。不要產(chǎn)生錯誤界限。 例如 n2+100n+6，當(dāng) n3 時，n2+100n+6

26、算法復(fù)雜性分析算法復(fù)雜性分析漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述31 1. O(1. O(f f )+O(g)=O( max( )+O(g)=O( max( f f, g ) ), g ) ) 2. O( 2. O(f f )+O(g)=O( )+O(g)=O(f f+g)+g) 3. O( 3. O(f f )O(g)=O( )O(g)=O(f fg)g) 4. 4. 如果如果 g(n)=O(g(n)=O(f f (n),(n),則則 O(O(f f )+O(g)=O( )+O(g)=O(f f ) ) 5. 5. f f=O( =O( f f )

27、 ) 6. O( c 6. O( c f f (n) )=O( (n) )=O( f f (n) )(n) )漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述運(yùn)算規(guī)則運(yùn)算規(guī)則32證明證明: O(: O(f f )+O(g)=O( max( )+O(g)=O( max( f f, g ) ), g ) )算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述設(shè)設(shè)F(N)=O(f).根據(jù)O的定義,存在正常數(shù)C1和自然數(shù)N1,使得對所有NN1,有F(N)C1f(N).類似G(N)=O(g).根據(jù)O的定義,存在正常數(shù)C2和自然數(shù)N2,使得對所有NN2,有G(N)C2g(N).令

28、令C3 =maxC1 ,C2, N3 =maxN1 ,N2, h(N)=maxf , g,則對所則對所有有NN3, 有有 F(N)C1f(N) C1h(N) C3h(N).類似類似 G(N)C2g(N) C2h(N) C3h(N).O(O(f f )+O(g)= )+O(g)= F(N) + G(N) C3h(N)+C3h(N)=2C3h(N)= O(h)=O( max( O( max( f f, g ) ), g ) )33 例例 估計如下二重循環(huán)的估計如下二重循環(huán)的 T Tmaxmax(n)(n)的階的階. .分析分析: :內(nèi)循環(huán)體只需內(nèi)循環(huán)體只需O O(1)(1)時間時間, ,故故for

29、 i:= 1 to n do for j:=1 to i do s1, s2, s3, s 4 ; s1, s2, s3, s4為單一賦值語句為單一賦值語句ij 1O(1)O()1O(1iij外循環(huán)共需外循環(huán)共需)O(n)2) 1(O()O()O(21n1nniinii內(nèi)循環(huán)共需內(nèi)循環(huán)共需 漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述2. O(2. O(f f )+O(g)=O( )+O(g)=O(f f+g)+g)34(2) (2) 大大 表示法表示法 ( (算法運(yùn)行時間的下限）算法運(yùn)行時間的下限）若若 正常數(shù)正常數(shù)c和和自然數(shù)自然數(shù)N0使得當(dāng)使得當(dāng) n

30、N0 時時,有有f(n) c g(n) 則稱函數(shù)則稱函數(shù)f(n)在在n充分大時有充分大時有下限下限, 且且 g(n)是它的一個下是它的一個下限限,記為記為f(n) = (g (n) ) 也稱也稱f (n)的階不低于的階不低于 g(n)的階的階漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法復(fù)雜性分析算法復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述例例 T(n)=c1n2+c2n , 則則 T(n)= ( (n2), ), 35 f f (n) =(n) = ( (g g(n) )(n) )等價于等價于 f f(n)=O(n)=O(g g (n) ) (n) ) 且且 f f(n)=(n)=

31、 ( (g g (n) (n) ) )稱函數(shù)稱函數(shù)f(n)f(n)與與g g(n) (n) 同階同階. .(3) 3) 表示法表示法例例 T(n)=c1n2+c2n , 則則 T(n)= ( (n2) )算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述36多項式階算法多項式階算法(有效算法): :若算法的最壞情形時間復(fù)雜度若算法的最壞情形時間復(fù)雜度 T(n)=O(n(nk k););指數(shù)階算法指數(shù)階算法: :若算法的最壞情形時間復(fù)雜度若算法的最壞情形時間復(fù)雜度T(n)=(a(an n) ) ,a1. ,a1. 這類算法可認(rèn)為計算上不可行的算法這類算法可認(rèn)為計算上不可行的算法. .漸進(jìn)性態(tài)漸進(jìn)性態(tài)

32、 算法復(fù)雜性分析算法復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述算法復(fù)雜性分類算法復(fù)雜性分類: :最優(yōu)算法最優(yōu)算法: : 時間復(fù)雜性達(dá)到其下界的算法時間復(fù)雜性達(dá)到其下界的算法. .O(1) O(1) O(logn) O(logn) O(n) O(n) O(nlogn) O(nlogn) O(nO(n2 2) ) O(nO(n3 3) )O(2O(2n n) ) O(n!) O(n!) 漸進(jìn)性態(tài)漸進(jìn)性態(tài) 算法復(fù)雜性分析算法復(fù)雜性分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述兩點(diǎn)說明兩點(diǎn)說明: :時間復(fù)雜度并不是表示一個程序解決問題需要花多少時時

33、間復(fù)雜度并不是表示一個程序解決問題需要花多少時間，而是當(dāng)問題規(guī)模擴(kuò)大后，程序需要的間，而是當(dāng)問題規(guī)模擴(kuò)大后，程序需要的時間長度增長時間長度增長得有多快得有多快。3838 算法復(fù)雜性分析算法復(fù)雜性分析 漸進(jìn)分析漸進(jìn)分析 算法概述算法概述算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述1.31.3 NPNP完全性理論完全性理論 確定性算法：設(shè)確定性算法：設(shè)A是求解問題的一個算法是求解問題的一個算法,如果在如果在算法的整個執(zhí)行過程中算法的整個執(zhí)行過程中,每一步只有一個確定的選每一步只有一個確定的選擇擇,并且對于同一輸入實(shí)例運(yùn)行算法并且對于同一輸入實(shí)例運(yùn)行算法,所得的結(jié)果嚴(yán)所得的結(jié)果嚴(yán)格一致格一致.P類

34、問題類問題:對于某個判定問題對于某個判定問題II，對于規(guī)模為對于規(guī)模為n的輸?shù)妮斎耄軌蛟谌?，能夠在O(nk)時間內(nèi)運(yùn)行一個確定性算法求解時間內(nèi)運(yùn)行一個確定性算法求解得到得到y(tǒng)es或或no的答案，其中的答案，其中k為某一確定常數(shù)。為某一確定常數(shù)。僅回答僅回答yes或或no的問題的問題算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述非確定性算法：設(shè)非確定性算法：設(shè)A是求解問題的一個算法是求解問題的一個算法,如果算法以如如果算法以如下猜測并驗證的方式工作下猜測并驗證的方式工作,算法算法A是非確定算法是非確定算法. (1)猜測階段猜測階段:對問題的輸入實(shí)例產(chǎn)程一個任意字符串對問題的輸入實(shí)例產(chǎn)程一個任意

35、字符串y,在算法的每一次執(zhí)行在算法的每一次執(zhí)行y的值可能不同的值可能不同,猜測以一種非確定猜測以一種非確定性的形式工作性的形式工作; (2)驗證階段驗證階段:用一個確定性算法驗證用一個確定性算法驗證: a)檢查在猜測階段產(chǎn)生的串檢查在猜測階段產(chǎn)生的串y是否是合適的形式，如是否是合適的形式，如果不是，算法停止得到果不是，算法停止得到no； b)如果如果y是合適的形式，再驗證它是否是問題的解，是合適的形式，再驗證它是否是問題的解，如果是算法停止得到如果是算法停止得到y(tǒng)es，否則算法停止得到，否則算法停止得到no。算法設(shè)計與分析算法設(shè)計與分析 算法概述算法概述NP類問題類問題:對于某個判定問題對于某個判定問題II，對于規(guī)模為，對于規(guī)模為n的輸入，的輸入，能夠在能夠在O(nk)時間內(nèi)運(yùn)行一個非確定性算法求解得到時間內(nèi)運(yùn)行一個非確定性算法求解得到y(tǒng)es或或no,其中其中k為某一確定常數(shù)，該判定問題為某一確定常數(shù)，該判定問題II是一個是一個NP類類問題。問題。NP完全問題：令完全問題：令I(lǐng)I是個判定問題，如果問題是個判定問題，如果問題II屬于屬于NP類問題，并且對類問題，并且對NP類問題中的每個問題類問題中的每個問題II，都有，都有(規(guī)約規(guī)約) ,則稱判定問題則稱判定問題II是個是個NP完全問題。完全問題。IIIIp輸入轉(zhuǎn)換輸入轉(zhuǎn)換IO輸出轉(zhuǎn)換輸出轉(zhuǎn)換OI算法算法A問題問題II問題問題