103課程算法課件

1、第一章 緒論2012年秋季學期ComuterAlorithms-roductiontoDesignandysis，SaraBasse,AllenVanGelder，高等教育1.1roduction算法不僅是計算機科學的一個分支，它更是計算機科學的，而且，可以毫不夸張地說，它和絕大多數(shù)的科學、商業(yè)和技術(shù)都是相關(guān)的David Harel算法：計算的算法可以解決哪些問題找出人類DNA中所有100000中，確定人類DNA的30億種化學基對的各種序列快速地和檢索互聯(lián)網(wǎng)數(shù)據(jù)電子商務(wù)活動中各種信息的加密及簽名制造業(yè)中各種資源的有效分配確定地圖中兩地之間的最短路徑各種數(shù)學、幾何計算（矩陣、方程、集合）旅行商問

2、題有n個城市,已知任意2城市之間的距離, 一名推銷員要拜訪這n個城市，如何找到在拜訪每個地點一次后再回到起點的最短路徑。在一個圖中，從圖的一個頂點出發(fā)，沿著圖中的邊，經(jīng)過所有頂點各一次，這條路線就稱之為路；如果最終又回到了起點，則稱為回路。有最短回路的圖稱之為回路即是要求所有圖?；芈分凶疃痰囊粭l路徑。方法一找出所有可能的回路計算所有找出最短的回路的路徑長度回路窮舉法的時間復(fù)雜度O(n!)n=21,21!=5.11*1019,設(shè)每條路徑需要CPU時間1ns，需要1620多年才能完成方法二一步步回溯，有好的下來回路就保留A21123B12E183CD4分支限界法分支限界法類似于回溯法，也是一種在問

3、題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標不同?；厮莘ǖ那蠼饽繕耸钦页鯰中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。A22113B8E方法三1123A分支限界法CD24B81 3CE CDE4D12 34312E C D1244123CD CEE211AAA目前最短的回路長度=19A22113B8E方法二1123A分支限界法CD24B81 3CE CDE4D12 34312E C D1244123CD CEE211AAA目前最短的回路長度=

4、13G 鄰接矩陣V 棧W 保存最短路徑圖b 表示點是否進棧top 為棧頂指針，p為當前查看結(jié)點，L為當前路徑長度方法四貪心算每次選擇最近的點，總代價會比較小，但是局部最優(yōu)，不一定是全局最優(yōu)解。A12213B8E1123CD4方法五圖的規(guī)模更大采用分治的：將一個大的區(qū)域分成多個小區(qū)域，分別求出每一個小區(qū)域的最優(yōu)解，并以最優(yōu)的方式將各個區(qū)域連接起來本課程主要內(nèi)容介紹、研究、分析計算機解決問題常用的一些算法算法的時間和空間分析算法設(shè)計的技術(shù)：分治、貪心、深度優(yōu)先搜索、動態(tài)規(guī)劃等研究問題本身的計算復(fù)雜性plete問題啟發(fā)式算法說明描述工具JAVA1.2節(jié)相關(guān)數(shù)學知識-1.3節(jié)上述2節(jié)+基本的數(shù)據(jù)結(jié)構(gòu)知

5、識自己復(fù)習補習1.4yzingAlgorithmsandProblems算法評價的準則：（1）正確性（2）時間（3）空間（4）簡單性、清晰性（5）優(yōu)化正確性證明對于每一個合法的輸入，該算法都會在有限的時間內(nèi)輸出一個滿足要求的結(jié)果。算法：方法和指令序列確定輸入和輸出的關(guān)系一般方法：數(shù)學歸納法正確性證明的內(nèi)容方法的正確性證明算法思路的正確性。證明一系列與算法的工作對象有關(guān)的引理、定理以及公式。程序的正確性證明證明所給出的一系列指令確實做了所要求的工作。程序正確性證明的方法：大型程序的正確性證明可以將它分解為小的相互獨立的互不相交的模塊，分別驗證。小模塊程序可以使用以下方法驗證：數(shù)學歸納法、軟件形式

6、方法等1.4.2 Amount of work done算法本身選用的策略問題的規(guī)模書寫程序的語言編譯產(chǎn)生的機器代碼質(zhì)量機器執(zhí)行指令的速度一個特定算法的運行工作量只依賴于問題的規(guī)模算法時間復(fù)雜度1.4.2 Amount of work done從算法中選取一種對于所研究來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。T(n)=O(f(n)隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。原操作執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。1.4.2 Amount of work done問題

7、基本操作Find x in an array of namesComparison of x win entryhe arrayMultiply two matriwithMultiplication of two realreal entriesnumbersSort an array of numbersComparison of two array entries1.4.3平均和情況分析算法的時間復(fù)雜性問題的規(guī)模+具體的輸入情況情況下的時間復(fù)雜性| IDn W(n)=maxt(I)平均情況下的時間復(fù)雜性 pr(I )t(I )A(n)=I查找算法為例說明w(n),A(n)1.5 漸進時間

8、復(fù)雜性設(shè)f,g是定義域為自然數(shù)的函數(shù)，f(n)=O(g(n):若存在正數(shù)c和n0，使得對一切nn0,0f(n)cg(n)limf (n) c g(n)n練習f(n)=n3/2, g(n)=37n2+120n+12證明：gO(f),fO(g)設(shè)f,g是定義域為自然數(shù)的函數(shù)，f(n)=(g(n):若存在正數(shù)c和n0，使得對一切 nn0,0cg(n) f(n)limf (n) 0g(n)n設(shè)f,g是定義域為自然數(shù)的函數(shù)，f(n)=(g(n):f(n)=O(g(n), f(n)=(g(n)(g) O(g)O(g)limf (n) c,0 c g(n)no,的定義設(shè)f,g是定義域為自然數(shù)的函數(shù)f(n)=

9、o(g(n):若任意正數(shù)c ,存在n0 ,使得對一切nn0,0f(n) cg(n)f(n)= (g(n):若任意正數(shù)c,存在n0 ,使得對一切nn0,0 cg(n) f(n)O,o,第二種理解法求復(fù)雜性函數(shù)階的極限方法limf (n) s若g(n)n當s0時，f(n)與g(n)同價， f(n) =(g(n)當s=0時，f(n)比g(n)階低， f(n) =O(g(n)當s=無窮時， f(n)比g(n)階高f(n) =(g(n)證明規(guī)則O(f(n)+O(g(n) = O(maxf(n),g(n)對于任意f1(n) O(f(n) ，存在正常數(shù)c1和自然數(shù)n1，使得對所有n n1，有f1(n) c1

10、f(n) 。類似地，對于任意g1(n) O(g(n) ，存在正常數(shù)c2和自然數(shù)n2，使得對所有n n2，有g(shù)1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。則對所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .算法分析中常見的復(fù)雜性函數(shù)小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)最優(yōu)算法問題的計算時間下界為(f(n)，則計算時間復(fù)雜性為O(f(n)的算法是最優(yōu)算法

11、。例如，排序問題的計算時間下界為(nlogn)，計算時間復(fù)雜性為O(nlogn)的排序算法是最優(yōu)算法。堆排序算法是最優(yōu)算法。P與NP問題多項式級的復(fù)雜度：O(1),O(n),O(logn),O(n2)等非多項式級的復(fù)雜度：O(an),O(n！)等P與NP問題P問題-可以由一個確定型圖靈機在多項式表達的時間內(nèi)解決NP問題-其肯定解可以在給定正確信息的多項式時間內(nèi)驗證的判定問題組成或者等效的說，那些解可以在非確定圖靈機上在多項式時間內(nèi)找出合。的集P與NP問題求n個數(shù)的平均數(shù)P問題分解因子問題比如把44427因數(shù)分解，過程復(fù)雜，驗證容易，175*251NP問題回路NP問題P與NP問題P屬于NPP=N

12、P？NP問題不一定都是難解，比如，簡單的數(shù)組排序問題是P類問題，但是P屬于NP，所以也是NP問題Reducibility 約化，歸約一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。求解一個一元一次方程和求解一個一元二次方程：前者可以約化為后者，即知道如何解一個一元二次方程那么一定能解出一元一次方程。Reducibility 約化，歸約問題A可約化為問題B”：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度。即，問題A不比問題B難約化的性質(zhì)：傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C?！翱杉s化”是指的可“多項式

13、地”約化(Polynomial-timeReducible)，問題同時滿足下面兩個條件是一個NP問題；就是問題：(2) 所有的NP問題都可以約化到它。證明一個問題是問題：先證明它是一個NP問題，再證明其中一個已知的問題能約化到它，這樣就可以說它是既然所有的NP問題都能約化成問題了。問題，那么只要任意一個問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了。問題是求NP中判定問題的一個子類比如前面說的回路問題就是一個問題。問題的歷史并，cook在1971年找到了第一個問題，此后人們又陸續(xù)發(fā)現(xiàn)很多可能已經(jīng)有3000多個了。所以，問題，現(xiàn)在一般認為問題是難解間的算法

14、。類似，因為他不太可能存在一個多項式時回路/路徑問題，貨郎擔問題，問題，最小邊覆蓋問題，等等很多問題都是問題，所以都是難解。NP-Hard問題一個問題是NP-Hard問題，如果所有的NP問題都可以約化到它。它滿足問題定義的第二條但不一定要滿足第一條（NP-Hard問題要比問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不的研究范圍，因為它不一定是NP問題。問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問列入即使題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有。的時間復(fù)雜度更高從而更難以解決P真的容易處理嗎？一個需要101000n時間題與一個需要10-100002n時間的問1.一個時間復(fù)雜度n1000與一個時間復(fù)雜度2n/1000的問2.題它只考慮了情況的復(fù)雜度?？赡墁F(xiàn)實世界中的有些3.問題在多數(shù)時候可以在時間n中解決，但是很偶爾你會看到需要時間2n的特例。這個問題可能有一個多項式的平均時間，但情況是指數(shù)式的，所以該問題不屬于P。它只考慮確定性解?？赡苡幸粋€問題你可以很快解決如果你可以接受出現(xiàn)一點誤差的可能，但是確保正確的答案