數(shù)據(jù)結構北京大理工學計算機科學與技術學院Page數(shù)據(jù)結構袁武yuan

1、數(shù)據(jù)結構數(shù)據(jù)結構袁武袁武北京理工大學計算機科學與技術學院北京理工大學計算機科學與技術學院軟件研究所軟件研究所北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 2教學目的教學目的n掌握常用的基本數(shù)據(jù)結構的掌握常用的基本數(shù)據(jù)結構的ADT及其應用及其應用n學會合理地組織數(shù)據(jù)學會合理地組織數(shù)據(jù), 有效地表有效地表示數(shù)據(jù)示數(shù)據(jù), 有效地處理數(shù)據(jù)有效地處理數(shù)據(jù)n基本掌握算法的設計分析技術基本掌握算法的設計分析技術n提高程序設計的質(zhì)量提高程序設計的質(zhì)量北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 3教學要求教學要求n平時作業(yè)和上機實驗平時作業(yè)和上機實驗

2、30n期末閉卷筆試期末閉卷筆試 70北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 4誠信誠信n端正學習態(tài)度、調(diào)動學習興趣端正學習態(tài)度、調(diào)動學習興趣n提倡討論，但嚴禁抄襲提倡討論，但嚴禁抄襲n可以討論思路，請同學看算法的邏輯問題可以討論思路，請同學看算法的邏輯問題和效率問題。和效率問題。n但要親自動手實現(xiàn)。但要親自動手實現(xiàn)。n發(fā)現(xiàn)抄襲，則抄襲者和被抄襲者本次發(fā)現(xiàn)抄襲，則抄襲者和被抄襲者本次作業(yè)或上機題計作業(yè)或上機題計0分。以后的作業(yè)題會分。以后的作業(yè)題會得到重點檢查。得到重點檢查。北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 5按時提交

3、作業(yè)，嚴禁抄襲按時提交作業(yè)，嚴禁抄襲n作業(yè)和上機實驗都必須在指定的期限內(nèi)完成并作業(yè)和上機實驗都必須在指定的期限內(nèi)完成并提交提交n當周完成四選一的練習題當周完成四選一的練習題n上機實驗：每次三道題，二周完成上機實驗：每次三道題，二周完成北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 6網(wǎng)絡教室地址網(wǎng)絡教室地址http:/ Page 7教材教材n嚴蔚敏嚴蔚敏,吳偉民編吳偉民編.數(shù)據(jù)結構數(shù)據(jù)結構（C語言版）語言版）M.北京北京:清華大清華大學出版社學出版社,1997年年4月月. 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 8教學參考書教學參

4、考書(續(xù)續(xù))n美美Mark Allen Weiss.陳越改編陳越改編.Data Structures and Algorithm Analysis in C(Second Edition)M.北京北京:人民郵電出版人民郵電出版社社,2005.n田魯懷田魯懷.數(shù)據(jù)結構數(shù)據(jù)結構M.北京北京:電子工業(yè)出版電子工業(yè)出版社社,2006.n美美Ellis Horowitz等等.李建中等譯李建中等譯.數(shù)據(jù)結構數(shù)據(jù)結構（C語言版）語言版）M.北京北京:機械工業(yè)出版機械工業(yè)出版社社,2006. n 嚴蔚敏，嚴蔚敏，數(shù)據(jù)結構題集數(shù)據(jù)結構題集，清華大學出版，清華大學出版社社北京大理工學計算機科學與技術學院北京大理工

5、學計算機科學與技術學院 Page 9教學參考書教學參考書(續(xù)續(xù))nDonald E. Knuth, The Art of Computer Programming, Addison Wesley. Vol. 1， Vol 3. 國防工業(yè)出版社影印。（蘇運霖譯）國防工業(yè)出版社影印。（蘇運霖譯）nThomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press. 高高等教育出版社影印。等教育出版社影印。nWilliam Ford，Data Stru

6、cture with C+，清華大學出版社，清華大學出版社北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 10第一章第一章 概論概論n1.1 為什么要學習數(shù)據(jù)結構為什么要學習數(shù)據(jù)結構n1.2 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構n1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n1.4 算法的特性及分類算法的特性及分類n1.5 算法的效率度量算法的效率度量n1.6 數(shù)據(jù)結構的選擇和評價數(shù)據(jù)結構的選擇和評價北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 111.1 為什么要學習數(shù)據(jù)結構為什么要學習數(shù)據(jù)結構n計算機軟件與理論學科的計算機軟件與理論學科的專業(yè)基礎專業(yè)基

7、礎課程課程 n后續(xù)專業(yè)課程學習的后續(xù)專業(yè)課程學習的必要必要知識與技能準備知識與技能準備 n編譯技術要使用棧、散列表及語法樹編譯技術要使用棧、散列表及語法樹 n操作系統(tǒng)中用隊列、存儲管理表及目錄樹操作系統(tǒng)中用隊列、存儲管理表及目錄樹 n數(shù)據(jù)庫系統(tǒng)運用線性表、多鏈表、及索引樹數(shù)據(jù)庫系統(tǒng)運用線性表、多鏈表、及索引樹 netc.n增強學生增強學生求解復雜問題求解復雜問題的能力的能力 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 121.2 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構(data structure) n數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構n數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構n數(shù)據(jù)的運算

8、數(shù)據(jù)的運算 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 131.2.1 數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構 n反映了我們對數(shù)據(jù)含義的解釋反映了我們對數(shù)據(jù)含義的解釋n數(shù)據(jù)的邏輯結構可以用數(shù)據(jù)的邏輯結構可以用一組數(shù)據(jù)一組數(shù)據(jù)（表示為結點集合（表示為結點集合K），以及這些數(shù)據(jù)之間的），以及這些數(shù)據(jù)之間的一組二元關系一組二元關系（關系集合（關系集合R）來表示：來表示：( K ，R )nK是由是由有限個有限個結點組成的集合，每一個結點都代表一個數(shù)據(jù)結點組成的集合，每一個結點都代表一個數(shù)據(jù)或一組有明確結構的數(shù)據(jù)或一組有明確結構的數(shù)據(jù)n而關系集而關系集R是定義在集合是定義在集合K上

9、的一組關系，其中每個關系上的一組關系，其中每個關系(relation) r（rR）都是）都是KK上的二元關系上的二元關系，用它描述結，用它描述結點數(shù)據(jù)之間的邏輯關系點數(shù)據(jù)之間的邏輯關系 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 14數(shù)據(jù)的邏輯結構（示例）數(shù)據(jù)的邏輯結構（示例） n家族人員家族人員n把每個成員個體的屬性描述作為數(shù)據(jù)結點，而全部人員組成把每個成員個體的屬性描述作為數(shù)據(jù)結點，而全部人員組成結點集結點集Kn家族的各類親屬關系就是一組關系家族的各類親屬關系就是一組關系R, 其中如母系血緣關系其中如母系血緣關系r、遠親關系遠親關系r*、和非血緣的親情關系、

10、和非血緣的親情關系r等等，每一個關系要給等等，每一個關系要給出具體人員的關系元組出具體人員的關系元組n例如：母子關系（王愛蓮，張選）例如：母子關系（王愛蓮，張選） 兄弟關系（張選，張立）兄弟關系（張選，張立） 妯娌關系妯娌關系 （王愛蓮，李美英）（王愛蓮，李美英）北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 15結點的類型結點的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n整數(shù)類型整數(shù)類型(integer)：該類型規(guī)定了所能表示的整數(shù)范圍，：該類型規(guī)定了所能表示的整數(shù)范圍，在計算機中一般使用在計算機中一般使用1個字節(jié)個字節(jié)到到4個字節(jié)個字節(jié)來存儲整數(shù)來存儲整數(shù)n實數(shù)類型實數(shù)類

11、型(real)：計算機的浮點數(shù)據(jù)類型所能表示的數(shù)值范：計算機的浮點數(shù)據(jù)類型所能表示的數(shù)值范圍和精度是圍和精度是有限有限的。的。 機器一般使用機器一般使用4個字節(jié)個字節(jié)到到8個字節(jié)個字節(jié)來存來存儲浮點數(shù)儲浮點數(shù)n布爾類型布爾類型(boolean)：取值為：取值為真真(true)和假和假(false)，在，在C+語言中一般使用整數(shù)語言中一般使用整數(shù)0表示表示false，用非，用非0表示真表示真 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 16結點的類型結點的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n字符類型字符類型(char)：用：用單個字節(jié)單個字節(jié)（8bit，最高位，最高

12、位bit為為0）表示）表示ASCII字符集中的字符。字符集中的字符。n漢字符號需要使用漢字符號需要使用2個字節(jié)個字節(jié)（每個字節(jié)的最高位（每個字節(jié)的最高位bit為為1）的編碼，單個字節(jié)對于漢字是沒有獨立含義的。的編碼，單個字節(jié)對于漢字是沒有獨立含義的。北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 17結點的類型結點的類型n在在C中把雙字節(jié)表示中文符號的字節(jié)類型稱中把雙字節(jié)表示中文符號的字節(jié)類型稱為為w_char類型（類型（wide character）。）。n目前國際上已經(jīng)采用了統(tǒng)一的擴展字符集合標準目前國際上已經(jīng)采用了統(tǒng)一的擴展字符集合標準UNICODE，這一標準

13、允許英、日、韓、阿拉伯，這一標準允許英、日、韓、阿拉伯語等文字的混合文字處理語等文字的混合文字處理北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 18結點的類型結點的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n指針類型指針類型(pointer)：用于表示機器內(nèi)存地址，指：用于表示機器內(nèi)存地址，指針表示指向某一內(nèi)存單元的地址。針表示指向某一內(nèi)存單元的地址。n由于機器的指令系統(tǒng)一般采用由于機器的指令系統(tǒng)一般采用32 bit或或64bit的地址長度，的地址長度，所以指針類型也相應地用所以指針類型也相應地用4個字節(jié)個字節(jié)或或8個字節(jié)個字節(jié)來表示一個來表示一個指針。指針。北京大理工學計

14、算機科學與技術學院北京大理工學計算機科學與技術學院 Page 19n指針值的存儲和指針值的運算方式，在形式上與指針值的存儲和指針值的運算方式，在形式上與正整數(shù)相似。正整數(shù)相似。n但指針的運算一般僅限于兩個指針地址的比較，但指針的運算一般僅限于兩個指針地址的比較，加減，或?qū)σ粋€指針增減一個整數(shù)量等加減，或?qū)σ粋€指針增減一個整數(shù)量等北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 20結點的類型結點的類型 n復合數(shù)據(jù)類型復合數(shù)據(jù)類型n復合類型是由基本數(shù)據(jù)類型組合而成的數(shù)據(jù)結構類型。例如：復合類型是由基本數(shù)據(jù)類型組合而成的數(shù)據(jù)結構類型。例如：在程序語言中常用的數(shù)組類型，結構

15、（記錄）類型等皆屬復在程序語言中常用的數(shù)組類型，結構（記錄）類型等皆屬復合數(shù)據(jù)類型合數(shù)據(jù)類型n復合數(shù)據(jù)類型本身，又可以復合數(shù)據(jù)類型本身，又可以參與定義參與定義結構更為復雜的結點類結構更為復雜的結點類型。型。n結點的類型不限于基本數(shù)據(jù)類型，可以根據(jù)應用的需要來靈結點的類型不限于基本數(shù)據(jù)類型，可以根據(jù)應用的需要來靈活定義活定義 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 21結構的分類結構的分類 n討論邏輯結構（討論邏輯結構（K,R）的分類，一般把討論重點放在）的分類，一般把討論重點放在關系集關系集R上。用上。用R的性質(zhì)來刻劃數(shù)據(jù)結構的特點，并對的性質(zhì)來刻劃數(shù)據(jù)結構

16、的特點，并對數(shù)據(jù)結構進行分類數(shù)據(jù)結構進行分類 n線性結構（線性結構（linear structure）n樹型結構（樹型結構（tree structure） n圖結構（圖結構（graph structure）北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 22線性結構線性結構n這種結構在程序設計中這種結構在程序設計中應用最多應用最多。n它的關系它的關系r 是一種是一種線性關系線性關系，或稱為，或稱為前后關系前后關系，有時也稱為有時也稱為大小關系大小關系。關系。關系r是是有向有向的，且滿足的，且滿足全全序性序性和和單索性單索性等約束條件等約束條件n全序性是指，線性結構的

17、全部結點兩兩皆可以比較前后（關全序性是指，線性結構的全部結點兩兩皆可以比較前后（關系系r）n單索性是指，每一個結點單索性是指，每一個結點x都存在唯一的一個直接后繼結點都存在唯一的一個直接后繼結點y。如果其他結點。如果其他結點z在在y之前，則這個之前，則這個z也一定在也一定在x之前，不會之前，不會在在x，y之間之間 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 23樹型結構樹型結構 n樹型結構簡稱樹結構，或稱為層次結構。其關系樹型結構簡稱樹結構，或稱為層次結構。其關系r稱為層次關系，稱為層次關系，或稱或稱父子關系父子關系、上下級關系上下級關系等等n每一個結點可以有每

18、一個結點可以有多于一個的多于一個的直接下級直接下級，但是它只能有，但是它只能有唯唯一的一的直接上級直接上級。樹型結構的最高層次的結點稱為。樹型結構的最高層次的結點稱為根（根（root）結點結點。只有它。只有它沒有父結點沒有父結點n從數(shù)學上看，樹型結構和圖結構的基本區(qū)別就是從數(shù)學上看，樹型結構和圖結構的基本區(qū)別就是“每個結點是每個結點是否否僅僅從屬一個直接上級僅僅從屬一個直接上級”。而線性結構和樹型結構的基本區(qū)。而線性結構和樹型結構的基本區(qū)別是別是“每個結點是否每個結點是否僅僅有一個直接后繼僅僅有一個直接后繼”。n樹型結構存在著很多變種，如二叉樹結構，堆結構等，它們都樹型結構存在著很多變種，如二

19、叉樹結構，堆結構等，它們都有著各自獨特的有效應用有著各自獨特的有效應用北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 24圖結構圖結構 n圖結構有時稱為結點互聯(lián)的圖結構有時稱為結點互聯(lián)的網(wǎng)絡結構網(wǎng)絡結構，因特網(wǎng)的網(wǎng)頁，因特網(wǎng)的網(wǎng)頁鏈接關系就是一個非常復雜的圖結構鏈接關系就是一個非常復雜的圖結構n對于圖結構的關系對于圖結構的關系r沒有加任何約束。這樣也就無法象沒有加任何約束。這樣也就無法象線性結構及樹結構那樣，利用關系線性結構及樹結構那樣，利用關系r的約束來設計圖結的約束來設計圖結構的存儲結構構的存儲結構n在日常應用中圖結構往往只是層次結構的一種擴展在日常應用中圖結構

20、往往只是層次結構的一種擴展允許結點具有多個允許結點具有多個直接上級結點直接上級結點，關系，關系r表現(xiàn)表現(xiàn)為樹型結構約束的放松為樹型結構約束的放松 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 25結點和結構結點和結構 n對于數(shù)據(jù)結構（對于數(shù)據(jù)結構（K,R），結點數(shù)據(jù)類型不限于基本數(shù)），結點數(shù)據(jù)類型不限于基本數(shù)據(jù)類型，可以根據(jù)應用需要來靈活設計結點的數(shù)據(jù)類據(jù)類型，可以根據(jù)應用需要來靈活設計結點的數(shù)據(jù)類型型n可以認為數(shù)據(jù)結構的設計是一層一層地進行的可以認為數(shù)據(jù)結構的設計是一層一層地進行的n先明確先明確數(shù)據(jù)結點數(shù)據(jù)結點，及其，及其主要關系主要關系r n在分析關系在分析關

21、系r的同時，也要分析其數(shù)據(jù)結點的的同時，也要分析其數(shù)據(jù)結點的數(shù)據(jù)類型數(shù)據(jù)類型n如果數(shù)據(jù)結點的邏輯結構比較復雜，那么把它作為下一個層如果數(shù)據(jù)結點的邏輯結構比較復雜，那么把它作為下一個層次，再分析下一層次的邏輯結構次，再分析下一層次的邏輯結構n這是一種這是一種自頂向下自頂向下的分析設計方法的分析設計方法 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 261.2.2 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構n計算機的主存儲器的特性計算機的主存儲器的特性n其存儲空間提供了一種具有其存儲空間提供了一種具有非負整數(shù)非負整數(shù)地址編地址編碼的，碼的，相鄰單元相鄰單元的集合，其基本的存儲單元的

22、集合，其基本的存儲單元是是字節(jié)字節(jié)n計算機的指令具有計算機的指令具有按地址隨機訪問按地址隨機訪問存儲空間存儲空間內(nèi)任意單元的能力，訪問不同地址所需的訪內(nèi)任意單元的能力，訪問不同地址所需的訪問時間基本相同問時間基本相同 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 271.2.2 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構n用數(shù)學上的映射來表示，數(shù)據(jù)的存儲結構是建立一種用數(shù)學上的映射來表示，數(shù)據(jù)的存儲結構是建立一種映射，對于數(shù)據(jù)邏輯結構（映射，對于數(shù)據(jù)邏輯結構（ K , r ）,其中其中rRn對它的結點集合對它的結點集合K建立一個從建立一個從K到存儲器到存儲器M的單元的映射：的單

23、元的映射：KM，對于每一個結點，對于每一個結點jK都對應一個都對應一個唯一唯一的的連續(xù)存儲連續(xù)存儲區(qū)區(qū)域域cM。n每一個關系元組（每一個關系元組（j1 ,j2）r（其中（其中j1, j2K是結點），亦是結點），亦即即j1, j2的邏輯后繼關系應映射為存儲單元的地址順序關系的邏輯后繼關系應映射為存儲單元的地址順序關系（或指針的地址指向關系）。（或指針的地址指向關系）。n四種基本存儲映射方法：順序、鏈接、索引、散列四種基本存儲映射方法：順序、鏈接、索引、散列北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 28順序（順序（sequential）的方法）的方法 n用一塊無空

24、隙的存儲區(qū)域存儲數(shù)據(jù)稱為用一塊無空隙的存儲區(qū)域存儲數(shù)據(jù)稱為順序順序存儲存儲n順序存儲把一組結點存儲在按順序存儲把一組結點存儲在按地址相鄰地址相鄰的順的順序存儲單元里，結點間的邏輯后繼關系用存序存儲單元里，結點間的邏輯后繼關系用存儲單元的自然順序關系來表達儲單元的自然順序關系來表達 n順序存儲法為使用整數(shù)編碼來訪問數(shù)據(jù)結點順序存儲法為使用整數(shù)編碼來訪問數(shù)據(jù)結點提供了便利提供了便利 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 29順序（順序（sequential）的方法）的方法 n順序存儲結構稱為順序存儲結構稱為緊湊存儲結構緊湊存儲結構，其緊湊性是指它，其緊湊性是指

25、它的存儲空間除了存儲有用數(shù)據(jù)外，沒有用于存儲其的存儲空間除了存儲有用數(shù)據(jù)外，沒有用于存儲其他附加的信息他附加的信息n緊湊性可以用緊湊性可以用存儲密度存儲密度來度量：它是一個存儲來度量：它是一個存儲結構所存儲的結構所存儲的有用數(shù)據(jù)有用數(shù)據(jù)和該結構（包括附加信和該結構（包括附加信息）整個存儲空間大小之比。息）整個存儲空間大小之比。n有時為了有時為了用空間換取時間用空間換取時間，在存儲結構中存儲，在存儲結構中存儲一些附加信息還是很必要的。譬如用于提高算法的一些附加信息還是很必要的。譬如用于提高算法的執(zhí)行速度，或者讓算法實現(xiàn)更為簡便等執(zhí)行速度，或者讓算法實現(xiàn)更為簡便等 北京大理工學計算機科學與技術學院

26、北京大理工學計算機科學與技術學院 Page 30順序（順序（sequential）的方法）的方法 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 31鏈接（鏈接（linked）的方法）的方法 n利用指針，在結點的存儲結構中附加指針字段稱為利用指針，在結點的存儲結構中附加指針字段稱為鏈接法鏈接法。兩個結點的邏輯后繼關系可以用指針的指。兩個結點的邏輯后繼關系可以用指針的指向來表達向來表達n任意的邏輯關系任意的邏輯關系r，也可以使用這種指針地址來表達。，也可以使用這種指針地址來表達。一般的做法是將數(shù)據(jù)結點分為兩部分一般的做法是將數(shù)據(jù)結點分為兩部分:n一部分存放結點本身的數(shù)

27、據(jù)，稱為一部分存放結點本身的數(shù)據(jù)，稱為數(shù)據(jù)字段數(shù)據(jù)字段n另一部分存放指針，稱另一部分存放指針，稱指針字段指針字段，鏈接到某個后繼結點，鏈接到某個后繼結點，指向它的存儲單元的開始地址。多個相關結點的依次鏈接指向它的存儲單元的開始地址。多個相關結點的依次鏈接就會形成就會形成鏈索鏈索北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 32鏈接（鏈接（linked）的方法）的方法 n對于經(jīng)常增刪結點的復雜數(shù)據(jù)結構，順序存儲往往會對于經(jīng)常增刪結點的復雜數(shù)據(jù)結構，順序存儲往往會遇到困難，鏈接方法結合遇到困難，鏈接方法結合new動態(tài)存儲為這些復雜問動態(tài)存儲為這些復雜問題提供了解決方法

28、題提供了解決方法n它也有缺陷：它也有缺陷：n為了訪問結點集為了訪問結點集K中某個結點，必須用該結點的存儲指針中某個結點，必須用該結點的存儲指針n當不知道結點指針時，為了在結點集當不知道結點指針時，為了在結點集K中尋找某個符合條件中尋找某個符合條件的結點，就要沿著鏈接結點的鏈索，一個個結點比較搜索。的結點，就要沿著鏈接結點的鏈索，一個個結點比較搜索。所需花費的時間是較大的所需花費的時間是較大的 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 33鏈接（鏈接（linked）的方法）的方法 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 34索

29、引（索引（indexing）的方法）的方法 n索引法是順序存儲法的一種推廣，它也使用整數(shù)編碼來訪問數(shù)索引法是順序存儲法的一種推廣，它也使用整數(shù)編碼來訪問數(shù)據(jù)結點位置據(jù)結點位置n索引方法是要建造一個由整數(shù)域索引方法是要建造一個由整數(shù)域Z映射到存儲地址域映射到存儲地址域D的函數(shù)的函數(shù)Y：ZD，把，把結點的整數(shù)索引值結點的整數(shù)索引值 zZ映射到映射到結點的存儲地址結點的存儲地址 dD 。它稱為。它稱為索引函數(shù)索引函數(shù)，一般而言它并不象數(shù)組那樣，是簡，一般而言它并不象數(shù)組那樣，是簡單的線性函數(shù)。單的線性函數(shù)。n當數(shù)據(jù)結點長度不等的情況下，索引函數(shù)就無法用線性表達式當數(shù)據(jù)結點長度不等的情況下，索引函數(shù)就

30、無法用線性表達式給出給出北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 35索引（索引（indexing）的方法）的方法n為了構造任意的索引函數(shù)，可以為索引函數(shù)提供附加為了構造任意的索引函數(shù)，可以為索引函數(shù)提供附加的存儲空間，稱為的存儲空間，稱為索引表索引表Sn索引表中每一元素是指向數(shù)據(jù)結點的指針。因為索引索引表中每一元素是指向數(shù)據(jù)結點的指針。因為索引表表S由等長元素（指針）組成，所以可以進行線性的由等長元素（指針）組成，所以可以進行線性的索引計算：索引計算： 始址始址(元素元素Si) 始址始址(元素元素S0) i （指針尺寸）（指針尺寸）n通過上述公式，由索引號通

31、過上述公式，由索引號i可以計算出索引表中的單可以計算出索引表中的單元元Si的始址，再通過讀出的始址，再通過讀出Si元素的內(nèi)容（是指元素的內(nèi)容（是指針），訪問真正需要訪問的數(shù)據(jù)結點針），訪問真正需要訪問的數(shù)據(jù)結點北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 36索引（索引（indexing）的方法）的方法n索引方法也付出了存儲開銷，其數(shù)據(jù)結點要附索引方法也付出了存儲開銷，其數(shù)據(jù)結點要附加用于指針的存儲空間。加用于指針的存儲空間。n索引方法在程序設計中是一種經(jīng)常使用的方法，索引方法在程序設計中是一種經(jīng)常使用的方法，其主要原因是對于非順序的存儲結構來說，使其主要原因是對

32、于非順序的存儲結構來說，使用索引表是快速地由整數(shù)索引值找到其對應數(shù)用索引表是快速地由整數(shù)索引值找到其對應數(shù)據(jù)結點的據(jù)結點的唯一唯一方法方法北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 37索引（索引（indexing）的方法）的方法北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 38散列（散列（hashing）的方法）的方法 n散列方法是索引方法的一種延伸和擴展散列方法是索引方法的一種延伸和擴展n利用一種稱為利用一種稱為散列函數(shù)散列函數(shù)(hash functions)進行索引值的計算，然后通過索引表求出結點的進行索引值的計算，然后通過索

33、引表求出結點的指針地址指針地址n散列函數(shù)是將字符串散列函數(shù)是將字符串s映射到非負整數(shù)映射到非負整數(shù)z的一類函的一類函數(shù)數(shù)h: S Z ， 對任意的對任意的 s S，散列函數(shù)，散列函數(shù) h(s)=z，z Z北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 39散列（散列（hashing）的方法）的方法 n散列函數(shù)散列函數(shù)h(s)除了它取非負整數(shù)值外，除了它取非負整數(shù)值外，關鍵的問題：關鍵的問題：n恰當?shù)剡x擇散列函數(shù)恰當?shù)剡x擇散列函數(shù)n如何建造散列表如何建造散列表n在構建散列表的中間解決在構建散列表的中間解決碰撞碰撞的辦的辦法法 北京大理工學計算機科學與技術學院北京大理工

34、學計算機科學與技術學院 Page 40抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstract data structure) n抽象數(shù)據(jù)類型是描述數(shù)據(jù)結構的一種理論工具抽象數(shù)據(jù)類型是描述數(shù)據(jù)結構的一種理論工具n特點是把數(shù)據(jù)結構作為獨立于應用程序的一種抽象特點是把數(shù)據(jù)結構作為獨立于應用程序的一種抽象代數(shù)結構來描述代數(shù)結構來描述n因此在很大程度上可以使人們獨立于程序的實現(xiàn)細因此在很大程度上可以使人們獨立于程序的實現(xiàn)細節(jié)來理解數(shù)據(jù)結構的主要性質(zhì)和約束條件節(jié)來理解數(shù)據(jù)結構的主要性質(zhì)和約束條件北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 41抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct

35、data structure) n抽象數(shù)據(jù)類型不同于具體的數(shù)據(jù)結構，前者所描述的是抽象數(shù)據(jù)類型不同于具體的數(shù)據(jù)結構，前者所描述的是一種模板以及模板的結構和性質(zhì)。而模板的類型參數(shù)一種模板以及模板的結構和性質(zhì)。而模板的類型參數(shù)T（元素的數(shù)據(jù)類型）必須用具體的數(shù)據(jù)類型所代入，才（元素的數(shù)據(jù)類型）必須用具體的數(shù)據(jù)類型所代入，才能成為具體的數(shù)據(jù)類型能成為具體的數(shù)據(jù)類型n抽象數(shù)據(jù)類型是把數(shù)據(jù)結構作為獨立于應用程序的一種抽象數(shù)據(jù)類型是把數(shù)據(jù)結構作為獨立于應用程序的一種抽象抽象，目的是使人們能夠獨立于程序的實現(xiàn)細節(jié)來理解，目的是使人們能夠獨立于程序的實現(xiàn)細節(jié)來理解數(shù)據(jù)結構的特性數(shù)據(jù)結構的特性 北京大理工學計算

36、機科學與技術學院北京大理工學計算機科學與技術學院 Page 42抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n抽象數(shù)據(jù)結構抽象數(shù)據(jù)結構 n的取值空間的取值空間n的關系集合的關系集合n的運算集的運算集 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 43抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n的取值空間：給出該數(shù)據(jù)結構的所有可能取值的集合。為此的取值空間：給出該數(shù)據(jù)結構的所有可能取值的集合。為此需要準確地給出該數(shù)據(jù)結構需要準確地給出該數(shù)據(jù)結構 的組成元素的取值類型的組成元素的取值類型 n 的取值空間

37、大小取決于它的元素類型的取值空間大小取決于它的元素類型T。具體的數(shù)據(jù)結構是。具體的數(shù)據(jù)結構是 和和T聯(lián)合確定的聯(lián)合確定的 n對于取值空間，進一步說明它的大小是否可以動態(tài)改變是很重要對于取值空間，進一步說明它的大小是否可以動態(tài)改變是很重要的的 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 44抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n的運算集：一般使用函數(shù)來定義運算，參與運算的的運算集：一般使用函數(shù)來定義運算，參與運算的對象成為函數(shù)的輸入?yún)?shù)，運算結果是函數(shù)值對象成為函數(shù)的輸入?yún)?shù)，運算結果是函數(shù)值n為適合不同應用領域以及它的元素

38、類型為適合不同應用領域以及它的元素類型T的不同，同一的不同，同一個結構的含義會有所不同，也就需要適當?shù)靥砑右恍﹤€結構的含義會有所不同，也就需要適當?shù)靥砑右恍┬碌倪\算種類新的運算種類n運算集的選擇也會受到該數(shù)據(jù)結構的存儲方案的影響運算集的選擇也會受到該數(shù)據(jù)結構的存儲方案的影響北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 45抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義數(shù)據(jù)關系：數(shù)據(jù)關系：數(shù)據(jù)關系的定義數(shù)據(jù)關系的定義基本操作：基本操作：基本操作的定義基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)

39、類型名北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 46抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述(續(xù)續(xù))基本操作名（參數(shù)表）基本操作名（參數(shù)表） 初始條件：初始條件： 操作結果：操作結果：賦值參數(shù)賦值參數(shù): 只為操作提供輸入值。只為操作提供輸入值。引用參數(shù)：以引用參數(shù)：以&打頭，除可提供輸入值之外，還將返回操作結果。打頭，除可提供輸入值之外，還將返回操作結果。初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。不滿足，則操作失敗，并返回相應出錯信息。操作結果：說

40、明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返操作結果：說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果?；氐慕Y果。北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 47ADT示例：復數(shù)定義示例：復數(shù)定義 ADT Complex 數(shù)據(jù)對象：數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關系：數(shù)據(jù)關系： R1 | e1是復數(shù)的實數(shù)部分是復數(shù)的實數(shù)部分, | e2 是復數(shù)的虛數(shù)部分是復數(shù)的虛數(shù)部分 基本操作：基本操作： InitComplex( &Z, v1, v2 ) 操作結果：構造復數(shù)操作結果：構造復數(shù)Z,其實部和虛部分別被賦以參數(shù)其實部和虛部

41、分別被賦以參數(shù)v1和和v2的值。的值。 DestroyComplex( &Z) 操作結果：復數(shù)操作結果：復數(shù)Z被銷毀。被銷毀。 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 48ADT示例：復數(shù)定義（續(xù)）示例：復數(shù)定義（續(xù)） GetReal( Z, &realPart ) 初始條件：復數(shù)已存在。初始條件：復數(shù)已存在。操作結果：用操作結果：用realPart返回復數(shù)返回復數(shù)Z的實部值。的實部值。GetImag( Z, &ImagPart )初始條件：復數(shù)已存在。初始條件：復數(shù)已存在。操作結果：用操作結果：用ImagPart返回復數(shù)返回復數(shù)Z的

42、虛部值。的虛部值。Add( z1,z2, &sum ) 初始條件：初始條件：z1,z2是復數(shù)是復數(shù)。操作結果：用操作結果：用sum返回兩個復數(shù)返回兩個復數(shù)z1,z2的和值。的和值。 ADT Complex北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 49北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 501.4 算法及其特性算法及其特性n算法算法(algorithms)是為了求解問題而給出的是為了求解問題而給出的指令序列指令序列n程序程序是算法的一種實現(xiàn)，計算機按照程序逐步是算法的一種實現(xiàn)，計算機按照程序逐步執(zhí)行算法，實現(xiàn)對問題

43、的求解執(zhí)行算法，實現(xiàn)對問題的求解 n一個一個求解問題求解問題通常用該問題的輸入數(shù)據(jù)類型和通常用該問題的輸入數(shù)據(jù)類型和該問題所要求解的結果（算法的輸出數(shù)據(jù)）所該問題所要求解的結果（算法的輸出數(shù)據(jù)）所應遵循的性質(zhì)來描述應遵循的性質(zhì)來描述 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 511.4.1 算法及其特性算法及其特性n 算法應該具有如下性質(zhì)算法應該具有如下性質(zhì):n一定的通用性。一定的通用性。n對于那些符合輸入類型的任意輸入數(shù)據(jù)，都能根據(jù)算法進行問題求對于那些符合輸入類型的任意輸入數(shù)據(jù)，都能根據(jù)算法進行問題求解，并保證計算結果的正確性解，并保證計算結果的正確性n算

44、法的有效性。算法的有效性。n算法是有限條指令組成的指令序列，其中每一條指令都必須是能夠算法是有限條指令組成的指令序列，其中每一條指令都必須是能夠被確切執(zhí)行的，被人或機器所執(zhí)行。指令的類型應該明確規(guī)定，僅被確切執(zhí)行的，被人或機器所執(zhí)行。指令的類型應該明確規(guī)定，僅限于若干明確無誤的指令動作，是一個有限的指令集限于若干明確無誤的指令動作，是一個有限的指令集 。其結果應具。其結果應具有確定的數(shù)據(jù)類型，是能夠預期的有確定的數(shù)據(jù)類型，是能夠預期的北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 521.4.1 算法及其特性算法及其特性n算法的確定性。算法的確定性。n算法每執(zhí)行一步

45、之后，關于它的下一步，應該有明確的指示。下一算法每執(zhí)行一步之后，關于它的下一步，應該有明確的指示。下一步動作可以是條件判斷、分支指令、或順序執(zhí)行一條指令、或者指步動作可以是條件判斷、分支指令、或順序執(zhí)行一條指令、或者指示整個算法的結束等。算法的確定性要保證每一步之后都有關于下示整個算法的結束等。算法的確定性要保證每一步之后都有關于下一步動作的指令，不能缺乏下一步指令（被鎖住）或僅僅含有模糊一步動作的指令，不能缺乏下一步指令（被鎖?。┗騼H僅含有模糊不清的指令不清的指令n 算法的有窮性。算法的有窮性。n算法的執(zhí)行必須在有限步內(nèi)結束。換句話說，算法不能含有死循環(huán)算法的執(zhí)行必須在有限步內(nèi)結束。換句話說

46、，算法不能含有死循環(huán) 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 531.4.2 計算復雜性和算法的效率計算復雜性和算法的效率n根據(jù)計算理論根據(jù)計算理論(theory of computation)，存在著一，存在著一類問題雖然能夠被準確定義，但卻不存在能夠解決該類問題雖然能夠被準確定義，但卻不存在能夠解決該問題的算法。稱為問題的算法。稱為不可解問題不可解問題n計算復雜性理論計算復雜性理論(computational complexity theory)指出，理論上存在一大類難解問題，它們雖指出，理論上存在一大類難解問題，它們雖然存在著求解算法，但是在算法的計算

47、時間上，都是然存在著求解算法，但是在算法的計算時間上，都是組合爆炸型組合爆炸型的求解算法的求解算法北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 541.4.2 計算復雜性和算法的效率計算復雜性和算法的效率n所謂組合爆炸型，是指隨著問題的規(guī)模所謂組合爆炸型，是指隨著問題的規(guī)模n的增大，算的增大，算法的時間開銷不能約束在法的時間開銷不能約束在n的的k階多項式數(shù)量范圍內(nèi)。階多項式數(shù)量范圍內(nèi)。（其中（其中k是任意不依賴于是任意不依賴于n的常數(shù)）的常數(shù)） n根據(jù)計算復雜性理論，根據(jù)計算復雜性理論，難解問題難解問題的定義就是它的求解的定義就是它的求解算法均無法在多項式時間算法

48、均無法在多項式時間nk數(shù)量級內(nèi)解決（其中數(shù)量級內(nèi)解決（其中k是是任意正整數(shù)）。比較常見的難解問題有：圖論中的求任意正整數(shù)）。比較常見的難解問題有：圖論中的求最優(yōu)巡游路徑問題，判定命題邏輯公式是否為恒真等最優(yōu)巡游路徑問題，判定命題邏輯公式是否為恒真等北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 551.5 算法的執(zhí)行效率及其度量算法的執(zhí)行效率及其度量n解決同一個問題總是存在著多種算法，而算解決同一個問題總是存在著多種算法，而算法設計者在所法設計者在所花費的時間花費的時間和所和所使用的空間使用的空間資資源往往要兩者之間采取折中，采用某種以空源往往要兩者之間采取折中，采

49、用某種以空間資源換取時間資源的策略間資源換取時間資源的策略n算法設計者可以通過算法分析，判斷所提出算法設計者可以通過算法分析，判斷所提出的算法是否現(xiàn)實，設計出更好的算法的算法是否現(xiàn)實，設計出更好的算法 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 561.5.1算法的漸進分析算法的漸進分析(asymptotic analysis) n算法的漸進分析，簡稱算法的漸進分析，簡稱算法分析算法分析。算法在計算機。算法在計算機上實際執(zhí)行時，需要消耗時間資源（歸結為上實際執(zhí)行時，需要消耗時間資源（歸結為CPU執(zhí)行指令的總數(shù)），和使用空間資源（歸結為所執(zhí)行指令的總數(shù)），和使用空

50、間資源（歸結為所需占用的存儲單元數(shù)量，字節(jié)數(shù)）。需占用的存儲單元數(shù)量，字節(jié)數(shù)）。n由于算法分析和它所求解的問題規(guī)模直接有關，由于算法分析和它所求解的問題規(guī)模直接有關，因此通常將因此通常將問題規(guī)模問題規(guī)模n作為一個參照量，求算法的作為一個參照量，求算法的時空開銷和時空開銷和n的關系。的關系。 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 571.5.1算法的漸進分析算法的漸進分析(asymptotic analysis) n算法的漸進分析就是要估計，當數(shù)據(jù)規(guī)模算法的漸進分析就是要估計，當數(shù)據(jù)規(guī)模n逐逐步增大時，資源開銷步增大時，資源開銷T(n)的增長趨勢。的增長趨勢

51、。n從數(shù)量級大小的比較來考慮，當從數(shù)量級大小的比較來考慮，當n增大到一定增大到一定值以后，資源開銷的計算公式中影響最大的就值以后，資源開銷的計算公式中影響最大的就是是n的冪次最高的項，其他的常數(shù)項和低冪次的冪次最高的項，其他的常數(shù)項和低冪次項都是可以忽略的。項都是可以忽略的。 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 581.5.1算法的漸進分析算法的漸進分析(asymptotic analysis) n算法的漸進分析就是要得到一個大算法的漸進分析就是要得到一個大O漸進表達式，簡寫為：漸進表達式，簡寫為：rate n T(n) O( F(n) )n其中其中O是

52、數(shù)學分析常用符號是數(shù)學分析常用符號大大O，而而 F(n)是自變量為是自變量為n的某個具體的整的某個具體的整函數(shù)表達式，例如函數(shù)表達式，例如F(n)n2北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 59算法的漸進分析示例算法的漸進分析示例矩陣求和（矩陣求和（matrix_addition ）void matrix_addition(double *M1, double *M2, int k)/ 矩陣矩陣M1,M2求和，即兩兩元素求和，結果存回求和，即兩兩元素求和，結果存回M1/ kk是矩陣的規(guī)模是矩陣的規(guī)模 for (int i=0 ; ik; i+) for (i

53、nt j=0 ; jk; j+) /對應位置的矩陣元素相加對應位置的矩陣元素相加 M1ij = M1ij +M2ij ;北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 60算法的漸進分析示例算法的漸進分析示例矩陣求和（矩陣求和（matrix_addition ）n此問題的規(guī)模由輸入數(shù)據(jù)規(guī)模決定，主要是浮點矩陣此問題的規(guī)模由輸入數(shù)據(jù)規(guī)模決定，主要是浮點矩陣M1, M2的尺寸的尺寸n2*k2 n在漸進分析時，通常我們把浮點運算和數(shù)組元素的讀寫在漸進分析時，通常我們把浮點運算和數(shù)組元素的讀寫操作的執(zhí)行時間都看作在同一個數(shù)量級內(nèi)，忽略其執(zhí)行操作的執(zhí)行時間都看作在同一個數(shù)量級

54、內(nèi)，忽略其執(zhí)行時間的細微差別時間的細微差別n為了求出一個漸進估計的代數(shù)公式，若令為了求出一個漸進估計的代數(shù)公式，若令r是單個指令是單個指令執(zhí)行時間，那么對于矩陣加法程序，由于循環(huán)體每執(zhí)行執(zhí)行時間，那么對于矩陣加法程序，由于循環(huán)體每執(zhí)行一次，需要一次，需要p r時間，其中時間，其中p是一個常數(shù)倍數(shù)是一個常數(shù)倍數(shù) 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 61算法的漸進分析示例算法的漸進分析示例矩陣求和（矩陣求和（matrix_addition ）n考慮到兩重嵌套的考慮到兩重嵌套的for循環(huán)，一共執(zhí)行循環(huán)，一共執(zhí)行kk遍，因此，遍，因此，這個程序的時間開銷的漸進估

55、計式可以寫為這個程序的時間開銷的漸進估計式可以寫為T(n) p r nC。其中。其中C是一個不隨是一個不隨n而變化的常數(shù)，代表那些而變化的常數(shù)，代表那些在進入循環(huán)體前后計算機所作的輔助操作時間在進入循環(huán)體前后計算機所作的輔助操作時間n由此看出，矩陣加法的時間開銷是和問題規(guī)模由此看出，矩陣加法的時間開銷是和問題規(guī)模n成正比成正比的，或稱該算法（的時間開銷）是線性增長率的。簡寫的，或稱該算法（的時間開銷）是線性增長率的。簡寫為為rate n T(n) O(n )，即，即F(n)=n北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 621.5.1算法的漸進分析算法的漸進分析

56、(asymptotic analysis) n用于漸進分析的常見的用于漸進分析的常見的F(n)還有以下若干種還有以下若干種 ：nF(n) = 1, 常數(shù)函數(shù)，不依賴于常數(shù)函數(shù)，不依賴于nnF(n) = log n, 對數(shù)函數(shù)，它比線性函數(shù)對數(shù)函數(shù)，它比線性函數(shù)n增長慢增長慢nF(n) = n， 線性增長，隨著問題規(guī)模線性增長，隨著問題規(guī)模n而增長而增長 例如，例如，rate n（n個個a相加）相加） = rate n （n a） = O(n)nF(n) = n2，二階增長，二階增長 例如，例如，rate n i=1.n j=i.n ( a ) = O(n2)， 這是因為這是因為 i=1.n（a

57、 ( ni )）（）（a (n (n-1)/2)北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 631.5.1算法的漸進分析算法的漸進分析(asymptotic analysis) n用于漸進分析的常見的用于漸進分析的常見的F(n)還有以下若干種還有以下若干種 ：nF(n)= n log(n)，其增長率的階數(shù)低于二階，但高于，其增長率的階數(shù)低于二階，但高于一階線性。例如，一階線性。例如， rate n i=1.log n j=i.n ( a ) O( n log(n) )n F(n)= an 指數(shù)增長，隨問題規(guī)模指數(shù)增長，隨問題規(guī)模n而增長極快而增長極快 這種指數(shù)型

58、的漸進函數(shù)往往由遞歸定義的函數(shù)產(chǎn)生。例這種指數(shù)型的漸進函數(shù)往往由遞歸定義的函數(shù)產(chǎn)生。例 如函數(shù)如函數(shù)H(n)，令，令H(1)=1, 且且H(n)=2 H(n-1), 那么那么通過遞推可以計算出通過遞推可以計算出H(n) = 2(n-1)北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 641.5.2最壞、最好、和平均情況最壞、最好、和平均情況n在具體進行算法增長率估計時，往往會由于算法中在具體進行算法增長率估計時，往往會由于算法中的條件分支而遇到困難。的條件分支而遇到困難。n由于算法實際執(zhí)行的操作往往依賴于分支條件的走由于算法實際執(zhí)行的操作往往依賴于分支條件的走向，而

59、輸入數(shù)據(jù)的取值又影響這些分支走向，因此向，而輸入數(shù)據(jù)的取值又影響這些分支走向，因此很多算法都無法得出獨立于輸入數(shù)據(jù)的漸進估計。很多算法都無法得出獨立于輸入數(shù)據(jù)的漸進估計。n針對這一情況，提出了最壞情況估計、平均情況估針對這一情況，提出了最壞情況估計、平均情況估計、和計、和Theta（ 希塔）估計等三種方法希塔）估計等三種方法 北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 651.5.2示例示例求矩陣求矩陣M中絕對值最大的元素中絕對值最大的元素 double abs_biggest(double *M, int k) /求矩陣求矩陣M中絕對值最大的元素，中絕對值最大

60、的元素，kk是矩陣的規(guī)模是矩陣的規(guī)模 double current_big = 0;/臨時存儲單元，初始化為臨時存儲單元，初始化為0 for (int i=0 ; ik; i+) for (int j=0 ; j current_big) current_big = temp; / current_big存儲當前最大者存儲當前最大者 return current_big; /函數(shù)值返回函數(shù)值返回北京大理工學計算機科學與技術學院北京大理工學計算機科學與技術學院 Page 661.5.2示例示例求矩陣求矩陣M中絕對值最大的元素中絕對值最大的元素 n輸入?yún)?shù)為浮點矩陣輸入?yún)?shù)為浮點矩陣M，它的大小是影響算法時空開銷，它的大小是影響算法時空開銷