1、1 主講教師：孫成敏主講教師：孫成敏 2015年年3月月 - 2015年年6月月計算機算法計算機算法設計與分析設計與分析2p類別：專業(yè)必修課類別：專業(yè)必修課p學分：學分：3學分學分p理論學時：理論學時：48p習題課學時：習題課學時：8p開課周數(shù)：開課周數(shù)：1-14周周345計算機算法設計與分析計算機算法設計與分析 王曉東王曉東 電子工業(yè)電子工業(yè)計算機算法設計與分析計算機算法設計與分析 蘇德富蘇德富 電子工業(yè)電子工業(yè)6p這門課程和其他課程的區(qū)別是什么這門課程和其他課程的區(qū)別是什么?n從這門課程上我能學到哪些東西是在別的課程從這門課程上我能學到哪些東西是在別的課程上學不到的。上學不到的。p這門課程

2、的研究范疇是什么這門課程的研究范疇是什么?n這門課程的知識可以用來解決什么類型的問題，這門課程的知識可以用來解決什么類型的問題，應用到什么領域。應用到什么領域。 7p假設某一負責人交給你一個很難的任務，幾天后詢問假設某一負責人交給你一個很難的任務，幾天后詢問你問題解決了沒有?？赡軙l(fā)生如下圖這樣的情況：你問題解決了沒有?？赡軙l(fā)生如下圖這樣的情況：問：問：“交給你的問題，解決方法想出來了嗎？交給你的問題，解決方法想出來了嗎？”答：答：“我找不到一個有效的方法來解決它，沒能完成任我找不到一個有效的方法來解決它，沒能完成任 務。務?！?問：問：“交給你的問題，解決方法想出來了嗎？交給你的問題，解決

3、方法想出來了嗎？”答：答： “ “我找不到一個有效的方法來解決它，因為這樣的我找不到一個有效的方法來解決它，因為這樣的方法是不存在的。方法是不存在的?！币C明一個問題不存在有要證明一個問題不存在有效的方法，往往比尋找一效的方法，往往比尋找一種有效方法更難。種有效方法更難。9問：問：“交給你的問題，解決方法想出來了嗎？交給你的問題，解決方法想出來了嗎？”答：答： “ “我找到了一方法來解決它，理論上可實現(xiàn)的，但是我找到了一方法來解決它，理論上可實現(xiàn)的，但是以我們目前的力量實現(xiàn)它是不可能的。以我們目前的力量實現(xiàn)它是不可能的。” ” 方法消耗方法消耗的資源太的資源太大了。大了。10p問題能解決嗎？問

4、題能解決嗎？(可計算性可計算性)p問題解決的好嗎？問題解決的好嗎？ (計算復雜性計算復雜性)11p計算機雖然神通廣大，還是計算機雖然神通廣大，還是在人的控制下工作在人的控制下工作。 p計算機并非什么都能做，有的事情理論上它計算機并非什么都能做，有的事情理論上它根根本做不了本做不了。p討論哪些事計算機能做，哪些事計算機做不了，討論哪些事計算機能做，哪些事計算機做不了，屬于屬于可計算性可計算性理論研究的范疇。理論研究的范疇。12p26個英文字母全排列，它的排列數(shù)為個英文字母全排列，它的排列數(shù)為 26！41026p以每年以每年365天計算，共有天計算，共有3652436003.1536107秒。秒。

5、p以每秒能完成以每秒能完成107個排列的超高速電子計算機來做個排列的超高速電子計算機來做這項工作，需要這項工作，需要 41026/(3.1536107107)1.21012年（千億年）。年（千億年）。13p有一些問題雖然在理論上能夠由計算機解決，但有一些問題雖然在理論上能夠由計算機解決，但因其算法占用資源太多而無法實際完成，因此需因其算法占用資源太多而無法實際完成，因此需要選擇其他算法或改進算法。要選擇其他算法或改進算法。p要知道算法的優(yōu)劣好壞，就要對算法需要多少計要知道算法的優(yōu)劣好壞，就要對算法需要多少計算時間和存儲空間做定量的分析。算時間和存儲空間做定量的分析。迄今為止，已有迄今為止，已有

6、20%左右的計算左右的計算機科學家因其在計算復雜性方面機科學家因其在計算復雜性方面的研究工作而獲得圖靈獎。的研究工作而獲得圖靈獎。14p本課程指的計算機是和圖靈機計算能力等價的、本課程指的計算機是和圖靈機計算能力等價的、馮諾伊曼體系結構計算機，馮諾伊曼體系結構計算機， 即即確定性圖靈機。確定性圖靈機。p量子計算機是非確定性圖靈機，其算法和計算復量子計算機是非確定性圖靈機，其算法和計算復雜性完全不同。雜性完全不同。15p巡回推銷員問題巡回推銷員問題pn皇后問題皇后問題p背包問題背包問題16p 動態(tài)規(guī)劃動態(tài)規(guī)劃 設有設有n個城市，已知任意兩城市間之距個城市，已知任意兩城市間之距離，現(xiàn)有一推銷員想從

7、某一城市出發(fā)巡回經(jīng)過每離，現(xiàn)有一推銷員想從某一城市出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點，問如何找一條最短路徑。試一試求出最短發(fā)點，問如何找一條最短路徑。試一試求出最短路徑。路徑。17p 回溯法回溯法 這是高斯這是高斯1850年提出的一個著名問題：年提出的一個著名問題： 國際象棋中的國際象棋中的“皇后皇后”在橫向、豎向和斜向都能在橫向、豎向和斜向都能走步和吃子，問在走步和吃子，問在n n 格的棋盤上如何能擺上格的棋盤上如何能擺上n個個皇后而使她們都不能互相吃。皇后而使她們都不能互相吃。n當當n很大時，問題很難。很大時，問題很難。n

8、對于對于n 8，現(xiàn)已知此問題共有，現(xiàn)已知此問題共有92種解，但只有種解，但只有12種是獨種是獨立的，其余的都可以由這立的，其余的都可以由這12種利用對稱性或旋轉而得種利用對稱性或旋轉而得到。設到。設n 4，試一試。，試一試。18p有一旅行者要從有一旅行者要從3種物品中選取不超過種物品中選取不超過50公斤重的公斤重的行李隨身攜帶，要求總價值最大。行李隨身攜帶，要求總價值最大。p物品物品1重重10千克，價值千克，價值60元；物品元；物品2重重20千克，價千克，價值值100元；物品元；物品3重重30千克，價值千克，價值120元。元。n動態(tài)規(guī)劃動態(tài)規(guī)劃物品不可分割的前提下，求總價值最大。物品不可分割的

9、前提下，求總價值最大。n貪心算法貪心算法物品可以分割的前提下，求總價值最大。物品可以分割的前提下，求總價值最大。19p D.Knuth The Art of Computer ProgrammingpA.V.Aho , J.Hopcroft , J.Ullman The Design and Analysis of computer AlgothmspThomas H.Cormen, Charles E.Leiserson , Ronald L.Rivest Introduction to Algorithms20212.1 2.1 算算 法法p什么是算法什么是算法p算法的重要特性算法的重要特

10、性p計算過程與算法的區(qū)別計算過程與算法的區(qū)別p問題的求解過程問題的求解過程p算法學習的基本內(nèi)容算法學習的基本內(nèi)容22p算法是解決一確定類問題的任意一種算法是解決一確定類問題的任意一種特殊特殊的方法。的方法。n數(shù)值計算方法數(shù)值計算方法n非數(shù)值計算方法非數(shù)值計算方法p算法的非形式描述：算法就是一組有窮的規(guī)則，算法的非形式描述：算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。它規(guī)定了解決某一特定類型問題的一系列運算。 求解數(shù)值問題，插值計算、數(shù)值積分等。求解數(shù)值問題，插值計算、數(shù)值積分等。求解非數(shù)值問題，主要進行判斷比較。求解非數(shù)值問題，主要進行判斷比較。23確定性：確定性：每一種

11、運算必須要有確切的定義，無每一種運算必須要有確切的定義，無二義性；二義性；能行性：能行性：運算都是基本運算，原則上能在有限運算都是基本運算，原則上能在有限 時間內(nèi)完成；時間內(nèi)完成；輸輸 入：入：有有0個或多個輸入；個或多個輸入；輸輸 出：出：一個或多個輸出；一個或多個輸出；有窮性：有窮性：在執(zhí)行了有窮步運算后終止；在執(zhí)行了有窮步運算后終止；僅僅有窮還不夠，還要在現(xiàn)僅僅有窮還不夠，還要在現(xiàn)代計算機上有效才行。代計算機上有效才行。24計算過程可以不滿足算法的性質(zhì)計算過程可以不滿足算法的性質(zhì)(5)有窮性。有窮性。例如操作系統(tǒng)，當沒有任務時，操作系統(tǒng)并例如操作系統(tǒng)，當沒有任務時，操作系統(tǒng)并不終止，而是

12、處于等待狀態(tài)，直到有新的任不終止，而是處于等待狀態(tài)，直到有新的任務啟動，因而不是一個算法。務啟動，因而不是一個算法。 程序程序 算法算法 數(shù)據(jù)結構數(shù)據(jù)結構 (By Wirth )25證明正確性證明正確性分析算法分析算法理解問題理解問題精確解或近似解精確解或近似解算法設計策略算法設計策略選擇數(shù)據(jù)結構選擇數(shù)據(jù)結構設計算法設計算法設計程序設計程序26如何設計算法如何設計算法如何表示算法如何表示算法如何確認算法如何確認算法如何分析算法如何分析算法如何測試程序如何測試程序27如何設計算法如何設計算法p面對具體問題，運用一些基本設計策略，面對具體問題，運用一些基本設計策略，規(guī)劃算法。規(guī)劃算法。n被實踐證明

13、是有用的被實踐證明是有用的n計算機科學、運籌學、電器工程等領域計算機科學、運籌學、電器工程等領域n設計出很多精致有效的好算法設計出很多精致有效的好算法p掌握這些策略，設計出更多的好算法。掌握這些策略，設計出更多的好算法。28如何表示算法如何表示算法p設計的算法要用恰當?shù)姆绞奖硎境鰜碓O計的算法要用恰當?shù)姆绞奖硎境鰜韕采用結構程序設計的方式采用結構程序設計的方式pSPARKS程序設計語言程序設計語言簡單明了簡單明了29如何確認算法如何確認算法p算法確認算法確認(algorithm validation)證明該證明該算法對所有可能的合法輸入，都能給出正確答案算法對所有可能的合法輸入，都能給出正確答案

14、p算法確認的目的算法確認的目的確保該算法能正確無誤地工作確保該算法能正確無誤地工作n窮舉法窮舉法n推理推理數(shù)學歸納法、反證法數(shù)學歸納法、反證法n構造性證明構造性證明n測試測試30如何分析算法如何分析算法p分析執(zhí)行一個算法時，分析執(zhí)行一個算法時，n占用占用CPU時間完成運算；時間完成運算；n占用存儲器的存儲空間，存放程序和數(shù)據(jù)。占用存儲器的存儲空間，存放程序和數(shù)據(jù)。p即對一個算法需要多少計算時間和存儲空間，做即對一個算法需要多少計算時間和存儲空間，做定量分析。定量分析。31測試程序測試程序p 調(diào)試調(diào)試調(diào)試只能指出有錯誤，而不能指出它們不調(diào)試只能指出有錯誤，而不能指出它們不存在錯誤。存在錯誤。n源

15、于程序正確性的證明還沒有取得突破性進展。源于程序正確性的證明還沒有取得突破性進展。p時空分布圖時空分布圖n用各種給定數(shù)據(jù)執(zhí)行調(diào)試后的程序用各種給定數(shù)據(jù)執(zhí)行調(diào)試后的程序n測定計算時間和空間測定計算時間和空間n印證之前的分析是否正確印證之前的分析是否正確n指出實現(xiàn)最優(yōu)化的有效邏輯位置指出實現(xiàn)最優(yōu)化的有效邏輯位置32332.2 2.2 分析算法分析算法p算法分析目的算法分析目的p算法分析的準備工作算法分析的準備工作p計算時間的漸進表示計算時間的漸進表示p一些證明方法一些證明方法p作時空性能分布圖作時空性能分布圖34算法分析的目的算法分析的目的p算法分析算法分析(analysis of algorit

16、hms)是對一個是對一個算法需要多少算法需要多少計算時間計算時間和和存儲空間存儲空間作定量的分析。作定量的分析。 確定算法在什么樣的環(huán)境下能夠有效地運行。確定算法在什么樣的環(huán)境下能夠有效地運行。p分析在分析在最好最好、最壞最壞和和平均平均情況下的執(zhí)行情況。情況下的執(zhí)行情況。 對同一問題不同算法的有效性作出比較。對同一問題不同算法的有效性作出比較。35算法運行假定的計算機類型算法運行假定的計算機類型要求獨立于具體的軟硬件環(huán)境單純分析算法。要求獨立于具體的軟硬件環(huán)境單純分析算法。p假定使用一臺通用計算機假定使用一臺通用計算機n順序處理每條指令；順序處理每條指令；n存儲容量足夠大；存儲容量足夠大；n

17、存取時間恒定。存取時間恒定。/第第1次課程次課程36 證明：證明：n2 O(n3) ； 證明：證明：2n2 11n 10 O(n2) ； 證明：證明： O的以下兩個性質(zhì)成立，其中的以下兩個性質(zhì)成立，其中c是一個正常是一個正常數(shù)：數(shù)： O(f(n) O(g(n) O(f(n) g(n) ； O(cf(n) O(f(n)； 1. 證明：證明：n3 O(n2) ；37 判判斷斷以以下下命命題題是是否否成成立，立，若若成成立，立，證證明明之；之；不不成成立，立，舉舉反反例。例。 5. 如如果果g(n) (f(n)，則則 (f(n) (g(n) (f(n) ；？；？ 6. (cf(n) (f(n) ，其

18、其中中c是是一一個個正正常常數(shù)；數(shù)；？ 7. f(n) (f(n) ；？；？ 8. (f(n) (g(n) (min(f(n), g(n)；？ 9. (f(n) (g(n) (max(f(n), g(n)；？ 10. (f(n) (g(n) (f(n) g(n)；？38算法分析過程算法分析過程確定算法所涉及確定算法所涉及的運算的運算分析算法語句分析算法語句的執(zhí)行次數(shù)的執(zhí)行次數(shù)分析算法的執(zhí)分析算法的執(zhí)行時間的漸進行時間的漸進表示表示確定出能反映算確定出能反映算法在各種情況下法在各種情況下工作的數(shù)據(jù)集工作的數(shù)據(jù)集作時空性作時空性能分布圖能分布圖事前分析事前分析準備工作準備工作事后測試事后測試全面分

19、析的兩個階段全面分析的兩個階段39準備工作準備工作(一一)p首先確定使用哪些首先確定使用哪些運算運算以及執(zhí)行這些運算以及執(zhí)行這些運算所用的時間。所用的時間。n基本運算基本運算n由一些更基本的任意長序列的運算所組成的復由一些更基本的任意長序列的運算所組成的復雜運算雜運算40基本運算基本運算p時間囿界于常數(shù)的運算時間囿界于常數(shù)的運算n加、減、乘、除整數(shù)算術運算加、減、乘、除整數(shù)算術運算n浮點算術、字符比較、對變量賦值、過程調(diào)用等浮點算術、字符比較、對變量賦值、過程調(diào)用等p每種運算所用時間雖然不同，但都只花費一每種運算所用時間雖然不同，但都只花費一個固定量的時間個固定量的時間41復雜運算復雜運算p由

20、一些更基本的任意長序列的運算組成由一些更基本的任意長序列的運算組成p如：兩個字符串的比較運算如：兩個字符串的比較運算n一系列字符比較指令一系列字符比較指令n一個字符的比較時間一個字符的比較時間囿界于常數(shù)囿界于常數(shù)n字符串比較的時間總量則取決于字符串的長度字符串比較的時間總量則取決于字符串的長度42準備工作準備工作(二二)p其次是要確定出能反映算法在各種情況下工作的其次是要確定出能反映算法在各種情況下工作的數(shù)據(jù)集。數(shù)據(jù)集。n編造出能產(chǎn)生編造出能產(chǎn)生最好最好、最壞最壞和和有代表性有代表性情況的數(shù)據(jù)配置情況的數(shù)據(jù)配置n通過使用這些數(shù)據(jù)來運行算法，以更了解算法的性能。通過使用這些數(shù)據(jù)來運行算法，以更了

21、解算法的性能。算法分析最重要和最算法分析最重要和最富于創(chuàng)造性的工作。富于創(chuàng)造性的工作。43全面分析算法的兩個階段全面分析算法的兩個階段事前分析事前分析(a prior analysis) 確定每條語句的執(zhí)行次數(shù)。確定每條語句的執(zhí)行次數(shù)。 求出該算法的一個求出該算法的一個時間限界函數(shù)時間限界函數(shù)(一些關于參數(shù)一些關于參數(shù)的函數(shù)的函數(shù))事后測試事后測試(a posterior testing) 收集此算法的實際執(zhí)行時間和占用空間的統(tǒng)計收集此算法的實際執(zhí)行時間和占用空間的統(tǒng)計資料資料44算法的執(zhí)行時間算法的執(zhí)行時間p同一條語句在一個算法中的執(zhí)行次數(shù)同一條語句在一個算法中的執(zhí)行次數(shù) (frequenc

22、y count )稱為頻率計數(shù)稱為頻率計數(shù)p語句的時間總量語句的時間總量 頻率計數(shù)頻率計數(shù) 執(zhí)行一次該語句所需要執(zhí)行一次該語句所需要的時間的時間p算法的執(zhí)行時間就是構成算法的所有語句的執(zhí)行時算法的執(zhí)行時間就是構成算法的所有語句的執(zhí)行時間總量之和間總量之和由算法就可直接確定，由算法就可直接確定，與所用的機器無關，且與所用的機器無關，且獨立于程序設計語言。獨立于程序設計語言。依賴機器、程序設依賴機器、程序設計語言、編譯程序計語言、編譯程序45例：計算語句例：計算語句xx y在下面三個程序段中的頻率計數(shù)在下面三個程序段中的頻率計數(shù)beginxx yendFC:1beginfor i1 to n do

23、xx yendFC:nbeginfor i1 to n do for j1 to n doxx yendFC:n2語句的數(shù)量級是指執(zhí)行它的頻率計數(shù)之和語句的數(shù)量級是指執(zhí)行它的頻率計數(shù)之和算法的數(shù)量級是指算法的所有語句的執(zhí)行頻率之和算法的數(shù)量級是指算法的所有語句的執(zhí)行頻率之和 確定一個算法的數(shù)量級十分重要，因為它在本質(zhì)上確定一個算法的數(shù)量級十分重要，因為它在本質(zhì)上反映了算法所需的計算時間。反映了算法所需的計算時間。46p描述算法數(shù)量級的多項表達式描述算法數(shù)量級的多項表達式p最高次項最高次項p最高次項的系數(shù)最高次項的系數(shù)p最高次項的次數(shù)最高次項的次數(shù)準確分析出算法數(shù)量級的多項式表達式是很困難的，準

24、確分析出算法數(shù)量級的多項式表達式是很困難的，因此我們對事前分析的計算時間進行漸進表示。因此我們對事前分析的計算時間進行漸進表示。47時間復雜性的形式化定義時間復雜性的形式化定義p算法的時間復雜性表示為算法的時間復雜性表示為T(n)，其中，其中n是問題的是問題的規(guī)模。規(guī)模。最壞情況最壞情況下：下： Tmax(n) max T(I) | size(I) n 最好情況最好情況下：下： Tmin(n) min T(I) | size(I) n 平均情況平均情況下：下： Tavg(n) P(I) T(I) 其中其中I是問題規(guī)模為是問題規(guī)模為n的實例，的實例，p(I)是實例是實例I出現(xiàn)的概率。出現(xiàn)的概率。

25、size(I) n48p定義定義2.1：f(n) O(g(n)p定義定義2.2： f(n) (g(n)p定義定義2.3： f(n) (g(n) p定理定理2.149pf(n) 表示算法的計算時間表示算法的計算時間p n表示問題的規(guī)模表示問題的規(guī)模n輸入或輸出量；輸入或輸出量；n兩者之和；兩者之和；n其中之一的某種測度。其中之一的某種測度。pg(n)是在事前分析中確定的某個形式簡單的是在事前分析中確定的某個形式簡單的函數(shù)函數(shù) 變量和函數(shù)的含義變量和函數(shù)的含義與機器和語言有關，而與機器和語言有關，而是獨立于機器和語言的。是獨立于機器和語言的。50n 當當n充分大時，充分大時， 有上界，一個常數(shù)倍的

26、有上界，一個常數(shù)倍的)是是 的一個上界，的一個上界， 的數(shù)量級就是的數(shù)量級就是)。的階不高于的階不高于)的階。的階。n 在確定在確定的數(shù)量級時，總是試圖求出的數(shù)量級時，總是試圖求出最小的最小的)。n 有關證明中，找出有關證明中，找出c和和n0是關鍵。是關鍵。51例子例子 判斷判斷 f(n) O(g(n) ？pf(n) 3n, g(n) 4npf(n) n 1024, g(n) 1025npf(n) 2n2 11n 10, g(n) n2pf(n) n2, g(n) n3p反例：反例： f(n) n3, g(n) 5n252對于非負的對于非負的f(n)和和g(n)，根據(jù)定義，根據(jù)定義2.1，有如

27、下性質(zhì)：，有如下性質(zhì)：1. O(f(n) O(g(n) O(max(f(n), g(n) ;2. O(f(n) O(g(n) O(f(n) g(n) ；3. O(f(n) O(g(n) O(f(n) g(n) ；4. 如果如果g(n) O(f(n) ，則，則O(f(n) O(g(n) O(f(n) ；5. O(cf(n) O(f(n) ，其中，其中c是一個正的常數(shù)；是一個正的常數(shù)；6. f(n) O(f(n)。53證明：取證明：取n0 1，當，當n n0時時 由由A(n)的定義和不等式關系的定義和不等式關系|A B| |A| |B|有有 |A(n)| |amnm a1 n a0 | |am|n

28、m |a1 | n |a0 | (|am| |am 1| n |a0 | nm ) nm (|am| |am 1| |a0 |) nm取取 c |am| |am 1| |a0 |，有，有|A(n)| cnm即：即：A(n) O(nm)，定理得證。，定理得證。54 定理定理2.1表明，變量表明，變量n的最高階數(shù)為的最高階數(shù)為m的任一多項式，的任一多項式，與與nm同階。因此一個計算時間為同階。因此一個計算時間為m階多項式的算階多項式的算法，其時間都可以用法，其時間都可以用O(nm)來表示。來表示。 若一個算法有數(shù)量級為若一個算法有數(shù)量級為c1nm1，c2nm2， cknmk的的k個語句，則算法的數(shù)

29、量級及計算時間就是個語句，則算法的數(shù)量級及計算時間就是 c1nm1 c2nm2 cknmk O(nm) 其中其中 m maxmi|1 i k55從計算時間上對算法分類從計算時間上對算法分類(polynomial time algorithm)： 用多項式來對其計算時間限界的算法用多項式來對其計算時間限界的算法O(1) O(logn) O(n) O(nlogn) O(n2) O(n3)(exponential time algorithm)： 計算時間用指數(shù)函數(shù)限界的算法計算時間用指數(shù)函數(shù)限界的算法 O(2n) O(n ) O(nn)56不同時間復雜性函數(shù)的對比不同時間復雜性函數(shù)的對比57585

30、9n 當當n充分大時，充分大時，f(n)有下界，一個常數(shù)倍的有下界，一個常數(shù)倍的g(n)是是f(n)的一個下界。的一個下界。n f(n)的階不低于的階不低于g(n)的階。的階。n 在確定在確定f(n)的下界時，總是試圖求出的下界時，總是試圖求出最大的最大的g(n) 。n 有關證明中，找出有關證明中，找出c和和n0是關鍵。是關鍵。 60對于非負的對于非負的f(n)和和g(n)，根據(jù)定義，根據(jù)定義2.2，有如下性質(zhì)：，有如下性質(zhì)：1. (f(n) (g(n) (min(f(n), g(n) ;2. (f(n) (g(n) (f(n) g(n) ；3. (f(n) (g(n) (f(n) g(n)

31、；4.如果如果g(n) (f(n) ，則，則 (f(n) (g(n) (f(n) ；5. (cf(n) (f(n) ，其中，其中c是一個正的常數(shù)；是一個正的常數(shù)；6.f(n) (f(n)。61定義定義2.3 如果存在兩個正常數(shù)如果存在兩個正常數(shù)c1, c2和和n0，對于所有的，對于所有的n n0，有，有 c1 |g(n)| |f(n)| c2 |g(n)|，則記作：，則記作：f(n)(g(n) 一個算法的一個算法的f(n)(g(n)意味著該算法在最好和最壞意味著該算法在最好和最壞情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相情況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的。同的。/第第2次課程次

32、課程626364規(guī)則規(guī)則O(f(n) O(g(n) O(maxf(n), g(n) 的的證明證明：對于任意對于任意f1(n) O(f(n) ，存在正常數(shù)，存在正常數(shù)c1和自然數(shù)和自然數(shù)n1，使得對所有，使得對所有n n1，有，有f1(n) c1f(n) 。類似地，對于任意類似地，對于任意g1(n) O(g(n) ，存在正常數(shù)，存在正常數(shù)c2和自然數(shù)和自然數(shù)n2，使得對所有使得對所有n n2，有，有g1(n) c2g(n) 。令令c3 maxc1, c2， n3 maxn1, n2，h(n) maxf(n),g(n) 。則對所有的則對所有的 n n3，有，有f1(n) g1(n) c1f(n)

33、c2g(n) c3f(n) c3g(n) c3(f(n) g(n) 2c3 maxf(n), g(n) 2c3h(n) O(maxf(n),g(n) .65規(guī)則規(guī)則O(f(n) O(g(n) O(f(n) g(n) 的的證明證明：對于任意對于任意f1(n) O(f(n) ，存在正常數(shù)，存在正常數(shù)c1和自然數(shù)和自然數(shù)n1，使得對所有，使得對所有n n1，有，有f1(n) c1f(n) 。類似地，對于任意類似地，對于任意g1(n) O(g(n) ，存在正常數(shù)，存在正常數(shù)c2和自然數(shù)和自然數(shù)n2，使得對所有使得對所有n n2，有，有g1(n) c2g(n) 。令令c3 maxc1, c2， n3 m

34、axn1, n2，h(n) f(n) g(n) 。則對所有的則對所有的 n n3，有，有 O(f(n) O(g(n) f1(n) g1(n) c1f(n) c2g(n) c3f(n) c3g(n) c3(f(n) g(n) c3h(n) O(f(n) g(n) .66規(guī)則規(guī)則O(f(n) O(g(n) O(f(n) g(n) 的的證明證明：對于任意對于任意f1(n) O(f(n) ，存在正常數(shù)，存在正常數(shù)c1 1和自然數(shù)和自然數(shù)n1， 使得對所有使得對所有 n n1，有，有f1(n) c1f(n) 。類似地，對于任意類似地，對于任意g1(n) O(g(n) ，存在正常數(shù)，存在正常數(shù)c2 1和自

35、然數(shù)和自然數(shù)n2， 使得對所有使得對所有n n2，有，有g1(n) c2g(n) 。令令c3 c1 c2， n3 maxn1, n2，h(n) f(n) g(n) 。則對所有的則對所有的 n n3，有，有 O(f(n) O(g(n) f1(n) g1(n) c1f(n) c2g(n) c3f(n) g(n) c3h(n) O(f(n) g(n) .67常用的整數(shù)求和公式常用的整數(shù)求和公式1n1(n) i21(1)/ 2() i nin nn231(1)(21)/6() i nin nnn111()12 kkkki nnnink低次項68697071對于正整數(shù)對于正整數(shù)m, n和實數(shù)和實數(shù)a 0

36、: a0 1; a1 a ; a-1 1/a ; (am)n amn ; (am)n (an)m ; aman am+n ; a 1 an為為單調(diào)遞增函數(shù)單調(diào)遞增函數(shù); a 1 nb o(an)lim0bnnna7223012!3!ixixxxexi lim1nxnxen 73 log n log2n; lg n log10n; ln n logen; logkn (log n)k; log log n log(log n); for a0, b0, c0abbalog74log ()loglogcccababloglognbbanalogloglogcbcaablog (1/ )logbba

37、a1loglogbaabloglogbbcaac75|x| 1 for x 1,for any a 0, , logbn O(na)2345ln(1).2345xxxxxxln(1)1xxxxloglogloglimlim0(2 )bbanannnnn7610!(1)!0nnn nn! 1 2 3nn 1!21nnnnen77!2nnnnnee1112112nnn!()nno n!(2 )nnlog( !)( log )nnn 78一些數(shù)學證明方法一些數(shù)學證明方法p直接證明：直接證明：PQp間接證明：間接證明：n反證法反證法n舉反例舉反例p數(shù)學歸納法：數(shù)學歸納法：n初始歸納：初始歸納：i 1

38、結論成立；結論成立；n歸納假設：若歸納假設：若i n 1時成立；時成立；n歸納證明：證明歸納證明：證明i n時成立。時成立。79p事后測試是在對算法進行設計、確認、事前分析和事后測試是在對算法進行設計、確認、事前分析和調(diào)試之后要做的工作，以確定程序所耗費的精確時調(diào)試之后要做的工作，以確定程序所耗費的精確時間和空間，即作時空性能分布圖。間和空間，即作時空性能分布圖。與所用計算機密與所用計算機密切相關切相關。8081 SPARKS語言的基本數(shù)據(jù)類型：語言的基本數(shù)據(jù)類型： 整型整型(integer), 實型實型(real), 布爾型布爾型(boolean), 字符型字符型(char) SPARKS語言的語言的變量命名規(guī)則變量命名規(guī)則： 以字母開頭，不允許使用特殊字符，不允許與保留字重復