第一講算法基礎(chǔ)

1、第一章第一章 算法及基礎(chǔ)知識(shí)算法及基礎(chǔ)知識(shí)徐克奇 教材 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析王秋芬、呂聰穎等編著王秋芬、呂聰穎等編著 清華大學(xué)出版社清華大學(xué)出版社 2011年年8月月 參考教材參考教材 1.算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析（第二版）王曉東編著（第二版）王曉東編著 清華大學(xué)出版社清華大學(xué)出版社 2008年年1月月 2. 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析c+語言描述語言描述陳慧南編著陳慧南編著 電子工業(yè)出版社電子工業(yè)出版社 2006年年5月月 算法概論算法概論(注釋版注釋版). Sanjoy Dasgupta等著，錢等著，錢楓等注釋，機(jī)械工業(yè)出版社，楓等注釋，機(jī)械工業(yè)出版社，2009 算法導(dǎo)論算法

2、導(dǎo)論（第二版（第二版 影印版）影印版）(美美) Corrmen. T. H. 北京：高等教育出版社，北京：高等教育出版社，20025主要內(nèi)容 第1章算法及基礎(chǔ)知識(shí) 第2章貪心法 第3章分治法 第4章動(dòng)態(tài)規(guī)劃 第5章搜索法 第6章隨機(jī)化算法 第7章 線性規(guī)劃問題 第8章 數(shù)論算法及計(jì)算幾何算法 第9章 NP完全理論 為什么要學(xué)習(xí)算法？為什么要學(xué)習(xí)算法？ 算法是計(jì)算機(jī)科學(xué)的基石。算法是計(jì)算機(jī)科學(xué)的基石。沒有算法，計(jì)算機(jī)程沒有算法，計(jì)算機(jī)程序?qū)⒉粡?fù)存在序?qū)⒉粡?fù)存在 學(xué)習(xí)算法可以提高人們的分析能力。學(xué)習(xí)算法可以提高人們的分析能力。 算法可以看作是解決問題的一類特殊方法算法可以看作是解決問題的一類特殊方

3、法它它雖非問題的答案，但它是經(jīng)過準(zhǔn)確定義的，用來雖非問題的答案，但它是經(jīng)過準(zhǔn)確定義的，用來獲得答案的過程。獲得答案的過程。 無論是否涉及計(jì)算機(jī)，特定的算法設(shè)計(jì)技術(shù)都能無論是否涉及計(jì)算機(jī)，特定的算法設(shè)計(jì)技術(shù)都能看作是問題求解的有效策略?？醋魇菃栴}求解的有效策略。 算法的魅力：算法的魅力：思考思考 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 算法讓我們上一個(gè)更高的臺(tái)階算法讓我們上一個(gè)更高的臺(tái)階一個(gè)皇室數(shù)學(xué)挑戰(zhàn)問題(1202)假設(shè)兔子出生一個(gè)月后能繁殖，以后每月產(chǎn)一個(gè)孩子，一直下去直到永遠(yuǎn)。從一個(gè)兔子開始，問n個(gè)月后有多少個(gè)兔子？Leonardo Fibonacci1170-1250兔子的繁殖成熟不成熟初

4、始一個(gè)月二個(gè)月三個(gè)月四個(gè)月五個(gè)月兔子出生一個(gè)月后能繁殖，以后每月產(chǎn)一個(gè)孩子，一直下去。設(shè)Fn是n個(gè)月時(shí)兔子的數(shù)量F1 = 1F2 = 1Fn = Fn-1 + Fn-2Fibonacci numbers:1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 數(shù)量增長非?？? F30 106 !事實(shí)上, Fn 20.694n 1.6n, 指數(shù)級(jí)增長.可以證明 (3/2)nFn T(n-1) + T(n-2)但是 Fn = Fn-1 + Fn-2. 因此 T(n) Fn 指數(shù)級(jí)時(shí)間. 這有多糟糕?例. 計(jì)算 F200 大概需要 2140 個(gè)運(yùn)算.在一個(gè)快速計(jì)算機(jī)上要花多長時(shí)間?

5、（在NEC Earth Simulator上花292秒）n694. 02指數(shù)級(jí)時(shí)間都那么糟糕嗎?Earth simulator計(jì)算機(jī)需要計(jì)算機(jī)需要292秒計(jì)算秒計(jì)算F200.Time in seconds Interpretation 210 17 分分 220 12 日日 230 32 年年 240 山洞繪畫作品山洞繪畫作品 (一萬五千年到一萬七千年之間一萬五千年到一萬七千年之間) 245 直立人直立人發(fā)現(xiàn)火發(fā)現(xiàn)火 251 恐龍滅絕恐龍滅絕 257 地球形成地球形成 260 宇宙起源宇宙起源 剖剖 析析為什么花這么長時(shí)間為什么花這么長時(shí)間?讓我們剖析該遞歸function Fib1(n)if

6、 n = 1 return 1if n = 2 return 1return Fib1(n-1) + Fib1(n-2)同一個(gè)子問題被反復(fù)求解同一個(gè)子問題被反復(fù)求解! 學(xué)習(xí)學(xué)習(xí)算法算法要點(diǎn)要點(diǎn): 理解算法的概念。理解算法的概念。理解什么是程序，程序與算法的區(qū)別和理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法的計(jì)算復(fù)雜性概念。掌握用掌握用C+/JAVA語言描述算法的方法。語言描述算法的方法。1.1算法的基本概念算法的基本概念 算法（算法（Algorithm）：即在）：即在有限步驟有限步驟內(nèi)解一個(gè)數(shù)學(xué)問內(nèi)解一個(gè)數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)。

7、（韋氏題的過程，步驟中常常包括某一操作的重復(fù)。（韋氏詞典）詞典） 一個(gè)算法是解決一個(gè)問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程。一個(gè)算法是解決一個(gè)問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程。（廣義）（廣義） 算法是有窮規(guī)則的集合，規(guī)定了一個(gè)解決某一特定類算法是有窮規(guī)則的集合，規(guī)定了一個(gè)解決某一特定類型問題的運(yùn)算序列。（型問題的運(yùn)算序列。（D.E.Knuth 唐納德.E.克努特) 輸入性輸入性：有零個(gè)或多個(gè)外部量作為算法的輸入。：有零個(gè)或多個(gè)外部量作為算法的輸入。 輸出性輸出性：算法產(chǎn)生至少一個(gè)量作為輸出。：算法產(chǎn)生至少一個(gè)量作為輸出。 確定性確定性：算法中每條指令清晰，無歧義。：算法中每條指令清晰，無歧義。 有窮性有窮性

8、：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。（計(jì)算過程，時(shí)效）的時(shí)間也有限。（計(jì)算過程，時(shí)效） 可行性：可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。紙做有限次運(yùn)算后即可完成。 是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)程序可以不滿足算法的性質(zhì)(4)(4)即有窮性即有窮性。如操作系統(tǒng)如操作系統(tǒng) 算法是滿足上述性質(zhì)的指令序列。算法是滿足上述性質(zhì)的指令序列。程序：1.1.1算法的特征算法的特征 歐幾里德算法mnr例：歐

9、幾里德算法例：歐幾里德算法輾轉(zhuǎn)相除法求兩輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)個(gè)自然數(shù) m 和和 n 的最大公約數(shù)的最大公約數(shù) 輸入輸入m 和和n； 求求m除以除以n的余數(shù)的余數(shù)r； 若若r等于等于0 0，則，則n為最大公約數(shù)，算法結(jié)束；為最大公約數(shù)，算法結(jié)束； 否則執(zhí)行第步；否則執(zhí)行第步； 將將n的值放在的值放在m中，將中，將r的值放在的值放在n中；中； 重新執(zhí)行第步。重新執(zhí)行第步。歐幾里德算法歐幾里德算法1.1.1算法的算法的4個(gè)標(biāo)準(zhǔn)個(gè)標(biāo)準(zhǔn) 正確性正確性：在合理的數(shù)據(jù)輸入下，能：在合理的數(shù)據(jù)輸入下，能在有限的時(shí)間內(nèi)得出正確的結(jié)果。在有限的時(shí)間內(nèi)得出正確的結(jié)果。 可讀性可讀性：應(yīng)易于人的理解，易于調(diào)：應(yīng)易于

10、人的理解，易于調(diào)試。試。 健壯性健壯性：具備檢查錯(cuò)誤和對錯(cuò)誤進(jìn)：具備檢查錯(cuò)誤和對錯(cuò)誤進(jìn)行適當(dāng)處理的能力。行適當(dāng)處理的能力。 效率效率：算法執(zhí)行時(shí)所需計(jì)算機(jī)資源：算法執(zhí)行時(shí)所需計(jì)算機(jī)資源的多少，包括運(yùn)行時(shí)間和存儲(chǔ)空間。的多少，包括運(yùn)行時(shí)間和存儲(chǔ)空間。1.1.3 算法的描述形式算法的描述形式（1 1）自然語言）自然語言優(yōu)點(diǎn)：容易理解優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長、不夠嚴(yán)謹(jǐn)、二義性缺點(diǎn)：冗長、不夠嚴(yán)謹(jǐn)、二義性使用方法：粗線條描述算法思想使用方法：粗線條描述算法思想 注意事項(xiàng)：避免寫成自然段注意事項(xiàng)：避免寫成自然段（2 2）算法框圖法）算法框圖法 優(yōu)點(diǎn)：流程圖、盒圖，流程直觀、優(yōu)點(diǎn)：流程圖、盒圖，流程直觀、

11、簡潔、明了，便于理解和交流簡潔、明了，便于理解和交流 缺點(diǎn)：缺少嚴(yán)密性、靈活性缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡單算法使用方法：描述簡單算法注意事項(xiàng)：注意抽象層次注意事項(xiàng)：注意抽象層次1.1.3 算法的描述形式算法的描述形式N開始輸入m和n r=m % nr=0m=n；n=r 輸出n結(jié)束Y歐幾里德算法歐幾里德算法（3 3） 偽代碼語言描述法偽代碼語言描述法偽代碼（偽代碼（Pseudocode）：介于自然語言和）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)

12、。然語言來設(shè)計(jì)。 （算法語言）算法語言）優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解1.1.3 算法的描述形式算法的描述形式 1. r = m % n; 2. 循環(huán)直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出 n ;歐幾里德算法歐幾里德算法（4 4）高級(jí)程序設(shè)計(jì)語言描述法）高級(jí)程序設(shè)計(jì)語言描述法優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行 缺點(diǎn)：抽象性差，對語言要求高缺點(diǎn)：抽象性差，對語言要求高使用方法：算法需要驗(yàn)證使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)注意事項(xiàng)：將算法寫成子函數(shù)1.1.3 算法的描述形

13、式算法的描述形式#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( ) coutCommonFactor(63, 54)endl;歐幾里德算法1.2 算法設(shè)計(jì)的一般過程算法設(shè)計(jì)的一般過程充分理解要解決的問題充分理解要解決的問題數(shù)學(xué)模型擬制數(shù)學(xué)模型擬制-建立符合要求數(shù)學(xué)模型，設(shè)計(jì)相關(guān)約束條件建立符合要求數(shù)學(xué)模型，設(shè)計(jì)相關(guān)約束條件算法詳細(xì)設(shè)計(jì)算法詳細(xì)設(shè)計(jì)-選擇算法設(shè)計(jì)策略，確定數(shù)據(jù)結(jié)構(gòu)選擇算法設(shè)計(jì)策略，確定數(shù)據(jù)結(jié)構(gòu)算法描述算法描述-描述工具將

14、算法具體過程描述下來描述工具將算法具體過程描述下來算法思路的正確性驗(yàn)證算法思路的正確性驗(yàn)證 算法分析算法分析-時(shí)間、空間復(fù)雜性時(shí)間、空間復(fù)雜性算法的計(jì)算機(jī)實(shí)現(xiàn)和測試算法的計(jì)算機(jī)實(shí)現(xiàn)和測試 文檔資料的編制文檔資料的編制 算法設(shè)計(jì)的一般過程算法設(shè)計(jì)的一般過程 1 1理解問題理解問題2 2預(yù)測所有可能的輸入預(yù)測所有可能的輸入3. 3. 在精確解和近似解間做選擇在精確解和近似解間做選擇 4. 4. 確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) 5 5算法設(shè)計(jì)技術(shù)算法設(shè)計(jì)技術(shù)6 6描述算法描述算法 7 7跟蹤算法跟蹤算法 8 8分析算法的效率分析算法的效率 9 9根據(jù)算法編寫代碼根據(jù)算法編寫代碼 著名公式著名公

15、式 Algorithm + Data Structure = Programming好的算法好的算法 提高求解問題的效率提高求解問題的效率 節(jié)省存儲(chǔ)空間節(jié)省存儲(chǔ)空間 需要解決的問題需要解決的問題 問題問題一個(gè)求解一個(gè)求解算法：算法設(shè)計(jì)技術(shù)算法：算法設(shè)計(jì)技術(shù) 算法算法算法的評(píng)價(jià)：算法的評(píng)價(jià)： 算法分析技術(shù)算法分析技術(shù)1.3 算法分析算法復(fù)雜性算法復(fù)雜性 = 算法運(yùn)行時(shí)所需要的計(jì)算機(jī)資源的量算法運(yùn)行時(shí)所需要的計(jì)算機(jī)資源的量 時(shí)間復(fù)雜性、空間復(fù)雜性時(shí)間復(fù)雜性、空間復(fù)雜性影響時(shí)間復(fù)雜性的因素影響時(shí)間復(fù)雜性的因素 問題規(guī)模問題規(guī)模n、輸入序列、輸入序列I、算法本身、算法本身A影響空間復(fù)雜性的因素影響空間

16、復(fù)雜性的因素 算法本身、輸入輸出數(shù)據(jù)、輔助變量算法本身、輸入輸出數(shù)據(jù)、輔助變量算法復(fù)雜性的權(quán)衡算法復(fù)雜性的權(quán)衡 時(shí)間復(fù)雜度和空間復(fù)雜度相互影響時(shí)間復(fù)雜度和空間復(fù)雜度相互影響（時(shí)間換空間或空間換時(shí)間）（時(shí)間換空間或空間換時(shí)間）1.3 算法分析 三種情況下的復(fù)雜性（結(jié)合順序查找操作）三種情況下的復(fù)雜性（結(jié)合順序查找操作） 最好情況最好情況Tmin（N)1次次 最壞情況最壞情況Tmax（N)N次次 平均情況平均情況Tavg（N)(N+1)/2算法復(fù)雜性分析 當(dāng)問題規(guī)模增大時(shí)，復(fù)雜當(dāng)問題規(guī)模增大時(shí)，復(fù)雜度的極限行為度的極限行為稱為稱為算法的算法的漸進(jìn)時(shí)間復(fù)雜度漸進(jìn)時(shí)間復(fù)雜度。算法算法時(shí)間復(fù)雜度時(shí)間復(fù)雜

17、度最大問題規(guī)模最大問題規(guī)模1秒秒1分分1小時(shí)小時(shí)A1n10006*1043.6*106A2nlogn14048932.0*105A3N2312441897A4N31039153A52n91521算法算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度加速前最大問題規(guī)加速前最大問題規(guī)模模加速后最大問題規(guī)加速后最大問題規(guī)模模A1nS110*S1A2nlognS2約為約為10*S2A3N2S33.16*S3A4N3S42.15*S4A52nS5S5+3.3假設(shè)下一代計(jì)算機(jī)的速度是目前的10倍，下表是計(jì)算機(jī)加速后在相同的時(shí)間內(nèi)可以解決的問題規(guī)模增量。 算法漸近復(fù)雜性態(tài)算法漸近復(fù)雜性態(tài) 設(shè)算法的運(yùn)行時(shí)間為設(shè)算法的運(yùn)行時(shí)間為T(n)

18、，如果存在，如果存在T*(n)，使得使得 就稱就稱T*(n)為算法的漸進(jìn)復(fù)雜性態(tài)或漸進(jìn)時(shí)為算法的漸進(jìn)復(fù)雜性態(tài)或漸進(jìn)時(shí)間復(fù)雜性。間復(fù)雜性。0)()()(lim*nTnTnTn舉例： 假設(shè)算法A的運(yùn)行時(shí)間表達(dá)式為T1(n) T1(n)=30n4+20n3+40n2+46n+100 假設(shè)算法B的運(yùn)行時(shí)間表達(dá)式為T2(n) T2(n)=1000n3+50n2+78n+10隨著n的增大，對算法的執(zhí)行時(shí)間影響最大的是最高次方。算法A的運(yùn)行時(shí)間可記為：T*1(n)n4算法B的運(yùn)行時(shí)間可記為：T*2(n)n3 漸近符號(hào)漸近符號(hào): O-上界上界 -下界下界 -精確界（上界和下界）精確界（上界和下界）漸進(jìn)符號(hào)漸進(jìn)

19、符號(hào) 1. 大大O符號(hào)符號(hào)(上界）上界）定義定義1.1 若存在兩個(gè)正的常數(shù)若存在兩個(gè)正的常數(shù)c和和n0，對于任意，對于任意nn0，都有，都有T( (n)cf( (n) )，則稱，則稱T( (n) )=O( (f( (n)n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前的之前的情況無關(guān)情況無關(guān)緊要緊要T( (n) )cf( (n) )f(N)是是T(N)的一個(gè)的一個(gè)上界上界，即即T(N)的階不高于的階不高于f(N)的階的階 根據(jù)根據(jù)O O的定義，的定義，容易證明它有如下運(yùn)算規(guī)則：容易證明它有如下運(yùn)算規(guī)則： (1)O(f)+O(g)=O(max(f,g) (1)O(f)+O(g)=O(max(f,g

20、)； (2)O(f)+O(g)=O(f+g) (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg) (3)O(f)O(g)=O(fg)； (4)O(Cf(N)=O(f(N) (4)O(Cf(N)=O(f(N)，其中，其中C C是一個(gè)正的常數(shù)；是一個(gè)正的常數(shù)； (5)f=O(f)(5)f=O(f)2. 大大符號(hào)符號(hào) （下界）定義定義1.2 若存在兩個(gè)正的常數(shù)若存在兩個(gè)正的常數(shù)c和和n0，對于任意，對于任意nn0，都有，都有T( (n)cg( (n) )，則稱，則稱T( (n) )=( (g( (n)n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之 前 的之 前 的情 況 無

21、關(guān)情 況 無 關(guān)緊要緊要T( (n) )cg( (n) )漸進(jìn)符號(hào)（續(xù)）漸進(jìn)符號(hào)（續(xù)） g(N)是是T(N)的一個(gè)的一個(gè)下界下界，即即T(N)的階不低于的階不低于g(N)的階的階3. 符號(hào)符號(hào)（同階）（同階）定義定義1.3 若存在三個(gè)正的常數(shù)若存在三個(gè)正的常數(shù)c1、c2和和n0，對于任意，對于任意nn0都有都有c1f( (n)T( (n)c2f( (n) )，則稱，則稱T( (n) )=(f( (n) n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之 前 的之 前 的情 況 無 關(guān)情 況 無 關(guān)緊要緊要T( (n) )c2f( (n) )c1f( (n) )漸進(jìn)符號(hào)（續(xù)）漸進(jìn)符號(hào)（續(xù)） 當(dāng)且僅當(dāng)當(dāng)

22、且僅當(dāng)f(N)=O(g(N)f(N)=O(g(N)且且f(N)= f(N)= (g(N)(g(N)。稱稱f(N)f(N)與與g(N)g(N)同階同階。 例: 求T(n)=10n+4的漸進(jìn)上界 O(n)算法分析中常見的復(fù)雜性函數(shù)算法分析中常見的復(fù)雜性函數(shù) 幾種常見的時(shí)間復(fù)雜度函數(shù)按數(shù)量級(jí)從小幾種常見的時(shí)間復(fù)雜度函數(shù)按數(shù)量級(jí)從小到大的順序依次是：到大的順序依次是： (1), (logn)，(sqrt(n)，(n)，(nlogn)，(n2)，(n3)，(2n)，(n!) 在多項(xiàng)式中，在多項(xiàng)式中，n的最高次指數(shù)的最高次指數(shù)是最主要的決是最主要的決定因素，常數(shù)項(xiàng)、低次冪項(xiàng)和系數(shù)都是次定因素，常數(shù)項(xiàng)、低次

23、冪項(xiàng)和系數(shù)都是次要的。要的。例：求T(n)=amnm+am-1nm-1+a1n+a0的上界、下界根據(jù)定理1T(n)=(nm)時(shí)間復(fù)雜度分析的基本規(guī)則時(shí)間復(fù)雜度分析的基本規(guī)則 主要考慮可執(zhí)行語句的情況：主要考慮可執(zhí)行語句的情況： 輸入、輸出、賦值語句，為輸入、輸出、賦值語句，為O（1）；）； 順序結(jié)構(gòu)順序結(jié)構(gòu)，采用漸進(jìn)式，采用漸進(jìn)式O的求和規(guī)則來進(jìn)行計(jì)算；的求和規(guī)則來進(jìn)行計(jì)算； 選擇結(jié)構(gòu)選擇結(jié)構(gòu)，考慮判定后所執(zhí)行語句的執(zhí)行時(shí)間，考慮判定后所執(zhí)行語句的執(zhí)行時(shí)間O（max(T(s1), T(s2)）；）； 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)，考慮循環(huán)判定條件和循環(huán)體語句的執(zhí)行時(shí)，考慮循環(huán)判定條件和循環(huán)體語句的執(zhí)行時(shí)間

24、，采用漸進(jìn)式間，采用漸進(jìn)式O的乘積規(guī)則來進(jìn)行計(jì)算；的乘積規(guī)則來進(jìn)行計(jì)算； 復(fù)雜算法，先分割，然后采用漸進(jìn)式復(fù)雜算法，先分割，然后采用漸進(jìn)式O的求和規(guī)則和乘的求和規(guī)則和乘法規(guī)則來計(jì)算整個(gè)算法的時(shí)間復(fù)雜度；法規(guī)則來計(jì)算整個(gè)算法的時(shí)間復(fù)雜度； 基本語句基本語句對算法運(yùn)行時(shí)間貢獻(xiàn)最大的原操作語句。對算法運(yùn)行時(shí)間貢獻(xiàn)最大的原操作語句。 當(dāng)算法時(shí)間復(fù)雜性只依賴于問題規(guī)模時(shí)，選擇基本語句執(zhí)當(dāng)算法時(shí)間復(fù)雜性只依賴于問題規(guī)模時(shí)，選擇基本語句執(zhí)行次數(shù)來作為運(yùn)行時(shí)間行次數(shù)來作為運(yùn)行時(shí)間T(n)建立的依據(jù)。建立的依據(jù)。 例：求數(shù)組中元素最大值例：求數(shù)組中元素最大值空間復(fù)雜度空間復(fù)雜度 算法所占用的存儲(chǔ)空間包括算法所占

25、用的存儲(chǔ)空間包括 算法自身 輸入、輸出輸入、輸出 輔助空間輔助空間 空間復(fù)雜度空間復(fù)雜度S(n)=O(f(n)，以最壞情況來分，以最壞情況來分析析 例：例：插入法升序排序插入法升序排序void insert_sort(int n,int s) int a,i,j; for (i=1;i=0; & sja) sj+1=sj; j-; sj+1=a; 1.4 遞歸（是算法設(shè)計(jì)與描述的有力工具是算法設(shè)計(jì)與描述的有力工具） 子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自已，稱為遞歸。直接或間接調(diào)用自身的算法稱為遞歸算法 。 采用遞歸算法來求解問題的一般步驟： 分析問題，尋找遞歸關(guān)系

26、 找出停止條件 構(gòu)建函數(shù)體n的階乘00)!1(1!nnnnn停止條件停止條件遞歸關(guān)系遞歸關(guān)系停止條件與遞歸關(guān)系是遞歸函數(shù)的兩個(gè)要素，停止條件與遞歸關(guān)系是遞歸函數(shù)的兩個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。次計(jì)算后得出結(jié)果。Long long fun(int n) if(n0) printf(“ illegal number!n ”); break; else if(n=0) return 1; else return n*fun(n-1);例：例：排列問題排列問題 問題描述問題描述 n個(gè)元素，它們的編號(hào)為個(gè)元素，它們的編號(hào)為1,

27、2,n，排列問題的，排列問題的目的是生成這目的是生成這n個(gè)元素的全排列。個(gè)元素的全排列。 解題步驟解題步驟 分析遞歸關(guān)系分析遞歸關(guān)系 找出停止條件找出停止條件 設(shè)計(jì)遞歸函數(shù)設(shè)計(jì)遞歸函數(shù) 算法設(shè)計(jì)思路算法設(shè)計(jì)思路 將規(guī)模為將規(guī)模為n的排列問題轉(zhuǎn)化為規(guī)模為的排列問題轉(zhuǎn)化為規(guī)模為n-1的排列的排列問題。問題。 將規(guī)模為將規(guī)模為n-1的排列問題轉(zhuǎn)化為規(guī)模為的排列問題轉(zhuǎn)化為規(guī)模為n-2的排的排列問題列問題 將問題規(guī)模一級(jí)一級(jí)降至將問題規(guī)模一級(jí)一級(jí)降至1，1個(gè)元素的排列是個(gè)元素的排列是它本身，此時(shí)到達(dá)遞推的停止條件。數(shù)組中的它本身，此時(shí)到達(dá)遞推的停止條件。數(shù)組中的元素即為元素即為1個(gè)排列，然后進(jìn)行回歸依次

28、得到其個(gè)排列，然后進(jìn)行回歸依次得到其它的排列。它的排列。共要遞歸共要遞歸K次（次（K=n，n-1,n-2，1)當(dāng)當(dāng)k=1 輸出一個(gè)排列輸出一個(gè)排列 如何如何將規(guī)模為將規(guī)模為n的排列問題轉(zhuǎn)化為規(guī)模為的排列問題轉(zhuǎn)化為規(guī)模為n-1的排的排列問題。列問題。步驟步驟1：數(shù)組的首元素為第一個(gè)元素，還需生成后面：數(shù)組的首元素為第一個(gè)元素，還需生成后面n-1個(gè)元素全排列。個(gè)元素全排列。步驟步驟2：將數(shù)組的第一個(gè)元素和第二個(gè)元素交換，數(shù)組的：將數(shù)組的第一個(gè)元素和第二個(gè)元素交換，數(shù)組的首元素為第二個(gè)元素，還需生成后面首元素為第二個(gè)元素，還需生成后面n-1個(gè)元素全排列。個(gè)元素全排列。步驟步驟3：將數(shù)組的第一個(gè)元素和

29、第三個(gè)元素交換，數(shù)組的：將數(shù)組的第一個(gè)元素和第三個(gè)元素交換，數(shù)組的首元素為第三個(gè)元素，還需生成后面首元素為第三個(gè)元素，還需生成后面n-1個(gè)元素全排列。個(gè)元素全排列。步驟步驟4：步驟步驟n: 數(shù)據(jù)結(jié)構(gòu)： int An-按次序存放1n個(gè)數(shù)排列算法 void perm(int a,int k,int n) if (k=1) 輸出一個(gè)排列 else for(i=n-k ;in;i+) swap( an-k,ai); perm( a,k-1, n); swap( an-k,ai); 時(shí)間復(fù)雜度： 采用后向代入法計(jì)算可得到通項(xiàng)公式： T(n) =nT(n-1) =n(n-1)T(n-2) = =n(n-1

30、)(n-2) .2T(1)=n! 時(shí)間復(fù)雜度：O(n!)1n1)nT(n1nO(1)T(n) 遞歸算法的空間復(fù)雜度：遞歸算法的空間復(fù)雜度：算法的遞歸深度算法的遞歸深度 全排列算法全排列算法perm共執(zhí)行了共執(zhí)行了n次遞歸次遞歸 深度為深度為n 空間復(fù)雜度空間復(fù)雜度(遞歸遞歸)：O(n)回到Fibonacci數(shù)列問題function Fib1(n)if n = 1 return 1if n = 2 return 1return Fib1(n-1) + Fib1(n-2)同一個(gè)子問題被反復(fù)求解!Fibonacci數(shù)列一個(gè)較好的算法數(shù)列一個(gè)較好的算法子問題子問題: F1, F2, , Fn. 依次求

31、解它們并依次求解它們并保存它們的值保存它們的值!function Fib2(n)Create an array fib1.nfib1 = 1fib2 = 1for i = 3 to n: fibi = fibi-1 + fibi-2return fibn1 它返回正確的答案嗎？它返回正確的答案嗎？2 它有多快它有多快?運(yùn)算數(shù)與運(yùn)算數(shù)與n成比例成比例. 以前的方法以前的方法: 20.7nF200 現(xiàn)在可在合理時(shí)間內(nèi)計(jì)算出來現(xiàn)在可在合理時(shí)間內(nèi)計(jì)算出來, F2000 和和 F20000也一樣也一樣.啟示啟示 : 恰當(dāng)?shù)乃惴ㄊ故虑閺氐赘挠^恰當(dāng)?shù)乃惴ㄊ故虑閺氐赘挠^ 。第三個(gè)算法第三個(gè)算法用矩陣重寫用矩陣

32、重寫 F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 如下如下:10211110FFFF102213211101110FFFFFF10111110.1110FFFFFFnnnnnnnM1110因此只需快速計(jì)算因此只需快速計(jì)算多項(xiàng)式級(jí)多項(xiàng)式級(jí) vs. 指數(shù)級(jí)指數(shù)級(jí)運(yùn)行時(shí)間如運(yùn)行時(shí)間如 n, n2, n3 是是多項(xiàng)式級(jí)多項(xiàng)式級(jí)。運(yùn)行時(shí)間如運(yùn)行時(shí)間如 2n, en, 2n 是指數(shù)級(jí)是指數(shù)級(jí).多項(xiàng)式是適當(dāng)?shù)亩囗?xiàng)式是適當(dāng)?shù)闹笖?shù)級(jí)是不適當(dāng)?shù)闹笖?shù)級(jí)是不適當(dāng)?shù)脑谒惴ǚ治鲋?，這是最基本的一個(gè)分界線在算法分析中，這是最基本的一個(gè)分界線.1.5 基本數(shù)據(jù)結(jié)構(gòu) 順序表鏈表 連續(xù)存儲(chǔ)離散存儲(chǔ) 定位、插

33、入、刪除 棧隊(duì)列 FILOFIFO Top、bottomFront、Rear 樹樹概念概念 基本術(shù)語基本術(shù)語結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM孩子孩子結(jié)點(diǎn)結(jié)點(diǎn)、雙親雙親結(jié)點(diǎn)結(jié)點(diǎn)、兄弟兄弟結(jié)點(diǎn)結(jié)點(diǎn)、堂兄弟堂兄弟祖先祖先結(jié)點(diǎn)結(jié)點(diǎn)、子孫子孫結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :樹的深度：樹的深度：ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為假設(shè)根結(jié)點(diǎn)的層次為1,1,它的孩子結(jié)點(diǎn)它的孩子結(jié)點(diǎn)為第二層，依此類推一個(gè)結(jié)點(diǎn)所在的為第二層，依此類推一個(gè)結(jié)點(diǎn)所在的層次，為其雙親結(jié)點(diǎn)所在的層次加層次，為其雙親結(jié)點(diǎn)所在的層次加1 1。樹中葉子結(jié)點(diǎn)

34、所在的最大層次樹中葉子結(jié)點(diǎn)所在的最大層次任何一棵非空樹是一個(gè)二元組任何一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：其中：root 被稱為根結(jié)點(diǎn)，被稱為根結(jié)點(diǎn)， F 被稱為子樹森林被稱為子樹森林森林：森林：是是 m（m0）棵互）棵互不相交的樹的集合不相交的樹的集合ArootBEFKLCGDHIJMF 樹的存儲(chǔ)結(jié)構(gòu) 雙親存儲(chǔ)結(jié)構(gòu)雙親存儲(chǔ)結(jié)構(gòu) A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) typedef struct ElemType data; int parent;PtreeMaxSize; 鏈存儲(chǔ)結(jié)構(gòu)鏈存儲(chǔ)結(jié)構(gòu) A B C F D E (a) G A B C D E F G (b) typedef struct node ElemType data; struct node*sonsMaxSons;TSonNode; 圖圖 定義定義圖圖(Graph)G(Graph)G由兩個(gè)集合由兩個(gè)集合V(Vertex)V(Vertex)和和