算法分析與設(shè)計(jì)講稿(1)

1、第 1 頁(yè) 共 148 頁(yè)目錄目錄第一章第一章緒論緒論.31.1 算法的概念.31.2 算法問(wèn)題求解基礎(chǔ).61.3 重要的問(wèn)題類型.91.4 基本數(shù)據(jù)結(jié)構(gòu).11第二章第二章算法效率分析基礎(chǔ)算法效率分析基礎(chǔ).162.1 分析框架.162.2 漸進(jìn)符號(hào)和基本效率類型.192.3 非遞歸算法的數(shù)學(xué)分析.222.4 遞歸算法的數(shù)學(xué)分析.252.5 例：FIBONACCI數(shù)列.27第三章第三章蠻力法（蠻力法（BRUTE FORCE）和算術(shù)問(wèn)題）和算術(shù)問(wèn)題.333.1 選擇排序和冒泡排序.333.2 蠻力字符串匹配.353.3 窮舉搜索（EXHAUSTIVE SEARCH）.363.4 基本算術(shù).403.

2、5 模算術(shù).423.6 素性檢測(cè).423.7 密碼學(xué).42第四章第四章分治法（分治法（DEVIDE-AND-CONQURE）.434.1 主定理（MASTER THEOREM）.434.2 歸并排序.444.3 快速排序.464.4 大整數(shù)乘法.494.5 STRASSEN矩陣乘法.504.6 快速傅里葉變換 FFT.52第五章第五章減治法（減治法（DECRESE-AND-CONQURE）.585.1 插入排序.585.2 深度優(yōu)先搜索和廣度優(yōu)先搜索.595.3 生成組合對(duì)象的算法.635.4 二叉搜索（折半查找）.675.5 乘法和乘方問(wèn)題.695.6 EUCLID算法分析.71第六章第六章

3、時(shí)空權(quán)衡（時(shí)空權(quán)衡（TIME AND SPACE TRADEOFFS）與動(dòng)態(tài)規(guī)劃（）與動(dòng)態(tài)規(guī)劃（DYNAMIC PROGRAMMING）.726.1 計(jì)數(shù)排序.726.2 高效串匹配算法.736.3 再談 FIBONACCI數(shù)列.78第 2 頁(yè) 共 148 頁(yè)6.4 有向無(wú)環(huán)圖中最短路徑.796.5 計(jì)算傳遞閉包的 WARSHALL算法和多源最短路徑問(wèn)題的 FLOYD算法 .816.6 矩陣鏈相乘問(wèn)題.846.7 最優(yōu)二叉搜索樹(shù).866.8 最長(zhǎng)遞增子序列.896.9 編輯距離.896.10 背包問(wèn)題.926.11 旅行商 TSP 問(wèn)題.95第七章第七章貪心法（貪心法（GREEDY TECHN

4、IQUES）.997.1 連續(xù)背包問(wèn)題.997.2 最小生成樹(shù)問(wèn)題（MST，MINIMUM SPANNING TREE）.1027.3 單源最短路徑問(wèn)題的 DIJKSTRA算法.1097.4 HUFFMAN編碼.1127.5 集合覆蓋.118第八章第八章線性規(guī)劃（線性規(guī)劃（LINEAR PROGRAMMING）.1198.1 線性規(guī)劃簡(jiǎn)介.1198.2 求解線性規(guī)劃問(wèn)題的單純形算法.1228.3 網(wǎng)絡(luò)流問(wèn)題.1298.4 二部圖的匹配問(wèn)題.1298.5 對(duì)偶.1298.6 零和游戲.130第九章第九章算法能力的極限算法能力的極限.1319.1 求算法下界的方法.1319.2 問(wèn)題歸約.1329

5、.3 P，NP 和 NP 完全問(wèn)題.1349.4 回溯法（BACKTRACKING）.1399.5 分支限界法（BRANCH-AND-BOUND）.1419.6 近似算法（APPROXIMATION ALGORITHMS）.144第 3 頁(yè) 共 148 頁(yè)第一章第一章緒論緒論1.1 算法的概念算法的概念算法：解決一個(gè)問(wèn)題的算法：解決一個(gè)問(wèn)題的無(wú)歧義無(wú)歧義的指令序列，對(duì)的指令序列，對(duì)合法的輸入合法的輸入在在有有限限的時(shí)間內(nèi)可得到需要的的時(shí)間內(nèi)可得到需要的輸出輸出。算法的一些特點(diǎn)：算法的一些特點(diǎn)： 無(wú)歧義性（確定性）：算法的每個(gè)步驟必須確定無(wú)疑無(wú)歧義性（確定性）：算法的每個(gè)步驟必須確定無(wú)疑 有窮性

6、：算法的執(zhí)行必須有限步終止有窮性：算法的執(zhí)行必須有限步終止 輸入的范圍：算法只對(duì)輸入的范圍：算法只對(duì)滿足條件的輸入有響應(yīng)滿足條件的輸入有響應(yīng) 正確性：算法應(yīng)能解決要求的問(wèn)題正確性：算法應(yīng)能解決要求的問(wèn)題 同一算法的不同表示形式：自然語(yǔ)言、偽代碼、高級(jí)語(yǔ)言同一算法的不同表示形式：自然語(yǔ)言、偽代碼、高級(jí)語(yǔ)言 同一問(wèn)題存在的多種算法：同一問(wèn)題存在的多種算法：設(shè)計(jì)思想不同，時(shí)空性能各異設(shè)計(jì)思想不同，時(shí)空性能各異例，求兩個(gè)正整數(shù) m 和 n 的最大公因子的算法算法一最容易想到的算法挨個(gè)檢查Step 1t = min m, nStep 2如果 m 除以 t 的余數(shù)為 0，轉(zhuǎn) Step 3；否則，轉(zhuǎn) Ste

7、p 4；Step 3如果 n 除以 t 的余數(shù)為 0，返回 t 的值；否則，轉(zhuǎn) Step 4；Step 4t = t 1，轉(zhuǎn) Step 2。分析：分析： 上述步驟每一步均確定沒(méi)有歧義，是一個(gè)循環(huán)結(jié)構(gòu)程序這才叫算法這指特定問(wèn)題的算法第 4 頁(yè) 共 148 頁(yè) 循環(huán)執(zhí)行次數(shù)未知，那么它會(huì)有限步終止嗎？（每次（每次 t 1） 該算法由自然語(yǔ)言描述自然語(yǔ)言描述 該算法正確嗎？如何證明？該算法正確嗎？如何證明？算法二小學(xué)數(shù)學(xué)中講述的算法Step 1將 m 分解質(zhì)因子；Step 2將 n 分解質(zhì)因子；Step 3尋找 Step 1 和 Step 2 得到的兩個(gè)質(zhì)因子連乘積的公共部分（注：若 m 的分解中質(zhì)

8、因子 p 出現(xiàn)了 x 次，n 的分解中 p 出現(xiàn)了 y 次，作為公共部分，p 應(yīng)出現(xiàn) minx, y次） ；Step 4計(jì)算公共部分的連乘積，并將結(jié)果返回。分析：分析：此算法中，如何分解質(zhì)因子沒(méi)說(shuō)明，如何尋找公共部分不清楚，不滿足算法的確定性要求，所以嚴(yán)格講起來(lái)不能稱為算法嚴(yán)格講起來(lái)不能稱為算法，至少有待進(jìn)一步具體說(shuō)明！考慮如何具體說(shuō)明：考慮如何具體說(shuō)明： 分解質(zhì)因子需要知道有哪些質(zhì)數(shù)分解質(zhì)因子需要知道有哪些質(zhì)數(shù) 尋找公共部分涉及到質(zhì)因子連乘積的表示形式尋找公共部分涉及到質(zhì)因子連乘積的表示形式算法三Euclid 算法（記錄于公元前 3 世紀(jì) Euclid 所著的Elements）Euclid

9、(m, n)/Input：兩個(gè)正整數(shù) m 和 n/Output：m 和 n 的最大公因子while n0 do第 5 頁(yè) 共 148 頁(yè)r = m mod nm = nn = rreturn m分析：分析： 上述步驟每一步均確定沒(méi)有歧義，是一個(gè)循環(huán)結(jié)構(gòu)程序 循環(huán)執(zhí)行次數(shù)未知，那么它有限步終止嗎？（每次（每次 n 都減?。┒紲p小） 該算法由偽代碼描述：偽代碼是自然語(yǔ)言和編程語(yǔ)言的混合偽代碼描述：偽代碼是自然語(yǔ)言和編程語(yǔ)言的混合 該算法正確嗎？如何證明？該算法正確嗎？如何證明？證明：證明：設(shè)函數(shù) gcd(m, n)就是采用 Euclid 算法計(jì)算最大公因子的函數(shù)。則算法的正確性基于兩個(gè)事實(shí)： 若

10、m0，則 gcd(m, 0)= m gcd(m, n) = gcd(n, m mod n)第一個(gè)事實(shí)顯然易見(jiàn)。設(shè) d = gcd(m, n)且 m = kn + t。則存在 a，b 使得 m = ad，n = bd，且 a 與 b 互質(zhì)。m mod n = t = m kn = ad kbd =(a kb)*d。說(shuō)明 d 是 n 和 m mod n 的公因子，還需說(shuō)明，b 與 a kb 互質(zhì)。假設(shè) b 與 a kb 有公因子 c。即，b = uc，a kb = vc。則 a = kuc + vc =(ku + v)*c，m =(ku + v)*cd，n = bd = ucd，由 d是 m 與

11、n 的最大公因子得 c=1，即 b 與 a kb 互質(zhì)。第 6 頁(yè) 共 148 頁(yè)比較上述三個(gè)算法，很明顯，Euclid 算法形式簡(jiǎn)單，循環(huán)次數(shù)算法形式簡(jiǎn)單，循環(huán)次數(shù)少少（后面會(huì)進(jìn)行詳細(xì)分析）（后面會(huì)進(jìn)行詳細(xì)分析） ，所以我們說(shuō) Euclid 算法更高效。算法更高效。1.2 算法問(wèn)題求解基礎(chǔ)算法問(wèn)題求解基礎(chǔ)算法是求解的具體指令，不是解答。算法是求解的具體指令，不是解答。設(shè)計(jì)和分析算法的典型步驟：設(shè)計(jì)和分析算法的典型步驟：1.理解問(wèn)題理解問(wèn)題1) 仔細(xì)閱讀問(wèn)題描述2) 手工測(cè)試幾個(gè)例子3) 思考特殊情形4) 分析是否已有該類問(wèn)題的算法2.確定計(jì)算設(shè)備的能力確定計(jì)算設(shè)備的能力現(xiàn)行的絕多數(shù)算法都是基

12、于馮諾依曼機(jī)器模型的，即，隨機(jī)存儲(chǔ)模型，它假定指令依次執(zhí)行，每次執(zhí)行一個(gè)操作，在這樣機(jī)器上執(zhí)行的算法稱為 sequential 算法算法。適合于現(xiàn)在新興的可同時(shí)執(zhí)行多條操作的計(jì)算機(jī)的算法，稱為并行算法并行算法。除非對(duì)某些本質(zhì)上復(fù)雜、需處理大量數(shù)據(jù)或者對(duì)時(shí)間要求很高除非對(duì)某些本質(zhì)上復(fù)雜、需處理大量數(shù)據(jù)或者對(duì)時(shí)間要求很高的問(wèn)題，的問(wèn)題，無(wú)需擔(dān)心現(xiàn)在計(jì)算機(jī)的能力！無(wú)需擔(dān)心現(xiàn)在計(jì)算機(jī)的能力！3.選擇精確算法還是近似算法選擇精確算法還是近似算法1) 存在某些問(wèn)題不能精確解決，例如求平方根2) 可精確解決的算法難以接受的慢，例如，TSP 問(wèn)題3) 近似算法可以是某些更為復(fù)雜的精確算法的組成部分第 7 頁(yè)

13、共 148 頁(yè)4.確定合適的數(shù)據(jù)結(jié)構(gòu)確定合適的數(shù)據(jù)結(jié)構(gòu)存在某些算法設(shè)計(jì)方法固有依賴于描述問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。5.算法設(shè)計(jì)方法算法設(shè)計(jì)方法本課程所要解決的主要問(wèn)題主要問(wèn)題。算法設(shè)計(jì)方法（或策略）是指：從算法上解決問(wèn)題的通用方法，可適用于不同領(lǐng)域的各種各樣的問(wèn)從算法上解決問(wèn)題的通用方法，可適用于不同領(lǐng)域的各種各樣的問(wèn)題題。學(xué)習(xí)這些方法的原因：1) 有助于為新問(wèn)題設(shè)計(jì)算法，授人以魚(yú)不如授人以漁授人以魚(yú)不如授人以漁2) 每門學(xué)科都對(duì)其研究主題進(jìn)行分類，算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，有助于根據(jù)設(shè)計(jì)思想對(duì)算法進(jìn)行分類6.描述算法的方法描述算法的方法1) 自然語(yǔ)言描述，如前例中算法一、二2) 偽代碼描述，如前例中算法

14、三 Euclid 算法，無(wú)統(tǒng)一格式3) 流程圖，只適合于描述很簡(jiǎn)單的算法4) 某種計(jì)算機(jī)語(yǔ)言寫成的程序7.證明算法的正確性證明算法的正確性一旦算法描述清楚，就需要證明其正確性，即，它對(duì)每一個(gè)合法的輸入都可以在有限的時(shí)間內(nèi)得出需要的結(jié)果。證明算法正確的一個(gè)常用方法是：數(shù)學(xué)歸納法。數(shù)學(xué)歸納法。注意：測(cè)試幾組輸入數(shù)據(jù)的方法雖然簡(jiǎn)單，但卻不足以說(shuō)明算注意：測(cè)試幾組輸入數(shù)據(jù)的方法雖然簡(jiǎn)單，但卻不足以說(shuō)明算法正確！法正確！不過(guò)卻可以說(shuō)明一個(gè)算法不正確！不過(guò)卻可以說(shuō)明一個(gè)算法不正確！8.算法分析算法分析第 8 頁(yè) 共 148 頁(yè)算法應(yīng)具有的幾個(gè)品質(zhì)：算法應(yīng)具有的幾個(gè)品質(zhì)：本課程所要解決的主要問(wèn)題主要問(wèn)題1)

15、 正確性正確性2) 效率效率：時(shí)間效率和空間效率。第二章詳述3) 簡(jiǎn)潔性簡(jiǎn)潔性：無(wú)法用數(shù)學(xué)定義精確描述，最好給人以美感例，前述的求 gcd 的算法哪個(gè)更簡(jiǎn)單？簡(jiǎn)單的算法易于理解，易于編程，通常包含較少的 bug，一般也更有效率4) 通用性通用性：同樣的效率，解決的問(wèn)題可適用范圍當(dāng)然越廣越好，但是有時(shí)通用算法難設(shè)計(jì)且效率差，或者根本無(wú)通用算法例，判定兩個(gè)正整數(shù)是否互質(zhì)的算法就沒(méi)有求 gcd 的通用；二次方程求根公式存在的，但沒(méi)有任意次方程的求根方法9.算法編碼實(shí)現(xiàn)算法編碼實(shí)現(xiàn)1) 注意程序嚴(yán)格準(zhǔn)確的實(shí)現(xiàn)算法2) 算法到程序的過(guò)渡：算法中假設(shè)輸入都是合法的，程序中需驗(yàn)證3) 程序的正確性驗(yàn)證的實(shí)際

16、方式：測(cè)試（testing） 。4) 學(xué)習(xí)編程技巧，以提高程序效率最優(yōu)算法（最優(yōu)算法（optimality）：不是算法效率的問(wèn)題，而是算法解決問(wèn)題的復(fù)雜性，即，解決某類問(wèn)題的任意算法中哪個(gè)所付出的代價(jià)最少。某些問(wèn)題的最優(yōu)算法是存在的，比如，通過(guò)比較進(jìn)行排序的最優(yōu)算法需要進(jìn)行 n log n 次比較；但某些看上去簡(jiǎn)單的問(wèn)題，還未找到最優(yōu)算法，例如，矩陣乘法。不可判定性不可判定性(undecidability)：不是說(shuō)，每個(gè)問(wèn)題均有算法解決第 9 頁(yè) 共 148 頁(yè)（注意，這不同于一個(gè)問(wèn)題沒(méi)有解這不同于一個(gè)問(wèn)題沒(méi)有解，例如，判別式為負(fù)的二次方程無(wú)實(shí)數(shù)解） 。所幸的是，實(shí)際計(jì)算中的絕大多數(shù)問(wèn)題還是有

17、解決算法的。1.3 重要的問(wèn)題類型重要的問(wèn)題類型后面的章節(jié)將以以下問(wèn)題展開(kāi)，討論不同算法的設(shè)計(jì)技術(shù)與分析方法。1. 排序排序我們經(jīng)常遇到排序問(wèn)題，比如學(xué)校學(xué)生按學(xué)號(hào)排序，學(xué)號(hào)通常被稱為 key。那么為什么要進(jìn)行排序?yàn)槭裁匆M(jìn)行排序？排序使得很多關(guān)于列表的問(wèn)排序使得很多關(guān)于列表的問(wèn)題簡(jiǎn)單題簡(jiǎn)單，比如字典中單詞的搜索；排序還常作為某些領(lǐng)域重要算法排序還常作為某些領(lǐng)域重要算法的輔助步驟的輔助步驟，比如，在幾何算法中。當(dāng)前，已有很多排序算法，在這些算法當(dāng)中，有些較好的可將任意 n 個(gè)元素通過(guò)大約 n log2 n 比較完成排序，但是沒(méi)有哪一個(gè)通過(guò)沒(méi)有哪一個(gè)通過(guò)關(guān)鍵字比較的排序算法能比關(guān)鍵字比較的排序算

18、法能比 n log2 n 作的更好作的更好！排序算法的兩個(gè)性質(zhì)：排序是否穩(wěn)定穩(wěn)定（保持輸入相等元素的相對(duì)次序不變）和是否需要大量輔助空間（in place 排序） 。2. 搜索（查找）搜索（查找）同樣，有很多搜索算法，簡(jiǎn)單的如順序搜索，快速的如二叉搜索（要求元素已排序） ，等等。由于搜索經(jīng)常與添加和刪除操作聯(lián)系在一起，所以，需仔細(xì)設(shè)需仔細(xì)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)計(jì)數(shù)據(jù)結(jié)構(gòu)。第 10 頁(yè) 共 148 頁(yè)3. 字符串處理字符串處理由于所有程序在計(jì)算機(jī)看來(lái)都是字符串，所以此類算法同計(jì)算機(jī)語(yǔ)言和編譯緊密相關(guān)。此類算法中最特殊的一個(gè)字符串匹配字符串匹配在給定文本中搜索給定單詞，在實(shí)際中非常有用。4. 圖論問(wèn)題圖論問(wèn)

19、題算法中最古老而又吸引人的領(lǐng)域就是圖算法。圖可以看作是由若干結(jié)點(diǎn)和若干個(gè)連接其中某些結(jié)點(diǎn)的邊所構(gòu)成，其準(zhǔn)確定義下一小節(jié)給出。圖可以為日常很多應(yīng)用建模，比如，交通和通信網(wǎng)，項(xiàng)目調(diào)度，博弈。最基本的圖算法包括：圖遍歷算法圖遍歷算法（如何遍歷網(wǎng)絡(luò)中所有結(jié)點(diǎn)） ，最小生成樹(shù)算法最小生成樹(shù)算法（如何鋪設(shè)最經(jīng)濟(jì)的通信網(wǎng)絡(luò)） ，最短路徑算法最短路徑算法（如何確定兩城市間的最佳路線） ，有向圖的拓?fù)渑判蛴邢驁D的拓?fù)渑判颍ㄈ绾未_定專業(yè)課程的學(xué)習(xí)順序） ，等等。有些圖論問(wèn)題非常復(fù)雜，以至于最快的計(jì)算機(jī)也只能解決較小規(guī)模的這類問(wèn)題，比如，旅行商問(wèn)題旅行商問(wèn)題（遍歷 n 個(gè)城市每個(gè)一次的最短線路）和圖著色問(wèn)題圖著色問(wèn)

20、題（給圖的結(jié)點(diǎn)著色以使相鄰結(jié)點(diǎn)顏色不同的最少顏色數(shù)） ，例如，多叉路口交通燈的設(shè)計(jì)就是一個(gè)圖著色問(wèn)題。5. 組合問(wèn)題組合問(wèn)題更抽象的講，旅行商問(wèn)題和圖著色問(wèn)題都是組合問(wèn)題的例子。組合問(wèn)題尋求滿足某些約束條件或者某些期望性質(zhì)的組合對(duì)象（排列，組合，多重集） 。第 11 頁(yè) 共 148 頁(yè)組合問(wèn)題被認(rèn)為是計(jì)算機(jī)科學(xué)中最困難的問(wèn)題，因?yàn)椋?隨著問(wèn)題規(guī)模擴(kuò)大，組合對(duì)象的數(shù)目急劇擴(kuò)大隨著問(wèn)題規(guī)模擴(kuò)大，組合對(duì)象的數(shù)目急劇擴(kuò)大 沒(méi)有已知的算法可在可接受的時(shí)間內(nèi)解決大多數(shù)此類問(wèn)題沒(méi)有已知的算法可在可接受的時(shí)間內(nèi)解決大多數(shù)此類問(wèn)題 大多數(shù)計(jì)算機(jī)科學(xué)家相信不存在可接受時(shí)間內(nèi)解決此類問(wèn)題大多數(shù)計(jì)算機(jī)科學(xué)家相信不存在

21、可接受時(shí)間內(nèi)解決此類問(wèn)題的算法，但不能證實(shí)和證偽的算法，但不能證實(shí)和證偽6. 幾何問(wèn)題幾何問(wèn)題幾何問(wèn)題處理點(diǎn)、線、多邊形。 應(yīng)用領(lǐng)域包括計(jì)算機(jī)圖形學(xué)，機(jī)器人學(xué)，X 線斷層攝影學(xué)。典型算法，比如尋找平面內(nèi) n 個(gè)點(diǎn)中的最近點(diǎn)對(duì)算法。7. 數(shù)值問(wèn)題數(shù)值問(wèn)題涉及到數(shù)學(xué)問(wèn)題的求解，比如，解方程或方程組，計(jì)算定積分，等等。大多數(shù)這類問(wèn)題只能近似解決，主要一個(gè)原因是他們的操作對(duì)象是實(shí)數(shù)，計(jì)算機(jī)只能夠近似表述。1.4 基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)1. 線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)兩種基本的線性數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表數(shù)組和鏈表。數(shù)組的特點(diǎn)： 每個(gè)元素類型相同，占有同樣大小的存儲(chǔ)空間 整個(gè)數(shù)組連續(xù)存儲(chǔ)，任意元素可通過(guò)下標(biāo)

22、隨機(jī)訪問(wèn)隨機(jī)訪問(wèn)單（雙、循環(huán)）鏈表的特點(diǎn)： 非連續(xù)存儲(chǔ)，訪問(wèn)某個(gè)元素的時(shí)間與其在鏈表中的位置有關(guān)第 12 頁(yè) 共 148 頁(yè) 無(wú)需預(yù)留存儲(chǔ)空間，插入和刪除操作方便數(shù)組和鏈表均可用于實(shí)現(xiàn)抽象數(shù)據(jù)結(jié)構(gòu)線性表，其基本操作是：搜索、插入、刪除。兩種特殊的線性表：棧（LIFO）和隊(duì)列（FIFO） 。2. 圖圖圖 G =(V, E)，其中 V 是頂點(diǎn)（結(jié)點(diǎn)）的有限集，E 是頂點(diǎn)對(duì)（邊）所構(gòu)成的集合。如果邊沒(méi)有方向性，稱 G 是無(wú)向圖；否則，稱 G 為有向圖。aedcbdfacfeb 例：如上左圖為無(wú)向圖，其中 V=a, b, c, d, e, f，E=(a, c), (a, d), (b, c), (b,

23、 f), (c, e), (d, e), (e, f)；右圖為有向圖，其中 V=a, b, c, d, e, f，E=(a, c), (b, c), (b, f), (c, e), (d, a), (d, e), (e, c), (e, f)。圖的定義不禁止圈（loop，自回路） ，但除非明確說(shuō)明，我們所講的圖不包含圈。 無(wú)向圖的性質(zhì)：0 |E| |V|(|V| 1)/ 2 完全圖：每對(duì)頂點(diǎn)均有邊相連，|V|個(gè)頂點(diǎn)的完全圖記作 K|V| 稠密圖（dense）和稀疏圖（sparse）圖的表示：算法中最主要的兩種表示是鄰接矩陣和鄰接表。上左圖的鄰接矩陣和鄰接表表示如下：fedcba第 13 頁(yè) 共

24、 148 頁(yè)fedcba010010101100010001010011100100001100acbfedcfebcaacdedebf對(duì)無(wú)向圖而言，其鄰接矩陣總是對(duì)稱對(duì)稱的。Why？顯然，稀疏圖用鄰接表更節(jié)省存儲(chǔ)空間。Why？但具體某問(wèn)題采用何種表示，更加依賴于解決該問(wèn)題的算法的性質(zhì)。 加權(quán)圖（weighted graph）：圖中邊賦有值，稱為權(quán)或 cost。比如實(shí)際應(yīng)用中，交通圖中兩城市間的公路距離。鄰接矩陣和鄰接表均可用于存儲(chǔ)加權(quán)圖。矩陣中的值可表示距離（無(wú)邊的是為） ，鄰接表的每一結(jié)點(diǎn)可添加一項(xiàng)表示距離adcb523187ab,2bdca,2a,5a,7c,5c,8b,3b,8d,7d

25、,3d,1c,1 路徑（path）：從頂點(diǎn) u 到頂點(diǎn) v 的路徑，是指始于 u 終于v 有邊連接的頂點(diǎn)序列（有向圖中，要求邊的方向均為從 u至 v 方向） 。若除起止點(diǎn)外路徑中無(wú)頂點(diǎn)重復(fù)，稱簡(jiǎn)單路徑簡(jiǎn)單路徑。路徑長(zhǎng)度指路徑中的邊數(shù)（即，頂點(diǎn)數(shù)減 1） 。 連通圖（connected）：圖中的每對(duì)頂點(diǎn)均有路徑連接 子圖（subgraph）：圖 G=(V, E)稱為圖 G 的子圖，當(dāng)且僅當(dāng)，VV 并且 E E第 14 頁(yè) 共 148 頁(yè) 連通子圖（connected component）：如果一個(gè)圖不是連通的，它將包含若干個(gè)連通子圖。連通子圖指，添加任何結(jié)點(diǎn)則不連通的極大子圖。下圖就不是一個(gè)連通

26、圖，它有兩個(gè)連通子圖，其頂點(diǎn)集分別是a, b, c, d, e和f, g, h, i。cbdaefghi思考：思考：中國(guó)的省際公路網(wǎng)是否是一個(gè)連通圖？(注意臺(tái)灣和海南!) 環(huán)路（cycle）：起止點(diǎn)為同一結(jié)點(diǎn)且路徑長(zhǎng)度為正的簡(jiǎn)單路徑。沒(méi)有環(huán)路的圖稱為無(wú)環(huán)圖（acyclic） 。 Hamilton 回路：起止點(diǎn)為同一結(jié)點(diǎn)，且只經(jīng)過(guò)圖中其它結(jié)點(diǎn)一次的環(huán)路 Euler 回路：起止點(diǎn)為同一結(jié)點(diǎn)，且只經(jīng)過(guò)圖中所有邊一次的環(huán)路3. 樹(shù)樹(shù)樹(shù)是一個(gè)連通的無(wú)環(huán)圖。森林森林：不連通的無(wú)環(huán)圖，其每個(gè)連通子圖是一棵樹(shù)。第 15 頁(yè) 共 148 頁(yè)a ab bc cf fd de e( (1 1) )樹(shù)樹(shù)a ab bc

27、 cf fd dg g( (2 2) )森森林林e eh hi ij j 樹(shù)的性質(zhì) 1：|E| = |V| 1。注意，這是圖成為樹(shù)的必要條件必要條件，而不是充分條件不是充分條件。Why? 因?yàn)閳D不一定連通，不連通的圖卻因?yàn)閳D不一定連通，不連通的圖卻可以有環(huán)，仍能滿足此條件！可以有環(huán)，仍能滿足此條件！ 樹(shù)的性質(zhì) 2：任意兩結(jié)點(diǎn)間均有唯一的簡(jiǎn)單路徑。Why? 根樹(shù)（rooted trees）：性質(zhì) 2 使得選擇任一結(jié)點(diǎn)為根成為可能。所得樹(shù)稱為根樹(shù)。一般從上至下依次畫(huà)出根和各層結(jié)點(diǎn)。根樹(shù)有廣泛的應(yīng)用，常簡(jiǎn)稱簡(jiǎn)稱為樹(shù)，下面的樹(shù)均指根樹(shù)。所謂雙親、孩子、祖先、子孫、子樹(shù)、葉子等概念，不再詳述。i id

28、dc ch hb bg ga ae ef fa ab bd de ec cg gf fh hi i 結(jié)點(diǎn)的深度（depth）：從根到該結(jié)點(diǎn)的簡(jiǎn)單路徑的長(zhǎng)度 樹(shù)的高度（height）：從根到葉子的最長(zhǎng)的簡(jiǎn)單路徑的長(zhǎng)度。 有序樹(shù)（ordered trees）：每個(gè)結(jié)點(diǎn)的所有孩子是有序的。假定樹(shù)中以從左至右表示順序。二叉樹(shù)（binary trees）是最常用的有序樹(shù)，從而有左孩子、右孩子、左子樹(shù)、右子樹(shù)的概念。一般的有序樹(shù)可以用“左孩子、右兄弟”的方式表示成二叉樹(shù)。第 16 頁(yè) 共 148 頁(yè)4. 集合與字典集合與字典集合（set）：不同元素組成的一個(gè)無(wú)序的整體。常用的集合操作：membership

29、、union 和 intersection。字典：一種數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)對(duì)給定集合進(jìn)行搜索、添加和刪除元素這三種操作。集合的表示形式：給定全集 U 的 bit vector 表示和列表表示。第 17 頁(yè) 共 148 頁(yè)第二章第二章算法效率分析基礎(chǔ)算法效率分析基礎(chǔ)算法分析的重點(diǎn)是算法效率的分析，因?yàn)樗梢粤炕ú幌窈?jiǎn)潔性和通用性） ，關(guān)注的是時(shí)間效率（時(shí)間效率（time efficiency）和空間效率空間效率（space efficiency） 。2.1 分析框架分析框架對(duì)于給定問(wèn)題，一個(gè)算法的 時(shí)間效率：指它運(yùn)行的有多快（running time） 空間效率：指它需要多大的額外空間（memo

30、ry space）隨著計(jì)算機(jī)技術(shù)的革新，越來(lái)越大容量的存儲(chǔ)器的出現(xiàn)，算法對(duì)空間的需要已不再是什么問(wèn)題，但是時(shí)間效率卻沒(méi)有相應(yīng)的提高，因此，我們關(guān)注的重點(diǎn)是時(shí)間效率關(guān)注的重點(diǎn)是時(shí)間效率，但分析框架完全適用于空間效率。1. 度量輸入規(guī)模度量輸入規(guī)模算法的效率和輸入規(guī)模 n 有關(guān)，因?yàn)閹缀跛兴惴▽?duì)大的輸入運(yùn)行時(shí)間要長(zhǎng)一些。例如，對(duì)較大的數(shù)組排序，兩個(gè)較高維數(shù)的矩陣相乘，等等。關(guān)鍵是 n 如何確定?例，對(duì)一個(gè)列表的排序、搜索或者尋找其中最小元素，顯然，n 即列表中元素的個(gè)數(shù)；矩陣相乘，n 可以是矩陣的維數(shù)，也可以是矩陣中元素的個(gè)數(shù)；而大整數(shù)相乘，則 n 取大整數(shù)的位數(shù)比取大整數(shù)本身更合適。第 18

31、頁(yè) 共 148 頁(yè)2. 度量運(yùn)行時(shí)間的單位度量運(yùn)行時(shí)間的單位 秒、毫秒等時(shí)間單位：依賴于特定機(jī)器的性能，我們需要的是一種不依賴于外部因素、只決定于算法本身的衡量標(biāo)準(zhǔn) 算法中各種操作執(zhí)行的次數(shù)：精確，但過(guò)于困難且沒(méi)有必要 算法中基本操作執(zhí)行的次數(shù)：對(duì)算法總運(yùn)行時(shí)間貢獻(xiàn)最大的、最重要的操作例，對(duì)一個(gè)列表的排序，位于最內(nèi)循環(huán)中的操作肯定執(zhí)行次數(shù)最大，選擇元素的比較操作為基本操作；矩陣相乘，需要對(duì)應(yīng)元素一一相乘并求和，又因?yàn)榇蠖鄶?shù)計(jì)算機(jī)中乘法比加法慢，所以選擇乘法為基本操作；而大整數(shù)相乘，則宜取每一位的乘法為其基本操作。因?yàn)閷?shí)際運(yùn)行時(shí)間 T 和基本操作的執(zhí)行次數(shù) C 關(guān)于輸入規(guī)模 n近似的成一定的比例

32、，即，T(n) k C(n)，要分析時(shí)間效率，就要建立輸入規(guī)模 n 和基本操作執(zhí)行次數(shù) C 之間的函數(shù)關(guān)系 C(n)。例，假設(shè) C(n)=，當(dāng)輸入規(guī)模翻番時(shí)，運(yùn)行時(shí)nnnn2121) 1(212間如何變化？（當(dāng) n 足夠大時(shí)）4242121)2(21)2(21)()2()()2(2222nnnnnnnnnkCnkCnTnT注意：注意： 實(shí)際運(yùn)行時(shí)間和基本操作執(zhí)行次數(shù)所成的比例 k 對(duì)最后的結(jié)果沒(méi)有影響 函數(shù) C(n)中的常數(shù)因子對(duì)最后的結(jié)果沒(méi)有影響21第 19 頁(yè) 共 148 頁(yè) 考慮較大輸入規(guī)模時(shí)，低階量對(duì)最后的結(jié)果沒(méi)有影響為什么分析效率只考慮較大輸入規(guī)模的情形？為什么分析效率只考慮較大輸入

33、規(guī)模的情形？輸入規(guī)模較小時(shí)，不同算法之間的效率差異不明顯！輸入規(guī)模較小時(shí)，不同算法之間的效率差異不明顯！3. 函數(shù)的階（分析效率時(shí)的關(guān)注重點(diǎn)）函數(shù)的階（分析效率時(shí)的關(guān)注重點(diǎn)）nn2lognnn2logn2n32nn!103.3103.3 101021031033.6 1061026.61026.6 1021041061.3 10309.3 10157103101031.0 104106109104131041.3 1051081012105171051.7 10610101015106201062.0 10710121018書(shū)上 P7 有類似表。，可見(jiàn)底數(shù)不同的對(duì)數(shù)函數(shù)之間只相差一個(gè)nbnba

34、alogloglog常數(shù)因子，由前討論，可以忽略，今后忽略底數(shù)忽略底數(shù)，寫作 log n。指數(shù)函數(shù)和階乘函數(shù)增長(zhǎng)過(guò)快，只適合求解很小的輸入規(guī)模只適合求解很小的輸入規(guī)模，今后統(tǒng)稱作指數(shù)函數(shù)指數(shù)函數(shù)。4. 最壞、最好和平均情況最壞、最好和平均情況有很多算法的性能不僅和輸入規(guī)模有關(guān)，還和特定的輸入有關(guān)。例，在以數(shù)組 A1 . n表示的線性表中順序搜索某個(gè)值 K，找到則返回下標(biāo)值，返回1 表示未找到。 SequentialSearch (A1.n, K)第 20 頁(yè) 共 148 頁(yè)/Input：數(shù)組 A1.n和搜索值 K/Output：若有 A 中元素等于 K，返回該元素下標(biāo)，否則返回1i = 1wh

35、ile i n doif K = Ai return i/基本操作為此處的比較else i = i + 1return 1 最壞情況最壞情況：所有同規(guī)模的輸入中，算法運(yùn)行時(shí)間最長(zhǎng)的輸入 最好情況最好情況：所有同規(guī)模的輸入中，算法運(yùn)行時(shí)間最快的輸入 平均情況平均情況：隨機(jī)輸入的運(yùn)行情況，需對(duì)輸入做某些假定對(duì)上述線性搜索，Cworst(n)= n，Cbest(n)=1。假定，對(duì)任意輸入，能搜索到的概率為 p，且在任一位置找到的可能性相同，則如果 p=1，則表)1 (2) 1()1 (21)(pnnppnnpnnpnpnCavg示一定能找到，平均比較次數(shù)為；如果 p=0，則表示一定找不21n到，也需

36、比較 n 次。 最壞情況最壞情況：決定算法運(yùn)行時(shí)間的上限，常用 最好情況最好情況：除極少情況，很難保證算法總處于最好，不常用 平均情況平均情況：需進(jìn)行概率分析，運(yùn)算復(fù)雜，但有時(shí)很有必要，尤其當(dāng)平均情況遠(yuǎn)不像最差情況那么糟的時(shí)候。注意：平均情況不是最壞情況和最好情況的平均 分?jǐn)傂史謹(jǐn)傂剩河行┧惴ǖ牡谝淮芜\(yùn)行代價(jià)很高，但多次運(yùn)行第 21 頁(yè) 共 148 頁(yè)的代價(jià)卻比第一次的代價(jià)乘以運(yùn)行次數(shù)的值要小的多2.2 漸進(jìn)符號(hào)和基本效率類型漸進(jìn)符號(hào)和基本效率類型本課程所討論函數(shù)均為非負(fù)函數(shù)。本課程所討論函數(shù)均為非負(fù)函數(shù)。1. O 記號(hào)記號(hào)：函數(shù) t(n)O(g(n)如果存在某個(gè)正常數(shù) c 和某個(gè)非負(fù)整數(shù)

37、 n0 使得對(duì)所有 nn0，t(n)c g(n)。例，100n+5100n+n=101n101n2 （對(duì)所有 n5） ，所以100n+5O(n2)，此處，取 c=101，n0=5；又，100n+5100n+5n=105n （對(duì)所有 n1） ，100n+5O(n)，此處，取 c=105，n0=1。試證明，nO(n2)，O(n2)，0.00001nO(n2)，) 1(21nn3n +n+1 O(n2)。42. 記號(hào)記號(hào)：函數(shù) t(n)(g(n)如果存在某個(gè)正常數(shù) c 和某個(gè)非負(fù)整數(shù) n0 使得對(duì)所有 nn0，t(n)c g(n)。例， n (n2)，因?yàn)閷?duì)所有 n0，n n2，此處 c=1，n0=

38、0。33試證明，n2(n)，(n2)，100n+5 (n2)。) 1(21nn3. 記號(hào)記號(hào)：函數(shù) t(n)(g(n)如果存在正常數(shù) c1 和 c2 和某個(gè)非負(fù)整數(shù) n0 使得對(duì)所有 nn0，c1 g(n)t(n)c2 g(n)。例，（對(duì)所有 n0）22212121) 1(21nnnnn（對(duì)所有 n2）222412121212121) 1(21nnnnnnnn所以，取 c1=，c2=，n0=2，有(n2)。4121) 1(21nn4. 漸進(jìn)符號(hào)的性質(zhì)漸進(jìn)符號(hào)的性質(zhì)第 22 頁(yè) 共 148 頁(yè) 性質(zhì)性質(zhì) 1 1如果如果 t1(n)O(g1(n)，t2(n)O(g2(n)，則 t1(n) + t2

39、(n) O(maxg1(n),g2(n) 性質(zhì)性質(zhì) 2 2如果如果 t1(n)(g1(n)，t2(n)(g2(n)，則 t1(n) + t2(n) (maxg1(n),g2(n) 性質(zhì)性質(zhì) 3 3如果如果 t1(n)(g1(n)，t2(n)(g2(n)，則 t1(n) + t2(n) (maxg1(n),g2(n)性質(zhì)性質(zhì) 1 1 的證明：的證明：t1(n)O(g1(n)， c1 和 n1 對(duì)所有 nn1，t1(n)c1 g1(n)t2(n)O(g2(n)， c2 和 n2 對(duì)所有 nn2，t2(n)c2 g2(n)對(duì)所有 nmaxn1,n2，t1(n) + t2(n) c1 g1(n) +

40、c2 g2(n) c1 maxg1(n),g2(n) + c2 maxg1(n),g2(n) (c1+c2) maxg1(n),g2(n)取 c= c1+c2，n0=maxn1,n2，即，t1(n) + t2(n) O(maxg1(n),g2(n)。試證明另外兩個(gè)性質(zhì)。例，某算法判斷數(shù)組中是否包含相同元素，其思想如下，首先將數(shù)組排序，然后比較相鄰元素是否相同。假設(shè)所用排序算法屬于 O(n2)，比較相鄰元素顯然屬于 O(n)，則該算法屬于 O(maxn2,n)= O(n2)。第 23 頁(yè) 共 148 頁(yè)5. 使用極限比較函數(shù)的階使用極限比較函數(shù)的階0 t(n)的階小于的階小于 g(n)c t(n

41、)與與 g(n)有相同的階有相同的階 t(n)的階高于的階高于 g(n)例，(n2)21)11 (lim21lim21) 1(21lim222nnnnnnnnnn) 1(21nn，比0limlog2211)(loglim)()(loglimloglim2222nnennennnnnnnnn2log的階小。n6. 基本效率類型基本效率類型即使不考慮常數(shù)因子，仍然有無(wú)窮多種函數(shù)的階類型。即使不考慮常數(shù)因子，仍然有無(wú)窮多種函數(shù)的階類型。類型名稱描述1常數(shù)某些算法的最好情況，實(shí)際中很少log n對(duì)數(shù)每次迭代輸入規(guī)模以常數(shù)因子遞減的算法n線性需掃描整個(gè)輸入的算法n log n n-log-n 許多分治算

42、法屬于此類，如歸并排序和快速排序n2平方有兩重循環(huán)的算法，如冒泡排序和選擇排序n3立方有三重循環(huán)的算法，如矩陣乘法2n指數(shù)產(chǎn)生輸入集所有子集的算法n！階乘產(chǎn)生輸入集元素全排列的算法)()(limngntn第 24 頁(yè) 共 148 頁(yè)2.3 非遞歸算法的數(shù)學(xué)分析非遞歸算法的數(shù)學(xué)分析例 1在 n 個(gè)元素的線性表（以數(shù)組 A1.n表示）中尋找最大元素。MaxElement(A1.n)/Input：數(shù)值型數(shù)組 A1.n/Output：A 中最大元素的值maxval = A1for i = 2 to n doif aimaxval maxval = Aireturn maxval 輸入規(guī)模輸入規(guī)模：數(shù)組

43、中元素的個(gè)數(shù) n 基本操作基本操作：最頻繁執(zhí)行的操作在循環(huán)內(nèi)，循環(huán)內(nèi)有比較和賦值，但賦值不是每次都做，故比較為基本操作 是否依賴于輸入是否依賴于輸入：對(duì)所有輸入都一樣，故無(wú)須區(qū)分最好、最差和平均情況 比較次數(shù)比較次數(shù)：C(n) = = n 1 (n)ni 21非遞歸算法效率分析的一般模式非遞歸算法效率分析的一般模式： 確定描述輸入規(guī)模的參數(shù) 識(shí)別算法的基本操作 檢查基本操作的執(zhí)行次數(shù)是否只和輸入規(guī)模有關(guān)，如果還和其他因素有關(guān)，則需根據(jù)最好、最差和平均情況分別求解第 25 頁(yè) 共 148 頁(yè) 建立表示基本操作執(zhí)行次數(shù)的公式 得出執(zhí)行次數(shù)的通項(xiàng)公式，或者至少確定其階例 2檢查給定數(shù)組中的元素是否彼

44、此不同。UniqueElement (A1.n)/Input：數(shù)組 A1.n)/Output：如果所有元素均不相同，返回 true；否則，返回 falsefor i = 1 to n 1 dofor j = i + 1 to n doif Ai = Aj return falsereturn true 輸入規(guī)模輸入規(guī)模：數(shù)組中元素的個(gè)數(shù) n 基本操作基本操作：循環(huán)內(nèi)只有比較操作 是否依賴于輸入是否依賴于輸入：比較的次數(shù)不僅與輸入規(guī)模有關(guān)，還和數(shù)組中是否有相同元素，以及相同元素在數(shù)組中的位置有關(guān)，此例我們考慮最差情況最差情況 比較次數(shù)比較次數(shù)：每次內(nèi)循環(huán)的比較都執(zhí)行，Cworst(n)= = 1

45、111ninij = = =11)1(niin11) 1(nin11nii111) 1(nin2) 1)(2(nn2) 1( n=(n2)2) 1)(2(nn2) 1(nn 例 3給定兩個(gè) nn 的矩陣 A 和 B，求 C=AB。MatrixMultiplication(A1.n, 1.n, B1.n, 1.n)/Input：兩個(gè) nn 的矩陣 A 和 B第 26 頁(yè) 共 148 頁(yè)/Output：矩陣 C=ABfor i = 1 to n dofor j = 1 to n doCi, j = 0for k = 1 to n doCi, j = Ci, j + Ai, k * Bk, jret

46、urn C 輸入規(guī)模輸入規(guī)模：矩陣的階 n 基本操作基本操作：最內(nèi)循環(huán)有加法和乘法兩種操作，兩種操作執(zhí)行次數(shù)相同，所以取哪個(gè)為基本操作都可以 是否依賴于輸入是否依賴于輸入：對(duì)所有輸入都一樣，故無(wú)須區(qū)分最好、最差和平均情況 乘法次數(shù)乘法次數(shù)：M(n) = =n3ninjnk1111ninjn11nin122.4 遞歸算法的數(shù)學(xué)分析遞歸算法的數(shù)學(xué)分析例 1非負(fù)整數(shù) n 的階乘 F(n) = n! = 1(n1)n，其遞歸定義如下：1n=0F(n) = n F(n1) n0由此定義，可得其遞歸算法如下F(n)/Input：非負(fù)整數(shù) n第 27 頁(yè) 共 148 頁(yè)/Output：n 的階乘if n=0

47、 return 1else return F(n1)*n 輸入規(guī)模輸入規(guī)模：非負(fù)整數(shù) n 基本操作基本操作：有比較和乘法，但 n=0 時(shí)算法結(jié)束，所以基本操作是 else 分支中的乘法 是否依賴于輸入是否依賴于輸入：輸入僅是一整數(shù)，無(wú)須區(qū)分最好、最差和平均情況 乘法次數(shù)乘法次數(shù)：M(n) =+ 對(duì) n0) 1(1 -nFnM）中的乘法（計(jì)算1n*1 -nF中的乘法）（這是一個(gè)遞推公式，要求 M(n)的通項(xiàng)公式，可逆向回推，得M(n) = M(n1)+1= M(n2)+1+1=M(n2)+2=M(n3)+3 = M(ni)+i = M(nn)+n =M(0)+n，又 n=0 時(shí)，算法直接返回，不

48、進(jìn)行乘法，即，M(0)=0,M(n) = n遞歸算法效率分析的一般模式遞歸算法效率分析的一般模式： 確定描述輸入規(guī)模的參數(shù) 識(shí)別算法的基本操作 檢查基本操作的執(zhí)行次數(shù)是否只和輸入規(guī)模有關(guān)，如果還和其他因素有關(guān)，則需根據(jù)最好、最差和平均情況分別求解 建立表示基本操作執(zhí)行次數(shù)的遞推公式 解遞推式，得出執(zhí)行次數(shù)的通項(xiàng)公式，或者至少確定其階例 2Tower of Hanoi 問(wèn)題的遞歸算法如下第 28 頁(yè) 共 148 頁(yè)Hanoi(n, A, B, C)/Input：要搬運(yùn)的盤子總數(shù) n/Output：塔上盤子的搬運(yùn)過(guò)程if n=1 Move(n, A, C)elseHanoi(n1, A, C, B

49、)Move(n, A, C)Hanoi(n1, B, A, C) 輸入規(guī)模輸入規(guī)模：盤子總數(shù) n 基本操作基本操作：有比較和搬運(yùn)操作 Move，此處去 Move，why？ 是否依賴于輸入是否依賴于輸入：輸入僅是一整數(shù)，無(wú)須區(qū)分最好、最差和平均情況 搬運(yùn)次數(shù)搬運(yùn)次數(shù)：M(n) = M(n1)+1+ M(n1) 對(duì) n1又，只有一個(gè)盤子（即 n=1）時(shí)，需 Move 一次，即，M(1)=1。逆向回推，得M(n) = 2M(n1)+1 = 22M(n2)+1+1 = 4M(n2)+2+1 = 42M(n3)+1+2+1 = 8M(n3)+4+2+1 = =12422)(221iiiinM12)(2i

50、iinM=12)1(211nnnnM12) 1 (211nnM12211nn12 n這是一個(gè)指數(shù)算法指數(shù)算法，并且，由于此問(wèn)題本身的復(fù)雜性，這已經(jīng)是解決這個(gè)問(wèn)題的最有效方法。另外注意，經(jīng)常根據(jù)遞歸定義得到第 29 頁(yè) 共 148 頁(yè)的算法看上去非常簡(jiǎn)潔，但是要小心看上去的簡(jiǎn)潔掩蓋了實(shí)際上的看上去的簡(jiǎn)潔掩蓋了實(shí)際上的低效低效!2.5 例：例：Fibonacci 數(shù)列數(shù)列1Fibonacci 數(shù)列的遞推公式為0n=0F(n)=1n=1F(n1)+F(n2) n1解法一解法一求數(shù)列通項(xiàng)公式求數(shù)列通項(xiàng)公式前面求解遞歸算法效率時(shí)，求得通項(xiàng)公式即可獲知算法效率，受此啟發(fā)，對(duì)于遞推式給出的數(shù)列，如能求得數(shù)列

51、的通項(xiàng)公式，則對(duì)任意的輸入 n，求解 F(n)的時(shí)間僅依賴于通項(xiàng)公式的復(fù)雜程度。但此處逆向回推逆向回推法會(huì)讓人迅速放棄！二階常系數(shù)線性遞推關(guān)系二階常系數(shù)線性遞推關(guān)系 a x(n)+b x(n1)+c x(n2) = f(n)的求解的求解 二階：待求遞推關(guān)系最高項(xiàng)二階：待求遞推關(guān)系最高項(xiàng) x(n)與最低項(xiàng)與最低項(xiàng) x(n2)相差兩階相差兩階 線性：左側(cè)是遞推關(guān)系未知項(xiàng)的線性組合線性：左側(cè)是遞推關(guān)系未知項(xiàng)的線性組合 常系數(shù)：常系數(shù)：a，b，c 均為常數(shù)均為常數(shù) 齊次：如果齊次：如果 f(n)=0；否則，稱為非齊次；否則，稱為非齊次考慮最簡(jiǎn)單情形最簡(jiǎn)單情形 a x(n) + b x(n1) = 0，

52、即，x(n) = x(n1)，ab這是一個(gè)等比數(shù)列，其通解為 x(n) = rn，公比 r = ， 的值由初ab始條件確定。1此處可只選講二階常系數(shù)遞推關(guān)系的求解，而把兩個(gè)算法留到講動(dòng)態(tài)規(guī)劃時(shí)。此處可只選講二階常系數(shù)遞推關(guān)系的求解，而把兩個(gè)算法留到講動(dòng)態(tài)規(guī)劃時(shí)。第 30 頁(yè) 共 148 頁(yè)對(duì)于 a x(n)+b x(n1)+c x(n2) = 0 的情形，類比可猜想其通解也應(yīng)為等比數(shù)列，設(shè) x(n) = rn，則 x(n1) = rn1，x(n2) = rn2，得 a rn + b rn1 + c rn2 = 0，考慮一般情況，0，r0，得 特征方程特征方程a r2 + b r + c = 0

53、。對(duì)此方程解的不同情況，遞推關(guān)系的通解如下： 方程有二不等實(shí)根方程有二不等實(shí)根 r1，r2：遞推關(guān)系的通解為 x(n)=+ ，nr1nr2其中 和 的值由初始條件確定 方程有二相等實(shí)根方程有二相等實(shí)根 r：遞推關(guān)系的通解為 x(n)=+ n，其中nrnr 和 的值由初始條件確定 方程有二共軛虛根方程有二共軛虛根 r1, 2=uiv：由于算法分析所考慮的數(shù)列均為非負(fù)數(shù)，數(shù)列遞推關(guān)系的通解 x(n)=( cos n+ sin n)，其中n=，=arc tan ， 和 的值由初始條件確定22vu uv對(duì)于 a x(n)+b x(n1)+c x(n2) = f(n)的情形，它的通解是相應(yīng)齊次遞推關(guān)系的

54、通解與該非齊次遞推關(guān)系的一個(gè)特解之和。不像求通解，求特解的無(wú)一般方法，常用的方法是嘗試與 f(n)同階的函數(shù)。上述求解二階常系數(shù)線性遞推關(guān)系的方法可推廣到上述求解二階常系數(shù)線性遞推關(guān)系的方法可推廣到 n 階常系數(shù)階常系數(shù)線性遞推關(guān)系。線性遞推關(guān)系。例，解遞推關(guān)系 x(n)6x(n1)+9x(n2) = 4。 特征方程為 r2 6 r + 9 = 0，有二相等實(shí)根 r=3，相應(yīng)齊次遞推關(guān)系的通解為 x(n)=+ nn3n3 f(n)=4，同階的函數(shù)同樣為常數(shù)，設(shè)為 c，代入得 c6c+9c=4，解得 c=1 遞推關(guān)系 x(n)6x(n1)+9x(n2) = 4 的通解為 x(n)第 31 頁(yè) 共

55、 148 頁(yè)=+n+1n3n3求解求解 Fibonacci 數(shù)列的通項(xiàng)公式數(shù)列的通項(xiàng)公式 特征方程為 r2 r1 = 0，有二不等實(shí)根，2511r，通解為 F(n)=+ 2512rn)251(n)251( 將 F(0)=0，F(xiàn)(1)=1 代入得 += 0+ = 1)251()251( 解此二元一次方程組得 =，=5151F(n) = 51n)251(51n)251(解法二解法二用遞歸算法求數(shù)列第用遞歸算法求數(shù)列第 n 項(xiàng)項(xiàng)F(n)/Input：非負(fù)整數(shù) n/Output：Fibonacci 數(shù)列第 n 項(xiàng)if n1 return nelse return F(n1)+ F(n2) 輸入規(guī)模輸入

56、規(guī)模：非負(fù)整數(shù) n 基本操作基本操作：有比較和加法，但 n1 時(shí)算法結(jié)束，所以基本操作是 else 分支中的加法 是否依賴于輸入是否依賴于輸入：無(wú)須區(qū)分最好、最差和平均情況 加法次數(shù)加法次數(shù)：A(n) = A(n1)+A(n2)+1 對(duì) n0，A(0) = A(1) 第 32 頁(yè) 共 148 頁(yè)=0 這是一個(gè)二階常系數(shù)線性非齊次遞推關(guān)系，其對(duì)應(yīng)齊次遞推關(guān)系的特征方程為 r2r1=0，與 Fibonacci 數(shù)列通解相同 f(n)=1，同階的函數(shù)同樣為常數(shù)，設(shè)為 c，代入得 ccc=1，解得 c= 1，通解為 A(n)=+ 1n)251(n)251( 將 A(0)=0，A(1)=0 代入得 +1

57、 = 0+ 1 = 0)251()251( 解此二元一次方程組得 =，=，10551055A(n) = +11055n)251(1055n)251( 關(guān)于 A(n) = A(n1)+A(n2)+1 的另一解法：A(n)+1= A(n1)+1 + A(n2)+1，顯然這就是 Fibanacci 數(shù)列的遞推關(guān)系，而 A(0)+1=1=F(1)，A(1)+1=1=F(2)，A(n)=F(n+1) 1，即 A(n) = 1()，why？511)251(n511)251(nn)251(顯然，這是一個(gè)指數(shù)算法指數(shù)算法，遞歸算法的簡(jiǎn)潔掩蓋了它實(shí)際的低實(shí)際的低效效!解法三解法三用非遞歸算法求數(shù)列第用非遞歸算法

58、求數(shù)列第 n 項(xiàng)項(xiàng)Fib(n)/Input：非負(fù)整數(shù) n/Output：Fibonacci 數(shù)列第 n 項(xiàng)第 33 頁(yè) 共 148 頁(yè)F0 = 0; F1 = 1for i = 2 to n doFi = Fi1 + Fi2return Fn 輸入規(guī)模輸入規(guī)模：非負(fù)整數(shù) n 基本操作基本操作：循環(huán)內(nèi)只有加法，故加法為基本操作 是否依賴于輸入是否依賴于輸入：無(wú)須區(qū)分最好、最差和平均情況 加法次數(shù)加法次數(shù)：A(n) = n 1 (n)ni 21三種算法的比較：三種算法的比較： 第二種遞歸算法不可取第二種遞歸算法不可取 如果第一種算法指數(shù)運(yùn)算采用依次相乘的方法，其效率也屬于 (n) 存在算法存在算法

59、使得 n 次指數(shù)運(yùn)算可以在 (log n)時(shí)間內(nèi)完成第 34 頁(yè) 共 148 頁(yè)第三章第三章蠻力法（蠻力法（Brute Force）和算術(shù)問(wèn)題）和算術(shù)問(wèn)題例，計(jì)算，由就是蠻力法的體現(xiàn)。na次nnaaa*為什么應(yīng)用蠻力法進(jìn)行算法設(shè)計(jì)？為什么應(yīng)用蠻力法進(jìn)行算法設(shè)計(jì)？ 不像其他算法設(shè)計(jì)方法只適合于某類問(wèn)題，很難指出蠻力法不適合于什么問(wèn)題 對(duì)于小規(guī)模問(wèn)題，采用蠻力法設(shè)計(jì)的算法速度可接受，花費(fèi)大量時(shí)間設(shè)計(jì)高效算法不值 蠻力法可作為評(píng)價(jià)更高效算法的標(biāo)準(zhǔn)3.1 選擇排序和冒泡排序選擇排序和冒泡排序1. 選擇排序掃描整個(gè)列表選擇最小的元素放在第一個(gè)位置，掃描余下的元素選擇最小的放在第二個(gè)位置，依次繼續(xù)，直至最

60、后一個(gè)元素，這恐怕是我們進(jìn)行排序所想到的第一個(gè)算法。例，對(duì) 89，45，68，90，29，34，17 的選擇法排序?？紤]一般情形，第 i 趟掃描是尋找第 i 小的元素，所以前面 i1個(gè)元素已經(jīng)排好序，要依次掃描從第 i 個(gè)元素開(kāi)始的每個(gè)元素，這是內(nèi)循環(huán)。經(jīng)過(guò) n1 趟掃描后，只余最后一個(gè)元素，無(wú)需比較，所以，共需 n1 趟掃描（外循環(huán)）完成排序。偽代碼如下SelectionSort(A1.n)/Input：一個(gè)可排序元素的數(shù)組 A1.n/Output：以升序排列的數(shù)組 A1.n第 35 頁(yè) 共 148 頁(yè)for i = 1 to n1 domin = ifor j = i+1 to n doi