第一講算法基礎

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

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

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

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

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

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

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

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

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

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

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

12、。然語言來設計。 （算法語言）算法語言）優(yōu)點：表達能力強，抽象性強，容易理解優(yōu)點：表達能力強，抽象性強，容易理解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）高級程序設計語言描述法）高級程序設計語言描述法優(yōu)點：能由計算機執(zhí)行優(yōu)點：能由計算機執(zhí)行 缺點：抽象性差，對語言要求高缺點：抽象性差，對語言要求高使用方法：算法需要驗證使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)注意事項：將算法寫成子函數(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ù)學模型擬制數(shù)學模型擬制-建立符合要求數(shù)學模型，設計相關約束條件建立符合要求數(shù)學模型，設計相關約束條件算法詳細設計算法詳細設計-選擇算法設計策略，確定數(shù)據(jù)結構選擇算法設計策略，確定數(shù)據(jù)結構算法描述算法描述-描述工具將

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

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

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

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

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

19、符號 1. 大大O符號符號(上界）上界）定義定義1.1 若存在兩個正的常數(shù)若存在兩個正的常數(shù)c和和n0，對于任意，對于任意nn0，都有，都有T( (n)cf( (n) )，則稱，則稱T( (n) )=O( (f( (n)n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前的之前的情況無關情況無關緊要緊要T( (n) )cf( (n) )f(N)是是T(N)的一個的一個上界上界，即即T(N)的階不高于的階不高于f(N)的階的階 根據(jù)根據(jù)O O的定義，的定義，容易證明它有如下運算規(guī)則：容易證明它有如下運算規(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是一個正的常數(shù)；是一個正的常數(shù)； (5)f=O(f)(5)f=O(f)2. 大大符號符號 （下界）定義定義1.2 若存在兩個正的常數(shù)若存在兩個正的常數(shù)c和和n0，對于任意，對于任意nn0，都有，都有T( (n)cg( (n) )，則稱，則稱T( (n) )=( (g( (n)n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之 前 的之 前 的情 況 無

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

22、且僅當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的漸進上界 O(n)算法分析中常見的復雜性函數(shù)算法分析中常見的復雜性函數(shù) 幾種常見的時間復雜度函數(shù)按數(shù)量級從小幾種常見的時間復雜度函數(shù)按數(shù)量級從小到大的順序依次是：到大的順序依次是： (1), (logn)，(sqrt(n)，(n)，(nlogn)，(n2)，(n3)，(2n)，(n!) 在多項式中，在多項式中，n的最高次指數(shù)的最高次指數(shù)是最主要的決是最主要的決定因素，常數(shù)項、低次冪項和系數(shù)都是次定因素，常數(shù)項、低次

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

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

25、用的存儲空間包括 算法自身 輸入、輸出輸入、輸出 輔助空間輔助空間 空間復雜度空間復雜度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ù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自已，稱為遞歸。直接或間接調(diào)用自身的算法稱為遞歸算法 。 采用遞歸算法來求解問題的一般步驟： 分析問題，尋找遞歸關系

26、 找出停止條件 構建函數(shù)體n的階乘00)!1(1!nnnnn停止條件停止條件遞歸關系遞歸關系停止條件與遞歸關系是遞歸函數(shù)的兩個要素，停止條件與遞歸關系是遞歸函數(shù)的兩個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結果。次計算后得出結果。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個元素，它們的編號為個元素，它們的編號為1,

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

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

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

30、)(n-2) .2T(1)=n! 時間復雜度：O(n!)1n1)nT(n1nO(1)T(n) 遞歸算法的空間復雜度：遞歸算法的空間復雜度：算法的遞歸深度算法的遞歸深度 全排列算法全排列算法perm共執(zhí)行了共執(zhí)行了n次遞歸次遞歸 深度為深度為n 空間復雜度空間復雜度(遞歸遞歸)：O(n)回到Fibonacci數(shù)列問題function Fib1(n)if n = 1 return 1if n = 2 return 1return Fib1(n-1) + Fib1(n-2)同一個子問題被反復求解!Fibonacci數(shù)列一個較好的算法數(shù)列一個較好的算法子問題子問題: 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 它有多快它有多快?運算數(shù)與運算數(shù)與n成比例成比例. 以前的方法以前的方法: 20.7nF200 現(xiàn)在可在合理時間內(nèi)計算出來現(xiàn)在可在合理時間內(nèi)計算出來, F2000 和和 F20000也一樣也一樣.啟示啟示 : 恰當?shù)乃惴ㄊ故虑閺氐赘挠^恰當?shù)乃惴ㄊ故虑閺氐赘挠^ 。第三個算法第三個算法用矩陣重寫用矩陣

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

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

34、所在的最大層次樹中葉子結點所在的最大層次任何一棵非空樹是一個二元組任何一棵非空樹是一個二元組 Tree = （root，F(xiàn)）其中：其中：root 被稱為根結點，被稱為根結點， F 被稱為子樹森林被稱為子樹森林森林：森林：是是 m（m0）棵互）棵互不相交的樹的集合不相交的樹的集合ArootBEFKLCGDHIJMF 樹的存儲結構 雙親存儲結構雙親存儲結構 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; 鏈存

35、儲結構鏈存儲結構 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由兩個集合由兩個集合V(Vertex)V(Vertex)和和E(Edge)E(Edge)組組成成, ,記為記為G=(V,E),G=(V,E),其中其中V V是頂點的有限集合是頂點的有限集合, ,記記為為V(G),EV(G),E是連接是連接V V中兩個不同頂點中兩個不同頂點( (頂點對頂點對) )的的邊的有限集合邊的有限集合, ,記為記為E(G)E(G)。EA