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

1、1算法分析與設(shè)計(jì)2第1章 算法引論1課程學(xué)習(xí)背景 1.1 為什么學(xué)習(xí)算法？1.2 算法的定義1.3 如何描述一個算法？2算法復(fù)雜性分析2.1 計(jì)算模型與算法分析框架2.2 漸進(jìn)表示為什么要學(xué)習(xí)算法算法是計(jì)算機(jī)科學(xué)的基石，是改造世界的有力工具！ 互聯(lián)網(wǎng)是20世紀(jì)最偉大的發(fā)明之一，改變了世界，改變了我們的生活！各種算法在支撐著整個互聯(lián)網(wǎng)的正常運(yùn)行，互聯(lián)網(wǎng)的信息傳輸需要路由選擇算法，互聯(lián)網(wǎng)的信息安全需要加密算法，互聯(lián)網(wǎng)的信息檢索需要模式匹配算法，互聯(lián)網(wǎng)的信息存儲需要排序算法，沒有算法也就沒有互聯(lián)網(wǎng)！學(xué)習(xí)算法可以開發(fā)人們的分析能力 算法是解決問題的一類特殊方法，它是經(jīng)過對問題的準(zhǔn)確理解和定義獲取答案的

2、過程。是你獲得高薪職位的敲門磚！3“微積分以及在微積分基礎(chǔ)上建立起來的數(shù)學(xué)分析體系成就了現(xiàn)代科學(xué)，而算法則成就了現(xiàn)代世界” David Berlinski, 2000思考題：小雞啄米輸入：一個m*n的矩陣A，矩陣的每一個元素都是一個非負(fù)整數(shù)，代表該位置的米數(shù)；有一只小雞從左上角A11出發(fā)，每次往右或者往下走一步，走到右下角Amn停止；小雞會將途中經(jīng)過的所有米粒都吃掉；設(shè)計(jì)一個算法，計(jì)算出小雞應(yīng)該如何走保證吃到的米粒最多。分析算法時間復(fù)雜度。4思考題：小雞啄米假設(shè)有兩只小雞從左上角A11出發(fā)，都要走到右下角Amn，都只能向下或者向右移動；兩只小雞移動的先后順序不做限制，但是先到某個位置的小雞會將

3、該位置米粒吃完；問如何安排兩只小雞的移動順序與軌跡，使得兩只小雞吃到的米粒數(shù)之和最多？如果有k只小雞呢？56為什么要分析算法效率？7算法效率的各個方面時間效率排序算法效率空間效率路由器與布隆過濾器（bloom filter）通訊量效率比特幣與稀疏恢復(fù)MapReduce與DSP模型8第1章 算法引論1課程學(xué)習(xí)背景 1.1 為什么學(xué)習(xí)算法？1.2 算法的定義1.3 如何描述一個算法？2算法復(fù)雜性分析2.1 計(jì)算模型與算法分析框架2.2 漸進(jìn)表示什么是算法？簡單說來，算法就是問題的程序化解決方案。定義：算法就是一個定義良好的可計(jì)算過程，它取一個或者一組值作為輸入，并產(chǎn)生出一個或者一組值作為輸出。即，

4、算法就是一系列的計(jì)算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。algorithmInputComputational ProcedureOutput“冒泡”排序是個計(jì)算過程9什么是算法？一個算法通常具有如下特征：輸 入：一個算法具有零個或者多個取自指定集合的輸入值；輸 出：對算法的每一次輸入，算法具有一個或多個與輸入值相聯(lián)系的輸出值；確定性：算法的每一個指令步驟都是明確的；有限性：對算法的每一次輸入，算法都必須在有限步驟（即有限時間）內(nèi)結(jié)束；正確性：對每一次輸入，算法應(yīng)產(chǎn)生出正確的輸出值；通用性：算法的執(zhí)行過程可應(yīng)用于所有同類求解問題，而不是僅適用于特殊的輸入。10相關(guān)概念：問題和問題實(shí)例問題（Pr

5、oblem）：規(guī)定了輸入與輸出之間的關(guān)系，可以用通用語言來描述；問題實(shí)例：某一個問題的實(shí)例包含了求解該問題所需的輸入；排序問題將一系列數(shù)按非降順序進(jìn)行排序排序問題的一個實(shí)例：11輸入: 由n個數(shù)組成的一個序列輸出: 對輸入系列的一個排列(重排） ，使得Input: Output: 相關(guān)概念：問題和問題實(shí)例算法可求解的問題：人類基因項(xiàng)目在電子商務(wù)中的應(yīng)用在互聯(lián)網(wǎng)中的應(yīng)用（圖像檢索、視頻檢索）.重要問題類型：排序、查找、字符串處理、圖問題、組合問題、幾何問題、數(shù)值問題等。12相關(guān)概念：輸入實(shí)例與問題規(guī)模輸入實(shí)例：問題的具體計(jì)算例子如，排序問題的3個輸入實(shí)例：13,5,6,37,8,92,1243,

6、5,23,76,2553,67,32,42,22,33,4,39,56問題規(guī)模：算法的輸入實(shí)例大小。如，上面排序問題的3個輸入實(shí)例的規(guī)模大小分別為7,5,913相關(guān)概念：正確算法與不正確算法正確的算法 如果一個算法對問題每一個輸入實(shí)例，都能輸出正確的結(jié)果并停止，則稱它為正確的。不正確的算法可能根本不會停止；停止時給出的不是預(yù)期的結(jié)果；如果算法的錯誤率可以控制，也是有用的。14作為一種技術(shù)的算法15如果計(jì)算機(jī)無限快、存儲器都是免費(fèi)的,算法研究是否還需要？Yes！證明方案是正確的，可以給出正確結(jié)果。Yes！希望自己的實(shí)現(xiàn)符合良好的軟件工程實(shí)踐要求，采用最容易的實(shí)現(xiàn)方法。算法對于當(dāng)代計(jì)算機(jī)非常重要！

7、類比硬件與軟件的不同，算法的迥異帶來的意義可能更明顯！比如，對100萬個數(shù)字進(jìn)行排序：插入排序: 計(jì)算機(jī)A: 109 指令/s世界最好的程序員器語言歸并排序: 計(jì)算機(jī)B: 107 指令/s普通程序員高級語言+低效編譯器問題求解基礎(chǔ)16理解問題決定：計(jì)算方法；精確或近似解法；數(shù)據(jù)結(jié)構(gòu)；算法設(shè)計(jì)技術(shù)設(shè)計(jì)算法正確性證明分析算法根據(jù)算法寫代碼 算法設(shè)計(jì)和分析過程問題求解基礎(chǔ)求解過程說明：理解問題：是否屬于已知問題？確定算法輸入范圍；了解計(jì)算設(shè)備的性能：清楚速度和計(jì)算資源的限制；在精確解法和近似解法之間做選擇：有時近似算法是唯一選擇；確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)算法的設(shè)計(jì)技術(shù)：這是本課程學(xué)習(xí)重點(diǎn)和目標(biāo)；算法的描述

8、：自然語言、流程圖、偽代碼；算法的正確性證明：證明對于所有合法輸入均能產(chǎn)生正確結(jié)果；算法的分析：分析執(zhí)行效率（時間和空間）、簡單性、一般性；為算法寫代碼：利用編程語言以計(jì)算機(jī)程序行使實(shí)現(xiàn)；1718第1章 算法引論1課程學(xué)習(xí)背景 1.1 學(xué)習(xí)動機(jī)1.2 算法定義1.3 算法描述2算法復(fù)雜性分析2.1 計(jì)算模型與算法分析框架2.2 漸進(jìn)表示算法描述方法偽代碼擁有自然語言和類編程語言特性，經(jīng)常被用于算法描述；與真實(shí)代碼(real code)的差異:對特定算法的描述更加的清晰與精確；不需要考慮太多技術(shù)細(xì)節(jié)（數(shù)據(jù)抽象、模塊、錯誤處理等）；用偽代碼可以體現(xiàn)算法本質(zhì)；永遠(yuǎn)不會過時；19算法描述方法20偽代碼

9、的一些約定：書寫上的“縮進(jìn)”(縮排)表示程序中的分程序（程序塊）結(jié)構(gòu)；循環(huán)結(jié)構(gòu)(while, for, repeat) 和條件結(jié)構(gòu) (if, then, else) 與Pascal, C語言類似；“/ ” or “ ”來表示注釋；利用ije 來表示多重賦值，等價于 je 和ij.變量是局部于給定過程的。數(shù)組元素的訪問方式: Ai ; A1 . j = 符合數(shù)據(jù)一般組織成對象，由屬性（attribute）或域(field)所組成；域的訪問是由域名后跟方括號括住的對象名形式來表示, 如lengthA；參數(shù)采用按值傳遞方式；布爾操作 “and” 和“or”具有短路能力: 如 “ x and (or)

10、 y ”: 無論y的值如何，必須首先計(jì)算x的值。插入排序的偽代碼問題: 把一系列數(shù)據(jù)按非遞增的順序排列輸入: n 個輸入數(shù)輸出: 輸入系列的一個排序 ，使得INSERTION-SORT(A)1for( j = 2; j 0 & Ai key)5Ai+1 = Ai6i = i-17Ai+1 = key2122第1章 算法引論1課程學(xué)習(xí)背景 1.1 學(xué)習(xí)動機(jī)1.2 算法定義1.3 算法描述2算法復(fù)雜性分析2.1 計(jì)算模型與算法分析框架2.2 漸進(jìn)表示算法分析框架算法分析是指對一個算法所需要的資源進(jìn)行預(yù)測，通常是對計(jì)算時間和空間的預(yù)測。算法分析的目的是為了從多個候選算法中選擇一個最有效的算法，或去掉

11、較差的算法。進(jìn)行算法分析之前，首先要確立有關(guān)實(shí)現(xiàn)技術(shù)的模型，通常采用隨機(jī)存取機(jī)（RAM）計(jì)算模型。默認(rèn)情況下，算法分析一般是指對算法時間效率的分析。23RAM模型24RAM模型（內(nèi)存模型）RAM（Random Access machine）：隨機(jī)訪問機(jī)Unit cost assumption模型簡單，應(yīng)用廣泛25CPU內(nèi)存26內(nèi)存層級現(xiàn)代計(jì)算機(jī)的存儲由多層級組成hierarchy層級離CPU越遠(yuǎn)，速度越慢，存儲容量越大不同層級之間以塊（block）的形式移動數(shù)據(jù)內(nèi)存L1L227Slow I/ODisk access is 106 times slower than main memory ac

12、cesstrackmagnetic surfaceread/write arm“The difference in speed between modern CPU and disk technologies is analogous to the difference in speed in sharpening a pencil using a sharpener on ones desk or by taking an airplane to the other side of the world and using a sharpener on someone elses desk.”

13、 (D. Comer)4835 1915 5748 4125data sizerunning timeI/O模型（外存模型）去掉Unit cost assumption以塊（block）形式讀取磁盤數(shù)據(jù)28CPU磁盤內(nèi)存Block數(shù)據(jù)流模型數(shù)據(jù)流是一個由海量數(shù)據(jù)組成的數(shù)據(jù)序列Single Pass: 每個數(shù)據(jù)最多訪問一次Small Space: 存儲空間非常小Small time: 更新(插入刪除)速度快CPU內(nèi)存：數(shù)據(jù)摘要回答近似查詢頻繁項(xiàng)有哪些/數(shù)據(jù)分布是什么/Top-K是什么？算法分析框架算法運(yùn)行時間是指在特定輸入時，所執(zhí)行的基本操作數(shù)。輸入數(shù)據(jù)的規(guī)模和分布是影響算法運(yùn)行時間的兩個主要因

14、素。 算法時間效率分析框架：算法時間效率用算法輸入規(guī)模n為參數(shù)的函數(shù)來度量；對輸入規(guī)模相同情況下，有些算法的時間效率會有明顯差異。對于這樣的算法要區(qū)分最壞運(yùn)行時間、最佳運(yùn)行時間、平均運(yùn)行時間；對于大規(guī)模輸入，通常只關(guān)注運(yùn)行時間效率函數(shù)的增長率，即只關(guān)注函數(shù)的高階項(xiàng)，而忽略低階項(xiàng)和高階項(xiàng)系數(shù)。30算法分析框架對于規(guī)模為n的任何輸入，一般考察算法的最壞運(yùn)行時間：最壞情況運(yùn)行時間是在任何輸入情況下的一個上界；對于某些算法來說，最壞情況出現(xiàn)還是比較頻繁的，如信息檢索（信息經(jīng)常不存在）；大致上看，“平均情況”通常和最壞情況一樣差。平均運(yùn)行時間（期望運(yùn)行時間）概率分析技術(shù)( probabilistic a

15、nalysis ) 隨機(jī)化算法( randomized algorithm )函數(shù)的增長率抽象簡化。忽略每條語句的真實(shí)代價，用常量c來表示；進(jìn)一步忽略了抽象的代價；增長率或增長量級。只考慮公式中的最高項(xiàng)，忽略最高項(xiàng)系數(shù)和低階項(xiàng)；31插入排序問題: 把一系列數(shù)據(jù)按非遞增的順序排列輸入: n 個輸入數(shù)輸出: 輸入系列的一個排序 ，使得32INSERTION-SORT(A)1for( j = 2; j 0 & Ai key)6Ai+1 = Ai7i = i-18Ai+1 = key33插入排序插入排序總運(yùn)行時間：34如果數(shù)組是排好序的，則會出現(xiàn)最好情況：如果數(shù)組是逆序排序的，則會出現(xiàn)最差情況： 此時

16、必須將每個元素Aj與整個已排序的子數(shù)組A1.j-1中的每一個元素進(jìn)行比較，對j=2,3,n,有tj=j. 則有：35插入排序DBSCAN的故事DBSCAN，英文全寫為Density-based spatial clustering of applications with noise ，是在 1996 年由Martin Ester, Hans-Peter Kriegel, Jrg Sander 及 Xiaowei Xu 提出的聚類分析算法， 這個算法是以密度為本的：給定某空間里的一個點(diǎn)集合，這算法能把附近的點(diǎn)分成一組（有很多相鄰點(diǎn)的點(diǎn)），并標(biāo)記出位于低密度區(qū)域的局外點(diǎn)（最接近它的點(diǎn)也十分遠(yuǎn)）D

17、BSCAN 是其中一個最常用的聚類分析算法，也是其中一個科學(xué)文章中最常引用的。在 2014 年，這個算法在領(lǐng)頭數(shù)據(jù)挖掘會議ACM SIGKDD 上獲頒發(fā)了 Test of Time award，該獎項(xiàng)是頒發(fā)給一些于理論及實(shí)際層面均獲得持續(xù)性的關(guān)注的算法。36DBSCAN的故事2015年的數(shù)據(jù)庫頂級會議ACM SIGMOD的最佳論文“DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation”中，Junhao Gan和Yufei Tao發(fā)現(xiàn)，DBSCAN的算法時間復(fù)雜度有誤DBSCAN原作者認(rèn)為算法時間復(fù)雜度是O(n log n)的

18、，而實(shí)際上是O(n2)該論文在數(shù)據(jù)挖掘領(lǐng)域和數(shù)據(jù)庫領(lǐng)域都引起論戰(zhàn)后來，很多數(shù)據(jù)挖掘的學(xué)者為DBSCAN辯護(hù)稱，雖然其最壞情況時間復(fù)雜度是O(n2)，但是其平均時間復(fù)雜度是O(n log n)的理由：假設(shè)所有點(diǎn)是均勻分布的前提下，算法的時間復(fù)雜度是O(n log n)的其實(shí)這仍然不對，為什么？故事的意義：算法的時間復(fù)雜度非常關(guān)鍵，受到研究領(lǐng)域的極大重視即使一個經(jīng)典的算法/論文/定理，仍然有出現(xiàn)錯誤的可能，需要自己多思考3738第1章 算法引論1課程學(xué)習(xí)背景 1.1 學(xué)習(xí)動機(jī)1.2 算法定義1.3 算法描述2算法復(fù)雜性分析2.1 計(jì)算模型與算法分析框架2.2 漸進(jìn)表示39算法復(fù)雜性分析計(jì)算時間的漸

19、近表示記：兩個算法的計(jì)算時間為函數(shù)f(n)與g(n)其中， n 輸入或輸出規(guī)模的某種測度。以下給出算法執(zhí)行時間：上界（）、下界（）、平均（ ）、低階(o)的定義。40算法復(fù)雜性分析1）上界函數(shù)定義1.1 如果存在兩個正常數(shù)c和n0，對于所有的nn0，有 0 f(n) c*g(n) 則記作f(n) = (g(n)含義：如果算法用 n 值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是小于|g(n)|的一個常數(shù)倍。則g(n)是計(jì)算時間f(n)的一個上界函數(shù)。 f(n)的數(shù)量級就是g(n)。試圖求出最小的g(n)，使得f(n) = (g(n)。41Big-oh42算法復(fù)雜性分析1）上界函數(shù)例1 線

20、性函數(shù) f(n)=3n+2 當(dāng)n2時， 3n+2 3n+n=4n，故f(n)=O(n) 當(dāng)n0時， 3n+2 10n，故f(n)=O(n)例2 平方函數(shù) f(n)=10n2 + 4n+2 當(dāng)n 2時， f(n) 10n2 + 5n ，故f(n)=O(n2) 當(dāng)n 5時， f(n) 10n2 + n2 = 11n2 ，故f(n)=O(n2)C=4,n0=2C=10,n0=0C=10,n0=2C=10,n0=543算法復(fù)雜性分析1）上界函數(shù)例3 指數(shù)函數(shù) f(n)=6*2n+n2 當(dāng)n 4時， n2 2n， f(n) 6*2n+2n= 7*2n ， 故f(n)=O(2n)例4 常數(shù)函數(shù) f(n)=

21、9 9*1 故f(n)=O(1) f(n)=2011 2011*1 故f(n)=O(1)C=7,n0=4C=9, n0=0C=2011, n0=044算法復(fù)雜性分析1）上界函數(shù)例5 松散界限 f(n)=3n+3 當(dāng)n 2時， f(n) 3n2，故f(n)=O(n2)例6 錯誤界限 f(n)=9 *n+2O(1) n2不是最小上限不存在c0及n045算法復(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),

22、其中C是一個正的常數(shù). (6) f=(f)46算法復(fù)雜性分析多項(xiàng)式定理:定理1 若A(n) = amnm+a1n+a0是一個m次多項(xiàng) 式，則有A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多 項(xiàng)式的最高階nm同階。 證明：取n0=1,當(dāng)nn0時，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 則，定理得證。47算法復(fù)雜性分析大O比率定理: 對于函數(shù)f(n)和g(n),若 存在，則f(n)=O ( g(n) )當(dāng)且僅當(dāng)存在確定的常數(shù)c，

23、有證明：如果f(n)=O ( g(n) )，則存在c0及某個n0, 使得對于所有的nn0，有f(n)/ g(n)c，因此 假定 ，它表明存在一個n0 ， 使得對于所有的nn0，有f(n) max1,c*g(n).48算法復(fù)雜性分析例7 因?yàn)?所以3n+2= O(n) 因?yàn)?所以 10n2 + 4n+2= O(n2) 因?yàn)?所以6*2n+n2 = O(2n) 因?yàn)?所以3n+3 = O(n2) 因?yàn)?所以3n2+3 O(n)49算法復(fù)雜性分析計(jì)算時間的數(shù)量級對算法有效性的影響 數(shù)量級的大小對算法的有效性有決定性的影響。 例：假設(shè)解決同一個問題的兩個算法，它們都有n個輸入，計(jì)算時間的數(shù)量級分別是n

24、2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和22528次運(yùn)算。 分析：在n加倍的情況下，一個(n2)的算法計(jì)算時間增長4 倍，而一個(nlogn)算法則只用兩倍多一點(diǎn)的時間即 可完成。50算法復(fù)雜性分析算法分類（計(jì)算時間）多項(xiàng)式時間算法：可用多項(xiàng)式（函數(shù)）對其計(jì)算時間限界的算法。 常見的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3)指數(shù)時間算法：計(jì)算時間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時間限界函數(shù)： (2n) (n！) 3n, 因此 f(n)= (n) 有f(n)=100n+6100

25、n,因此 f(n)= (n) 3n+2, 100n+6 都是帶有下限的線性函數(shù)。例2：對于所有的n0,有f(n)=9n2+2n+29n2, 因此f(n)= (n2) 有f(n)=100n2+8n+6100n2, 因此f(n)= (n2)這種下限更有實(shí)際意義57算法復(fù)雜性分析例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)58算法復(fù)雜性分析比率定理: 對于函數(shù)f(n)和g(n),若 存在，則f(n)= ( g(n) )對于確定的常數(shù)c，有例4 因?yàn)?所以3n+2=(n) 因?yàn)?所以10n2+4n+2=(n2) 因?yàn)?所以6*2n+n2=(2n) 因?yàn)?所以3n2+5(n3) 59算法復(fù)雜性分析3）“平均情況”限界函數(shù)定義1.3 如果存在正常數(shù)c1，c2和n0，對于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)| 則記作含義：兩個函數(shù)就一個常數(shù)因子范圍內(nèi)而言是相同的。可看作： 既有f(n) = (g(n)，又有f(n) = (g(n)60Big-theta61算法復(fù)雜性分析3）“平均情況”限界函數(shù)例