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

互聯網是20世紀最偉大的發明之一，改變了世界，改變了我們的生活！各種算法在支撐著整個互聯網的正常運行，互聯網的信息傳輸需要路由選擇算法，互聯網的信息安全需要加密算法，互聯網的信息檢索需要模式匹配算法，互聯網的信息存儲需要排序算法，……，沒有算法也就沒有互聯網！學習算法可以開發人們的分析能力

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

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

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

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

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

來表示多重賦值，等價于

j←e

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

把一系列數據按非遞增的順序排列輸入:n個輸入數輸出:輸入系列的一個排序，使得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插入排序的偽代碼問題:把一系列數據按非遞增的順序排列I22第1章算法引論1 課程學習背景1.1學習動機1.2算法定義1.3算法描述2 算法復雜性分析2.1計算模型與算法分析框架2.2漸進表示22第1章算法引論1 課程學習背景算法分析框架算法分析是指對一個算法所需要的資源進行預測，通常是對計算時間和空間的預測。算法分析的目的是為了從多個候選算法中選擇一個最有效的算法，或去掉較差的算法。進行算法分析之前，首先要確立有關實現技術的模型，通常采用隨機存取機（RAM）計算模型。默認情況下，算法分析一般是指對算法時間效率的分析。23算法分析框架算法分析是指對一個算法所需要的資源進行預測，通常RAM模型

24RAM模型

24RAM模型（內存模型）RAM（RandomAccessmachine）：隨機訪問機Unitcostassumption模型簡單，應用廣泛25CPU內存RAM模型（內存模型）RAM（RandomAccessm26內存層級現代計算機的存儲由多層級組成hierarchy層級離CPU越遠，速度越慢，存儲容量越大不同層級之間以塊（block）的形式移動數據內存L1L226內存層級LL27SlowI/ODiskaccessis106timesslowerthanmainmemoryaccesstrackmagneticsurfaceread/writearm“ThedifferenceinspeedbetweenmodernCPUanddisktechnologiesisanalogoustothedifferenceinspeedinsharpeningapencilusingasharpeneronone’sdeskorbytakinganairplanetotheothersideoftheworldandusingasharpeneronsomeoneelse’sdesk.”

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

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

把一系列數據按非遞增的順序排列輸入:n個輸入數輸出:輸入系列的一個排序，使得32插入排序問題:把一系列數據按非遞增的順序排列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插入排序插入排序總運行時間：34插入排序總運行時間：34如果數組是排好序的，則會出現最好情況：如果數組是逆序排序的，則會出現最差情況：

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

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

f(n)≤c*g(n)

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

當n2時，3n+23n+n=4n，故f(n)=O(n)

當n>0時，3n+210n，故f(n)=O(n)例2[平方函數]f(n)=10n2+

4n+2

當n2時，f(n)10n2+

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

當n5時，f(n)10n2+

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

當n4時，n22n，f(n)6*2n+2n=7*2n

，故f(n)=O(2n)例4[常數函數]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算法復雜性分析1）上界函數C=7,n0=4C=9,n044算法復雜性分析1）上界函數例5[松散界限]f(n)=3n+3

當n2時，f(n)

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

n2不是最小上限不存在c>0及n044算法復雜性分析1）上界函數n2不是最小上限不存在c>0及45算法復雜性分析1）上界函數有如下運算規則：

(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是一個正的常數.(6)f=Ο(f)45算法復雜性分析1）上界函數46算法復雜性分析多項式定理:定理1若A(n)=amnm+…+a1n+a0是一個m次多項式，則有A(n)=Ο(nm)

即：變量n的固定階數為m的任一多項式，與此多項式的最高階nm同階。證明：取n0=1,當n≥n0時，有

|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算法復雜性分析多項式定理:47算法復雜性分析大O比率定理:對于函數f(n)和g(n),若存在，則f(n)=O(g(n))當且僅當存在確定的常數c，有證明：如果f(n)=O(g(n))，則存在c>0及某個n0,

使得對于所有的nn0，有f(n)/g(n)c，因此假定，它表明存在一個n0，使得對于所有的nn0，有f(n)max{1,c}*g(n).47算法復雜性分析大O比率定理:對于函數f(n)和g(n)48算法復雜性分析例7因為

所以3n+2=O(n)

因為

所以10n2+

4n+2=O(n2)

因為

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

因為

所以3n+3=O(n2)

因為

所以3n2+3O(n)48算法復雜性分析例7因為49算法復雜性分析計算時間的數量級對算法有效性的影響數量級的大小對算法的有效性有決定性的影響。例：假設解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數量級分別是n2和nlogn。則，

n=1024：分別需要1048576和10240次運算。

n=2048：分別需要4194304和22528次運算。分析：在n加倍的情況下，一個Ο(n2)的算法計算時間增長4

倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。49算法復雜性分析計算時間的數量級對算法有效性的影響50算法復雜性分析算法分類（計算時間）多項式時間算法：可用多項式（函數）對其計算時間限界的算法。常見的多項式限界函數有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數時間算法：計算時間用指數函數限界的算法常見的指數時間限界函數：

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

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

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

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

有f(n)=100n2+8n+6>100n2,因此f(n)=Ω(n2)這種下限更有實際意義56算法復雜性分析2）下界函數這種下限更有實際意義57算法復雜性分析例2：對于所有的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算法復雜性分析例2：58算法復雜性分析Ω比率定理:對于函數f(n)和g(n),若存在，則f(n)=Ω(g(n))對于確定的常數c，有例4因為所以3n+2=Ω(n)

因為所以10n2+4n+2=Ω(n2)

因為所以6*2n+n2=Ω(2n)

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

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

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

由于3n2+3O(n)，所以3n2+3(n)

由于3n2+5Ω(n3)，所以3n2+5(n3)61算法復雜性分析3）“平均情況”限界函數62算法復雜性分析3）“平均情況”限界函數比率定理:對于函數f(n)和g(n),若及存在，則f(n)=(g(n))當且僅當存在確定的常數c，有及例：因為且所以3n+2=(n)62算法復雜性分析3）“平均情況”限界函數63算法復雜性分析4）“低階”與“高階”限界函數定義1.4如果對于任意給定的>0，都存在正整數n0，于所有的n≥n0，有

f(n)/g(n)<

則記作f(n)=o(g(n))含義：當n充分大時，f(n)的階比g(n)的階低。例如：3n+2=o(n2)4NlogN+7=o(3N2+4NlogN+7)63算法復雜性分析4）“低階”與“高階”限界函數64算法復雜性分析4）“低階”與“高階”限界函數定義1.5如果對于任意給定的>0，都存在正整數n0，于所有的n≥n0，有

g(n)/f(n)<

則記作f(n)=ω(g(n))含義：當n充分大時，f(n)的階比g(n)的階高。例如：3n3+2=ω(n2)4N2logN+7=ω(3N+4NlogN+7)64算法復雜性分析4）“低階”與“高階”限界函數65算法復雜性分析5）限界函數的性質1）若fО(g)且gО(h)，則fО(h)。即О具有傳遞性。（、同）2）fО(g)當且僅當g

(f)3）若f(g)，則g

(f)。即定義了一個等價關系（等價類）65算法復雜性分析5）限界函數的性質66算法復雜性分析

5.常用的整數求和公式在算法分析中，在統計語句的頻率時，求和公式的一般表示形式為：其中f(i)是一個帶有有理數系數且以i為變量的多項式。66算法復雜性分析5.常用的整數求和公式67算法復雜性分析

如：67算法復雜性分析如：f(n)漸近符號(可以是符號O、、之一）E1c(1)E2(nk)E3(n2)E4(n3)E5(nk+1)E6(rn)E7n!((n/e)n)E8(logn)68f(n)漸近符號(可以是符號O、、之一）E169

語句頻率總步數TSum(Ta[],intn)0(0){0(0)Ttsum=0;1(1)for(intI=0;I<n;I++)n+1(n)

tsum+=a[I];n(n)returntsum;1(1)}0(0)復雜性分析舉例：69語句頻率總步數TSum(Ta[],intn)70總結

1算法基本概念

2復雜性分析方法與手段70總結1算法基本概念71Thankyou!71Thankyou!72算法分析與設計1算法分析與設計73第1章算法引論1 課程學習背景1.1為什么學習算法？1.2算法的定義1.3如何描述一個算法？2 算法復雜性分析2.1計算模型與算法分析框架2.2漸進表示2第1章算法引論1 課程學習背景為什么要學習算法算法是計算機科學的基石，是改造世界的有力工具！

互聯網是20世紀最偉大的發明之一，改變了世界，改變了我們的生活！各種算法在支撐著整個互聯網的正常運行，互聯網的信息傳輸需要路由選擇算法，互聯網的信息安全需要加密算法，互聯網的信息檢索需要模式匹配算法，互聯網的信息存儲需要排序算法，……，沒有算法也就沒有互聯網！學習算法可以開發人們的分析能力

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

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

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

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

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

來表示多重賦值，等價于

j←e

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

把一系列數據按非遞增的順序排列輸入:n個輸入數輸出:輸入系列的一個排序，使得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]=key92插入排序的偽代碼問題:把一系列數據按非遞增的順序排列I93第1章算法引論1 課程學習背景1.1學習動機1.2算法定義1.3算法描述2 算法復雜性分析2.1計算模型與算法分析框架2.2漸進表示22第1章算法引論1 課程學習背景算法分析框架算法分析是指對一個算法所需要的資源進行預測，通常是對計算時間和空間的預測。算法分析的目的是為了從多個候選算法中選擇一個最有效的算法，或去掉較差的算法。進行算法分析之前，首先要確立有關實現技術的模型，通常采用隨機存取機（RAM）計算模型。默認情況下，算法分析一般是指對算法時間效率的分析。94算法分析框架算法分析是指對一個算法所需要的資源進行預測，通常RAM模型

95RAM模型

24RAM模型（內存模型）RAM（RandomAccessmachine）：隨機訪問機Unitcostassumption模型簡單，應用廣泛96CPU內存RAM模型（內存模型）RAM（RandomAccessm97內存層級現代計算機的存儲由多層級組成hierarchy層級離CPU越遠，速度越慢，存儲容量越大不同層級之間以塊（block）的形式移動數據內存L1L226內存層級LL98SlowI/ODiskaccessis106timesslowerthanmainmemoryaccesstrackmagneticsurfaceread/writearm“ThedifferenceinspeedbetweenmodernCPUanddisktechnologiesisanalogoustothedifferenceinspeedinsharpeningapencilusingasharpeneronone’sdeskorbytakinganairplanetotheothersideoftheworldandusingasharpeneronsomeoneelse’sdesk.”

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

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

把一系列數據按非遞增的順序排列輸入:n個輸入數輸出:輸入系列的一個排序，使得103插入排序問題:把一系列數據按非遞增的順序排列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]=key104插入排序INSERTION-SORT(A)33插入排序插入排序總運行時間：105插入排序總運行時間：34如果數組是排好序的，則會出現最好情況：如果數組是逆序排序的，則會出現最差情況：

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

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

f(n)≤c*g(n)

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

當n2時，3n+23n+n=4n，故f(n)=O(n)

當n>0時，3n+210n，故f(n)=O(n)例2[平方函數]f(n)=10n2+

4n+2

當n2時，f(n)10n2+

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

當n5時，f(n)10n2+

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

當n4時，n22n，f(n)6*2n+2n=7*2n

，故f(n)=O(2n)例4[常數函數]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算法復雜性分析1）上界函數C=7,n0=4C=9,n0115算法復雜性分析1）上界函數例5[松散界限]f(n)=3n+3

當n2時，f(n)

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

n2不是最小上限不存在c>0及n044算法復雜性分析1）上界函數n2不是最小上限不存在c>0及116算法復雜性分析1）上界函數有如下運算規則：

(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是一個正的常數.(6)f=Ο(f)45算法復雜性分析1）上界函數117算法復雜性分析多項式定理:定理1若A(n)=amnm+…+a1n+a0是一個m次多項式，則有A(n)=Ο(nm)

即：變量n的固定階數為m的任一多項式，與此多項式的最高階nm同階。證明：取n0=1,當n≥n0時，有

|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算法復雜性分析多項式定理:118算法復雜性分析大O比率定理:對于函數f(n)和g(n),若存在，則f(n)=O(g(n))當且僅當存在確定的常數c，有證明：如果f(n)=O(g(n))，則存在c>0及某個n0,

使得對于所有的nn0，有f(n)/g(n)c，因此假定，它表明存在一個n0，使得對于所有的nn0，有f(n)max{1,c}*g(n).47算法復雜性分析大O比率定理:對于函數f(n)和g(n)119算法復雜性分析例7因為

所以3n+2=O(n)

因為

所以10n2+

4n+2=O(n2)

因為

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

因為

所以3n+3=O(n2)

因為

所以3n2+3O(n)48算法復雜性分析例7因為120算法復雜性分析計算時間的數量級對算法有效性的影響數量級的大小對算法的有效性有決定性的影響。例：假設解決同一個問題的兩個算法，它們都有n個輸入，計算時間的數量級分別是n2和nlogn。則，

n=1024：分別需要1048576和10240次運算。

n=2048：分別需要4194304和22528次運算。分析：在n加倍的情況下，一個Ο(n2)的算法計算時間增長4

倍，而一個Ο(nlogn)算法則只用兩倍多一點的時間即可完成。49算法復雜性分析計算時間的數量級對算法有效性的影響121算法復雜性分析算法分類（計算時間）多項式時間算法：可用多項式（函數）對其計算時間限界的算法。常見的多項式限界函數有：

Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)指數時間算法：計算時間用指數函數限界的算法常見的指數時間限界函數：

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

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

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