算法分析與設(shè)計(jì)課件

1算法分析與設(shè)計(jì)1算法分析與設(shè)計(jì)2第1章算法引論1 課程學(xué)習(xí)背景1.1為什么學(xué)習(xí)算法？1.2算法的定義1.3如何描述一個(gè)算法？2 算法復(fù)雜性分析2.1計(jì)算模型與算法分析框架2.2漸進(jìn)表示2第1章算法引論1 課程學(xué)習(xí)背景為什么要學(xué)習(xí)算法算法是計(jì)算機(jī)科學(xué)的基石，是改造世界的有力工具！

互聯(lián)網(wǎng)是20世紀(jì)最偉大的發(fā)明之一，改變了世界，改變了我們的生活！各種算法在支撐著整個(gè)互聯(lián)網(wǎng)的正常運(yùn)行，互聯(lián)網(wǎng)的信息傳輸需要路由選擇算法，互聯(lián)網(wǎng)的信息安全需要加密算法，互聯(lián)網(wǎng)的信息檢索需要模式匹配算法，互聯(lián)網(wǎng)的信息存儲(chǔ)需要排序算法，……，沒(méi)有算法也就沒(méi)有互聯(lián)網(wǎng)！學(xué)習(xí)算法可以開(kāi)發(fā)人們的分析能力

算法是解決問(wèn)題的一類特殊方法，它是經(jīng)過(guò)對(duì)問(wèn)題的準(zhǔn)確理解和定義獲取答案的過(guò)程。是你獲得高薪職位的敲門(mén)磚！3“微積分以及在微積分基礎(chǔ)上建立起來(lái)的數(shù)學(xué)分析體系成就了現(xiàn)代科學(xué)，而算法則成就了現(xiàn)代世界”——DavidBerlinski,2000為什么要學(xué)習(xí)算法算法是計(jì)算機(jī)科學(xué)的基石，是改造世界的有力工具思考題：小雞啄米輸入：一個(gè)m*n的矩陣A，矩陣的每一個(gè)元素都是一個(gè)非負(fù)整數(shù)，代表該位置的米數(shù)；有一只小雞從左上角A[1][1]出發(fā)，每次往右或者往下走一步，走到右下角A[m][n]停止；小雞會(huì)將途中經(jīng)過(guò)的所有米粒都吃掉；設(shè)計(jì)一個(gè)算法，計(jì)算出小雞應(yīng)該如何走保證吃到的米粒最多。分析算法時(shí)間復(fù)雜度。4思考題：小雞啄米輸入：一個(gè)m*n的矩陣A，矩陣的每一個(gè)元素都思考題：小雞啄米假設(shè)有兩只小雞從左上角A[1][1]出發(fā)，都要走到右下角A[m][n]，都只能向下或者向右移動(dòng)；兩只小雞移動(dòng)的先后順序不做限制，但是先到某個(gè)位置的小雞會(huì)將該位置米粒吃完；問(wèn)如何安排兩只小雞的移動(dòng)順序與軌跡，使得兩只小雞吃到的米粒數(shù)之和最多？如果有k只小雞呢？5思考題：小雞啄米假設(shè)有兩只小雞從左上角A[1][1]出發(fā)，都6為什么要分析算法效率？

6為什么要分析算法效率？

7算法效率的各個(gè)方面時(shí)間效率排序算法效率空間效率路由器與布隆過(guò)濾器（bloomfilter）通訊量效率比特幣與稀疏恢復(fù)MapReduce與DSP模型7算法效率的各個(gè)方面時(shí)間效率8第1章算法引論1 課程學(xué)習(xí)背景1.1為什么學(xué)習(xí)算法？1.2算法的定義1.3如何描述一個(gè)算法？2 算法復(fù)雜性分析2.1計(jì)算模型與算法分析框架2.2漸進(jìn)表示8第1章算法引論1 課程學(xué)習(xí)背景什么是算法？簡(jiǎn)單說(shuō)來(lái)，算法就是問(wèn)題的程序化解決方案。定義：算法就是一個(gè)定義良好的可計(jì)算過(guò)程，它取一個(gè)或者一組值作為輸入，并產(chǎn)生出一個(gè)或者一組值作為輸出。即，算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。algorithmInputComputationalProcedureOutput<31,41,59,26,12,58><31,41,26,12,58,59><31,41,59,26,12,58><31,26,12,41,58,59>……<12,26,31,41,58,59>“冒泡”排序是個(gè)計(jì)算過(guò)程9什么是算法？簡(jiǎn)單說(shuō)來(lái)，算法就是問(wèn)題的程序化解決方案。Inpu什么是算法？一個(gè)算法通常具有如下特征：輸入：一個(gè)算法具有零個(gè)或者多個(gè)取自指定集合的輸入值；輸出：對(duì)算法的每一次輸入，算法具有一個(gè)或多個(gè)與輸入值相聯(lián)系的輸出值；確定性：算法的每一個(gè)指令步驟都是明確的；有限性：對(duì)算法的每一次輸入，算法都必須在有限步驟（即有限時(shí)間）內(nèi)結(jié)束；正確性：對(duì)每一次輸入，算法應(yīng)產(chǎn)生出正確的輸出值；通用性：算法的執(zhí)行過(guò)程可應(yīng)用于所有同類求解問(wèn)題，而不是僅適用于特殊的輸入。10什么是算法？一個(gè)算法通常具有如下特征：10相關(guān)概念：?jiǎn)栴}和問(wèn)題實(shí)例問(wèn)題（Problem）：規(guī)定了輸入與輸出之間的關(guān)系，可以用通用語(yǔ)言來(lái)描述；問(wèn)題實(shí)例：某一個(gè)問(wèn)題的實(shí)例包含了求解該問(wèn)題所需的輸入；排序問(wèn)題——將一系列數(shù)按非降順序進(jìn)行排序排序問(wèn)題的一個(gè)實(shí)例：11輸入:由n個(gè)數(shù)組成的一個(gè)序列輸出:對(duì)輸入系列的一個(gè)排列(重排），使得Input:<31,41,59,26,41,58>——Output:<26,31,41,41,58,59>相關(guān)概念：?jiǎn)栴}和問(wèn)題實(shí)例問(wèn)題（Problem）：規(guī)定了輸入與相關(guān)概念：?jiǎn)栴}和問(wèn)題實(shí)例算法可求解的問(wèn)題：人類基因項(xiàng)目在電子商務(wù)中的應(yīng)用在互聯(lián)網(wǎng)中的應(yīng)用（圖像檢索、視頻檢索……）…….重要問(wèn)題類型：排序、查找、字符串處理、圖問(wèn)題、組合問(wèn)題、幾何問(wèn)題、數(shù)值問(wèn)題等。12相關(guān)概念：?jiǎn)栴}和問(wèn)題實(shí)例算法可求解的問(wèn)題：12相關(guān)概念：輸入實(shí)例與問(wèn)題規(guī)模輸入實(shí)例：?jiǎn)栴}的具體計(jì)算例子如，排序問(wèn)題的3個(gè)輸入實(shí)例：13,5,6,37,8,92,1243,5,23,76,2553,67,32,42,22,33,4,39,56問(wèn)題規(guī)模：算法的輸入實(shí)例大小。如，上面排序問(wèn)題的3個(gè)輸入實(shí)例的規(guī)模大小分別為7,5,913相關(guān)概念：輸入實(shí)例與問(wèn)題規(guī)模輸入實(shí)例：?jiǎn)栴}的具體計(jì)算例子13相關(guān)概念：正確算法與不正確算法正確的算法

如果一個(gè)算法對(duì)問(wèn)題每一個(gè)輸入實(shí)例，都能輸出正確的結(jié)果并停止，則稱它為正確的。不正確的算法可能根本不會(huì)停止；停止時(shí)給出的不是預(yù)期的結(jié)果；如果算法的錯(cuò)誤率可以控制，也是有用的。14相關(guān)概念：正確算法與不正確算法正確的算法14作為一種技術(shù)的算法15如果計(jì)算機(jī)無(wú)限快、存儲(chǔ)器都是免費(fèi)的,算法研究是否還需要？Yes！證明方案是正確的，可以給出正確結(jié)果。Yes！希望自己的實(shí)現(xiàn)符合良好的軟件工程實(shí)踐要求，采用最容易的實(shí)現(xiàn)方法。算法對(duì)于當(dāng)代計(jì)算機(jī)非常重要！類比硬件與軟件的不同，算法的迥異帶來(lái)的意義可能更明顯！比如，對(duì)100萬(wàn)個(gè)數(shù)字進(jìn)行排序：插入排序:計(jì)算機(jī)A:109指令/s世界最好的程序員器語(yǔ)言歸并排序:計(jì)算機(jī)B:107指令/s普通程序員高級(jí)語(yǔ)言+低效編譯器作為一種技術(shù)的算法15如果計(jì)算機(jī)無(wú)限快、存儲(chǔ)器都是免費(fèi)的,算問(wèn)題求解基礎(chǔ)16理解問(wèn)題決定：計(jì)算方法；精確或近似解法；數(shù)據(jù)結(jié)構(gòu)；算法設(shè)計(jì)技術(shù)設(shè)計(jì)算法正確性證明分析算法根據(jù)算法寫(xiě)代碼

算法設(shè)計(jì)和分析過(guò)程問(wèn)題求解基礎(chǔ)16理解問(wèn)題決定：設(shè)計(jì)算法正確性證明分析算法根據(jù)問(wèn)題求解基礎(chǔ)求解過(guò)程說(shuō)明：理解問(wèn)題：是否屬于已知問(wèn)題？確定算法輸入范圍；了解計(jì)算設(shè)備的性能：清楚速度和計(jì)算資源的限制；在精確解法和近似解法之間做選擇：有時(shí)近似算法是唯一選擇；確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)算法的設(shè)計(jì)技術(shù)：這是本課程學(xué)習(xí)重點(diǎn)和目標(biāo)；算法的描述：自然語(yǔ)言、流程圖、偽代碼；算法的正確性證明：證明對(duì)于所有合法輸入均能產(chǎn)生正確結(jié)果；算法的分析：分析執(zhí)行效率（時(shí)間和空間）、簡(jiǎn)單性、一般性；為算法寫(xiě)代碼：利用編程語(yǔ)言以計(jì)算機(jī)程序行使實(shí)現(xiàn)；17問(wèn)題求解基礎(chǔ)求解過(guò)程說(shuō)明：1718第1章算法引論1 課程學(xué)習(xí)背景1.1學(xué)習(xí)動(dòng)機(jī)1.2算法定義1.3算法描述2 算法復(fù)雜性分析2.1計(jì)算模型與算法分析框架2.2漸進(jìn)表示18第1章算法引論1 課程學(xué)習(xí)背景算法描述方法偽代碼擁有自然語(yǔ)言和類編程語(yǔ)言特性，經(jīng)常被用于算法描述；與真實(shí)代碼(realcode)的差異:對(duì)特定算法的描述更加的清晰與精確；不需要考慮太多技術(shù)細(xì)節(jié)（數(shù)據(jù)抽象、模塊、錯(cuò)誤處理等）；用偽代碼可以體現(xiàn)算法本質(zhì)；永遠(yuǎn)不會(huì)過(guò)時(shí)；19算法描述方法偽代碼擁有自然語(yǔ)言和類編程語(yǔ)言特性，經(jīng)常被用于算算法描述方法20偽代碼的一些約定：書(shū)寫(xiě)上的“縮進(jìn)”(縮排)表示程序中的分程序（程序塊）結(jié)構(gòu)；循環(huán)結(jié)構(gòu)(while,for,repeat)和條件結(jié)構(gòu)(if,then,else)與Pascal,C語(yǔ)言類似；“//”or“”來(lái)表示注釋；利用i←j←e

來(lái)表示多重賦值，等價(jià)于

j←e

和i←j.變量是局部于給定過(guò)程的。數(shù)組元素的訪問(wèn)方式:A[i];A[1..j]=<A[1],A[2],…,A[i]>符合數(shù)據(jù)一般組織成對(duì)象，由屬性（attribute）或域(field)所組成；域的訪問(wèn)是由域名后跟方括號(hào)括住的對(duì)象名形式來(lái)表示,如length[A]；參數(shù)采用按值傳遞方式；布爾操作“and”和“or”具有短路能力:如“xand(or)y”:無(wú)論y的值如何，必須首先計(jì)算x的值。算法描述方法20偽代碼的一些約定：插入排序的偽代碼問(wèn)題:

把一系列數(shù)據(jù)按非遞增的順序排列輸入:n個(gè)輸入數(shù)輸出:輸入系列的一個(gè)排序，使得INSERTION-SORT(A)1 for(j=2;j<=length[A];j++)2 key=A[j]3 i←j-14 while(i>0&&A[i]>key)5 A[i+1]=A[i]6 i=i-1 7 A[i+1]=key21插入排序的偽代碼問(wèn)題:把一系列數(shù)據(jù)按非遞增的順序排列I22第1章算法引論1 課程學(xué)習(xí)背景1.1學(xué)習(xí)動(dòng)機(jī)1.2算法定義1.3算法描述2 算法復(fù)雜性分析2.1計(jì)算模型與算法分析框架2.2漸進(jìn)表示22第1章算法引論1 課程學(xué)習(xí)背景算法分析框架算法分析是指對(duì)一個(gè)算法所需要的資源進(jìn)行預(yù)測(cè)，通常是對(duì)計(jì)算時(shí)間和空間的預(yù)測(cè)。算法分析的目的是為了從多個(gè)候選算法中選擇一個(gè)最有效的算法，或去掉較差的算法。進(jìn)行算法分析之前，首先要確立有關(guān)實(shí)現(xiàn)技術(shù)的模型，通常采用隨機(jī)存取機(jī)（RAM）計(jì)算模型。默認(rèn)情況下，算法分析一般是指對(duì)算法時(shí)間效率的分析。23算法分析框架算法分析是指對(duì)一個(gè)算法所需要的資源進(jìn)行預(yù)測(cè)，通常RAM模型

24RAM模型

24RAM模型（內(nèi)存模型）RAM（RandomAccessmachine）：隨機(jī)訪問(wèn)機(jī)Unitcostassumption模型簡(jiǎn)單，應(yīng)用廣泛25CPU內(nèi)存RAM模型（內(nèi)存模型）RAM（RandomAccessm26內(nèi)存層級(jí)現(xiàn)代計(jì)算機(jī)的存儲(chǔ)由多層級(jí)組成hierarchy層級(jí)離CPU越遠(yuǎn)，速度越慢，存儲(chǔ)容量越大不同層級(jí)之間以塊（block）的形式移動(dòng)數(shù)據(jù)內(nèi)存L1L226內(nèi)存層級(jí)LL27SlowI/ODiskaccessis106timesslowerthanmainmemoryaccesstrackmagneticsurfaceread/writearm“ThedifferenceinspeedbetweenmodernCPUanddisktechnologiesisanalogoustothedifferenceinspeedinsharpeningapencilusingasharpeneronone’sdeskorbytakinganairplanetotheothersideoftheworldandusingasharpeneronsomeoneelse’sdesk.”

(D.Comer)4835191557484125datasizerunningtime27SlowI/ODiskaccessis106tI/O模型（外存模型）去掉Unitcostassumption以塊（block）形式讀取磁盤(pán)數(shù)據(jù)28CPU磁盤(pán)內(nèi)存BlockI/O模型（外存模型）去掉Unitcostassumpt數(shù)據(jù)流模型數(shù)據(jù)流是一個(gè)由海量數(shù)據(jù)組成的數(shù)據(jù)序列SinglePass:每個(gè)數(shù)據(jù)最多訪問(wèn)一次SmallSpace:存儲(chǔ)空間非常小Smalltime:更新(插入刪除)速度快CPU內(nèi)存：數(shù)據(jù)摘要回答近似查詢頻繁項(xiàng)有哪些/數(shù)據(jù)分布是什么/Top-K是什么？數(shù)據(jù)流模型數(shù)據(jù)流是一個(gè)由海量數(shù)據(jù)組成的數(shù)據(jù)序列CPU內(nèi)存：數(shù)算法分析框架算法運(yùn)行時(shí)間是指在特定輸入時(shí)，所執(zhí)行的基本操作數(shù)。輸入數(shù)據(jù)的規(guī)模和分布是影響算法運(yùn)行時(shí)間的兩個(gè)主要因素。

算法時(shí)間效率分析框架：算法時(shí)間效率用算法輸入規(guī)模n為參數(shù)的函數(shù)來(lái)度量；對(duì)輸入規(guī)模相同情況下，有些算法的時(shí)間效率會(huì)有明顯差異。對(duì)于這樣的算法要區(qū)分最壞運(yùn)行時(shí)間、最佳運(yùn)行時(shí)間、平均運(yùn)行時(shí)間；對(duì)于大規(guī)模輸入，通常只關(guān)注運(yùn)行時(shí)間效率函數(shù)的增長(zhǎng)率，即只關(guān)注函數(shù)的高階項(xiàng)，而忽略低階項(xiàng)和高階項(xiàng)系數(shù)。30算法分析框架算法運(yùn)行時(shí)間是指在特定輸入時(shí)，所執(zhí)行的基本操作數(shù)算法分析框架對(duì)于規(guī)模為n的任何輸入，一般考察算法的最壞運(yùn)行時(shí)間：最壞情況運(yùn)行時(shí)間是在任何輸入情況下的一個(gè)上界；對(duì)于某些算法來(lái)說(shuō)，最壞情況出現(xiàn)還是比較頻繁的，如信息檢索（信息經(jīng)常不存在）；大致上看，“平均情況”通常和最壞情況一樣差。平均運(yùn)行時(shí)間（期望運(yùn)行時(shí)間）概率分析技術(shù)(probabilisticanalysis)隨機(jī)化算法(randomizedalgorithm)函數(shù)的增長(zhǎng)率抽象簡(jiǎn)化。忽略每條語(yǔ)句的真實(shí)代價(jià)，用常量c來(lái)表示；進(jìn)一步忽略了抽象的代價(jià)；增長(zhǎng)率或增長(zhǎng)量級(jí)。只考慮公式中的最高項(xiàng)，忽略最高項(xiàng)系數(shù)和低階項(xiàng)；31算法分析框架對(duì)于規(guī)模為n的任何輸入，一般考察算法的最壞運(yùn)行時(shí)插入排序問(wèn)題:

把一系列數(shù)據(jù)按非遞增的順序排列輸入:n個(gè)輸入數(shù)輸出:輸入系列的一個(gè)排序，使得32插入排序問(wèn)題:把一系列數(shù)據(jù)按非遞增的順序排列32INSERTION-SORT(A)1 for(j=2;j<=length[A];j++)//loopheader2 key=A[j]3 //InsertA[j]intothesortedsequenceA[1..j-1]4 i←j-15 while(i>0&&A[i]>key)6 A[i+1]=A[i]7 i=i-1 8 A[i+1]=key33插入排序INSERTION-SORT(A)33插入排序插入排序總運(yùn)行時(shí)間：34插入排序總運(yùn)行時(shí)間：34如果數(shù)組是排好序的，則會(huì)出現(xiàn)最好情況：如果數(shù)組是逆序排序的，則會(huì)出現(xiàn)最差情況：

此時(shí)必須將每個(gè)元素A[j]與整個(gè)已排序的子數(shù)組A[1..j-1]中的每一個(gè)元素進(jìn)行比較，對(duì)j=2,3,…,n,有tj=j.則有：35插入排序35插入排序DBSCAN的故事DBSCAN，英文全寫(xiě)為Density-basedspatialclusteringofapplicationswithnoise，是在1996年由MartinEster,Hans-PeterKriegel,J?rgSander及XiaoweiXu提出的聚類分析算法，這個(gè)算法是以密度為本的：給定某空間里的一個(gè)點(diǎn)集合，這算法能把附近的點(diǎn)分成一組（有很多相鄰點(diǎn)的點(diǎn)），并標(biāo)記出位于低密度區(qū)域的局外點(diǎn)（最接近它的點(diǎn)也十分遠(yuǎn)）DBSCAN是其中一個(gè)最常用的聚類分析算法，也是其中一個(gè)科學(xué)文章中最常引用的。在2014年，這個(gè)算法在領(lǐng)頭數(shù)據(jù)挖掘會(huì)議ACMSIGKDD上獲頒發(fā)了TestofTimeaward，該獎(jiǎng)項(xiàng)是頒發(fā)給一些于理論及實(shí)際層面均獲得持續(xù)性的關(guān)注的算法。36DBSCAN的故事DBSCAN，英文全寫(xiě)為Density-bDBSCAN的故事2015年的數(shù)據(jù)庫(kù)頂級(jí)會(huì)議ACMSIGMOD的最佳論文“DBSCANRevisited:Mis-Claim,Un-Fixability,andApproximation”中，JunhaoGan和YufeiTao發(fā)現(xiàn)，DBSCAN的算法時(shí)間復(fù)雜度有誤DBSCAN原作者認(rèn)為算法時(shí)間復(fù)雜度是O(nlogn)的，而實(shí)際上是O(n2)該論文在數(shù)據(jù)挖掘領(lǐng)域和數(shù)據(jù)庫(kù)領(lǐng)域都引起論戰(zhàn)后來(lái)，很多數(shù)據(jù)挖掘的學(xué)者為DBSCAN辯護(hù)稱，雖然其最壞情況時(shí)間復(fù)雜度是O(n2)，但是其平均時(shí)間復(fù)雜度是O(nlogn)的理由：假設(shè)所有點(diǎn)是均勻分布的前提下，算法的時(shí)間復(fù)雜度是O(nlogn)的其實(shí)這仍然不對(duì)，為什么？故事的意義：算法的時(shí)間復(fù)雜度非常關(guān)鍵，受到研究領(lǐng)域的極大重視即使一個(gè)經(jīng)典的算法/論文/定理，仍然有出現(xiàn)錯(cuò)誤的可能，需要自己多思考37DBSCAN的故事2015年的數(shù)據(jù)庫(kù)頂級(jí)會(huì)議ACMSIGM38第1章算法引論1 課程學(xué)習(xí)背景1.1學(xué)習(xí)動(dòng)機(jī)1.2算法定義1.3算法描述2 算法復(fù)雜性分析2.1計(jì)算模型與算法分析框架2.2漸進(jìn)表示38第1章算法引論1 課程學(xué)習(xí)背景39算法復(fù)雜性分析計(jì)算時(shí)間的漸近表示記：兩個(gè)算法的計(jì)算時(shí)間為函數(shù)f(n)與g(n)其中，

n輸入或輸出規(guī)模的某種測(cè)度。以下給出算法執(zhí)行時(shí)間：上界（О）、下界（Ω）、平均（）、低階(o)的定義。39算法復(fù)雜性分析計(jì)算時(shí)間的漸近表示40算法復(fù)雜性分析1）上界函數(shù)定義1.1如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有0≤

f(n)≤c*g(n)

則記作f(n)=Ο(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。則g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)。f(n)的數(shù)量級(jí)就是g(n)。試圖求出最小的g(n)，使得f(n)=Ο(g(n))。40算法復(fù)雜性分析1）上界函數(shù)41Big-oh41Big-oh42算法復(fù)雜性分析1）上界函數(shù)例1[線性函數(shù)]f(n)=3n+2

當(dāng)n

2時(shí)，3n+2

3n+n=4n，故f(n)=O(n)

當(dāng)n>0時(shí)，3n+2

10n，故f(n)=O(n)例2[平方函數(shù)]f(n)=10n2+

4n+2

當(dāng)n

2時(shí)，f(n)

10n2+

5n，故f(n)=O(n2)

當(dāng)n

5時(shí)，f(n)

10n2+

n2=11n2，故f(n)=O(n2)C=4,n0=2C=10,n0=0C=10,n0=2C=10,n0=542算法復(fù)雜性分析1）上界函數(shù)C=4,n0=2C=10,n043算法復(fù)雜性分析1）上界函數(shù)例3[指數(shù)函數(shù)]f(n)=6*2n+n2

當(dāng)n

4時(shí)，n2

2n，f(n)

6*2n+2n=7*2n

，故f(n)=O(2n)例4[常數(shù)函數(shù)]f(n)=99*1故f(n)=O(1)f(n)=20112011*1故f(n)=O(1)C=7,n0=4C=9,n0=0C=2011,n0=043算法復(fù)雜性分析1）上界函數(shù)C=7,n0=4C=9,n044算法復(fù)雜性分析1）上界函數(shù)例5[松散界限]f(n)=3n+3

當(dāng)n

2時(shí)，f(n)

3n2，故f(n)=O(n2)例6[錯(cuò)誤界限]f(n)=9*n+2

O(1)

n2不是最小上限不存在c>0及n044算法復(fù)雜性分析1）上界函數(shù)n2不是最小上限不存在c>0及45算法復(fù)雜性分析1）上界函數(shù)有如下運(yùn)算規(guī)則：

(1)Ο(f)+Ο(g)=Ο(max(f,g))(2)Ο(f)+Ο(g)=Ο(f+g)(3)Ο(f)Ο(g)=Ο(fg)(4)如果g(N)=Ο(f(N))，則Ο(f)+Ο(g)=Ο(f)(5)Ο(Cf(N))=Ο(f(N)),其中C是一個(gè)正的常數(shù).(6)f=Ο(f)45算法復(fù)雜性分析1）上界函數(shù)46算法復(fù)雜性分析多項(xiàng)式定理:定理1若A(n)=amnm+…+a1n+a0是一個(gè)m次多項(xiàng)式，則有A(n)=Ο(nm)

即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。證明：取n0=1,當(dāng)n≥n0時(shí)，有

|A(n)|≤|am|nm+…+|a1|n+|a0|≤(|am|+|am-1|/n+…+|a0|/nm)nm

≤(|am|+|am-1|+…+|a0|)nm

令c=|am|+|am-1|+…+|a0|

則，定理得證。46算法復(fù)雜性分析多項(xiàng)式定理:47算法復(fù)雜性分析大O比率定理:對(duì)于函數(shù)f(n)和g(n),若存在，則f(n)=O(g(n))當(dāng)且僅當(dāng)存在確定的常數(shù)c，有證明：如果f(n)=O(g(n))，則存在c>0及某個(gè)n0,

使得對(duì)于所有的n

n0，有f(n)/g(n)c，因此假定，它表明存在一個(gè)n0，使得對(duì)于所有的n

n0，有f(n)max{1,c}*g(n).47算法復(fù)雜性分析大O比率定理:對(duì)于函數(shù)f(n)和g(n)48算法復(fù)雜性分析例7因?yàn)?/p>

所以3n+2=O(n)

因?yàn)?/p>

所以10n2+

4n+2=O(n2)

因?yàn)?/p>

所以6*2n+n2=O(2n)

因?yàn)?/p>

所以3n+3=O(n2)

因?yàn)?/p>

所以3n2+3

O(n)48算法復(fù)雜性分析例7因?yàn)?9算法復(fù)雜性分析計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響。例：假設(shè)解決同一個(gè)問(wèn)題的兩個(gè)算法，它們都有n個(gè)輸入，計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則，

n=1024：分別需要1048576和10240次運(yùn)算。

n=2048：分別需要4194304和22528次運(yùn)算。分析：在n加倍的情況下，一個(gè)Ο(n2)的算法計(jì)算時(shí)間增長(zhǎng)4

倍，而一個(gè)Ο(nlogn)算法則只用兩倍多一點(diǎn)的時(shí)間即可完成。49算法復(fù)雜性分析計(jì)算時(shí)間的數(shù)量級(jí)對(duì)算法有效性的影響50算法復(fù)雜性分析算法分類（計(jì)算時(shí)間）多項(xiàng)式時(shí)間算法：可用多項(xiàng)式（函數(shù)）對(duì)其計(jì)算時(shí)間限界的算法。常見(jiàn)的多項(xiàng)式限界函數(shù)有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法常見(jiàn)的指數(shù)時(shí)間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)說(shuō)明：當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。50算法復(fù)雜性分析算法分類（計(jì)算時(shí)間）51典型的計(jì)算時(shí)間函數(shù)曲線51典型的計(jì)算時(shí)間函數(shù)曲線52典型的計(jì)算時(shí)間函數(shù)曲線當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行具有比Ο(nlogn)復(fù)雜度還高的算法是比較困難的。指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。要想在順序處理機(jī)上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度。52典型的計(jì)算時(shí)間函數(shù)曲線當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)53計(jì)算時(shí)間函數(shù)值比較53計(jì)算時(shí)間函數(shù)值比較54算法復(fù)雜性分析2）下界函數(shù)定義1.2如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有

|f(n)|≥c|g(n)|

則記作f(n)=Ω(g(n))含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是不小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界函數(shù)。試圖求出“最大”的g(n)，使得f(n)=Ω(g(n))。54算法復(fù)雜性分析2）下界函數(shù)55Big-omega55Big-omega56算法復(fù)雜性分析2）下界函數(shù)例1：對(duì)于所有的n,有f(n)=3n+2>3n,因此f(n)=Ω(n)

有f(n)=100n+6>100n,因此f(n)=Ω(n)3n+2,100n+6都是帶有下限的線性函數(shù)。例2：對(duì)于所有的n0,有f(n)=9n2+2n+2>9n2,因此f(n)=Ω(n2)

有f(n)=100n2+8n+6>100n2,因此f(n)=Ω(n2)這種下限更有實(shí)際意義56算法復(fù)雜性分析2）下界函數(shù)這種下限更有實(shí)際意義57算法復(fù)雜性分析例2：對(duì)于所有的n0,有f(n)=6*2n+n2>6*2n,因此f(n)=Ω(2n)例3：

3n+2=Ω(1),

6*2n=Ω(1),

6*2n=Ω(n70),6*2n=Ω(n5.5)57算法復(fù)雜性分析例2：58算法復(fù)雜性分析Ω比率定理:對(duì)于函數(shù)f(n)和g(n),若存在，則f(n)=Ω(g(n))對(duì)于確定的常數(shù)c，有例4因?yàn)樗?n+2=Ω(n)

因?yàn)樗?0n2+4n+2=Ω(n2)

因?yàn)樗?*2n+n2=Ω(2n)

因?yàn)樗?n2+5

Ω(n3)58算法復(fù)雜性分析Ω比率定理:對(duì)于函數(shù)f(n)和g(n),59算法復(fù)雜性分析3）“平均情況”限界函數(shù)定義1.3如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有

c1|g(n)|≤|f(n)|≤c2|g(n)|

則記作含義：兩個(gè)函數(shù)就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))59算法復(fù)雜性分析3）“平均情況”限界函數(shù)60Big-theta60Big-theta61算法復(fù)雜性分析3）“平均情況”限界函數(shù)例：3n+2=(n),100n+6=(n)10n2+4n+2=(n2),1000n2+10n-6=(n2)6*2n+n2=(2n)

由于3n2+3

O(n)，所以3n2+3

(n)

由于3n2+5

Ω(n3)，所以3n2+5

(n3)61算法復(fù)雜性分析3）“平均情況”限界函數(shù)62算法復(fù)雜性分析3）“平均情況”限界函數(shù)

比率定理:對(duì)于函數(shù)f(n)和g(n),若及存在，則f(n)=

(g