1、文庫專用1國家級精品課程國家級精品課程數據結構與算法數據結構與算法張銘、趙海燕、王騰蛟、宋國杰、高軍張銘、趙海燕、王騰蛟、宋國杰、高軍/北京大學信息科學與技術學院北京大學信息科學與技術學院“數據結構與算法數據結構與算法”教學小組教學小組本章主筆：趙海燕趙海燕 版權所有，轉載或翻印必究版權所有，轉載或翻印必究第第 1 1 章章 概論概論主要內容主要內容n問題求解問題求解n數據結構及抽象數據類型數據結構及抽象數據類型n算法的特性及分類算法的特性及分類n算法的效率度量算法的效率度量n數據結構的選擇和評價數據結構的選擇和評價問題求解問題求解n階段和步驟階段和步驟q獲取需求（問題），以保證解決的問題正是

2、需獲取需求（問題），以保證解決的問題正是需要的（要的（solve the right problem）；）；q分析問題，將其分解為粒度更小的部分；分析問題，將其分解為粒度更小的部分；q針對問題（子問題）給出相應的解決方案，易針對問題（子問題）給出相應的解決方案，易于理解和修改；于理解和修改；q估算解決方案的開銷，以事先判斷其可行性；估算解決方案的開銷，以事先判斷其可行性；n利用數學等工具的輔助得到正確且簡潔的解決方案利用數學等工具的輔助得到正確且簡潔的解決方案q維護和演化維護和演化問題求解問題求解問題求解問題求解數據結構數據結構設計方法設計方法描述語言描述語言算法理論算法理論數據模型數據模型問

3、題求解問題求解n通過通過n問題抽象問題抽象n數據抽象數據抽象n算法抽象算法抽象分析問題，應用數據結構和算法來設計分析問題，應用數據結構和算法來設計和實現高效的程序和實現高效的程序問題求解問題求解n實質實質q描述問題域中實際對象的描述問題域中實際對象的數據數據及其及其相互相互關系關系q映射到計算機的存儲器上映射到計算機的存儲器上q編寫算法模擬對象領域中的求解過程編寫算法模擬對象領域中的求解過程文庫專用7問題求解問題求解n計算機科學就是計算機科學就是“一種關于信息結構轉換一種關于信息結構轉換的科學的科學” (Wegnor)n計算機科學是計算機科學是“算法的學問算法的學問” (D.Knuth)n其實

4、數據結構與算法兩者互為存在其實數據結構與算法兩者互為存在 （數據（數據結構離不開施于其上的操作，同時算法也結構離不開施于其上的操作，同時算法也必然離不開作為其處理對象和結果的數據）必然離不開作為其處理對象和結果的數據）問題求解問題求解n 例子：例子：q從一組人中找出最高、最矮，及身高最適從一組人中找出最高、最矮，及身高最適中的人。中的人。q有有12個外表完全相同的球，只有一個不標個外表完全相同的球，只有一個不標準，或輕或重，要求用天平以最少的次數準，或輕或重，要求用天平以最少的次數找出該球，并判定其輕重找出該球，并判定其輕重。q計算機專業課程安排。計算機專業課程安排。n問題抽象問題抽象 、數據

5、抽象、算法抽象、數據抽象、算法抽象數據結構數據結構n數據的數據的q圖圖 樹樹 二叉樹二叉樹 線性表線性表n數據的數據的q順序方法、鏈接方法順序方法、鏈接方法q索引方法、散列方法索引方法、散列方法 n數據的數據的q增、刪、查、改增、刪、查、改q排序、檢索排序、檢索存存儲儲數據數據結構結構邏邏輯輯運運算算數據結構數據結構n一類按照一定邏輯關系組織起來的數據的一類按照一定邏輯關系組織起來的數據的表示及其相關操作表示及其相關操作q邏輯結構：表示數據元素之間的邏輯關系；q存儲結構：數據結構在計算機存儲器中的表示，也稱存儲表示；q運算（結構的行為特征）：作用于數據結構上的運算。常見的基本數據結構常見的基本

6、數據結構：線性表，字符串，堆棧與隊列，樹與二叉樹，字典，圖數據的邏輯結構數據的邏輯結構 n二元組 B = (K, R) K ： 結點（ 初等或組合類型）的有限集合 R : K上的有窮關系的集合（一組二元關系）qK中每個結點都代表一個數據或一組有明確結構中每個結點都代表一個數據或一組有明確結構的數據的數據q關系集關系集 R中的每個關系中的每個關系(relation) r（r R）都）都是是 KK上的二元關系，用以描述結點之間的邏上的二元關系，用以描述結點之間的邏輯關系輯關系 例如, r = | ki K, 1 i n 數據的邏輯結構：示例數據的邏輯結構：示例 n家族人員家族人員q把每個成員個體的

7、屬性描述作為數據結點，而全部人員把每個成員個體的屬性描述作為數據結點，而全部人員組成結點集組成結點集Kq家族的各類親屬關系就是一組關系家族的各類親屬關系就是一組關系R，其中如母系血緣關，其中如母系血緣關系系r、遠親關系、遠親關系r*、和非血緣的親情關系、和非血緣的親情關系r等等，每一個關等等，每一個關系要給出具體人員的關系元組系要給出具體人員的關系元組q例如：例如： 母子關系（戴愛蓮，張遠）母子關系（戴愛蓮，張遠） 兄弟關系（張遠，張立）兄弟關系（張遠，張立） 妯娌關系妯娌關系 （戴愛蓮，李美英）（戴愛蓮，李美英）結點類型：基本數據類型結點類型：基本數據類型n整數類型整數類型(integer)

8、：規定了所能表示的整數范圍，：規定了所能表示的整數范圍，計算機一般用計算機一般用1個字節個字節到到4個字節個字節來存儲整數來存儲整數n實數類型實數類型(real)：計算機的浮點數據類型所能表示：計算機的浮點數據類型所能表示的數值范圍和精度是的數值范圍和精度是有限有限的。的。 機器一般使用機器一般使用4到到8個字節個字節來存儲浮點數來存儲浮點數n布爾類型布爾類型(boolean)：取值為：取值為真真(true)和和假假(false)，在在C+語言中一般使用整數語言中一般使用整數0表示表示false，用非，用非0表表示示true 結點類型：基本數據類型結點類型：基本數據類型n字符類型字符類型(ch

9、ar)： 用單個字節（用單個字節（8bit，最高位，最高位bit為為0）表示）表示ASCII字符集中的字符字符集中的字符q漢字符號需要使用漢字符號需要使用2個字節（每個字節的最高位個字節（每個字節的最高位bit為為1）的編碼，單個字節對于漢字是沒有獨立含義的的編碼，單個字節對于漢字是沒有獨立含義的q在在C+中把雙字節表示中文符號的字節類型稱為中把雙字節表示中文符號的字節類型稱為w_char類型（類型（wide character）。）。q目前國際上已經采用了統一的擴展字符集合標準目前國際上已經采用了統一的擴展字符集合標準UNICODE，這一標準允許英、日、韓、阿拉伯語等，這一標準允許英、日、韓

10、、阿拉伯語等文字的混合文字處理文字的混合文字處理結點類型結點類型 ：基本數據類型：基本數據類型n指針類型指針類型(pointer)：用于表示機器內存地址，指：用于表示機器內存地址，指針表示指向某一內存單元的地址針表示指向某一內存單元的地址q由于機器的指令系統一般采用由于機器的指令系統一般采用32 bit或或64bit的地址長的地址長度，故指針類型也相應地用度，故指針類型也相應地用4或或8個字節個字節來表示一個指來表示一個指針針q指針值的存儲和指針值的運算方式，在形式上與正整指針值的存儲和指針值的運算方式，在形式上與正整數相似數相似q指針的運算一般僅限于兩個指針地址的比較，加減，指針的運算一般僅

11、限于兩個指針地址的比較，加減，或對一個指針增減一個整數量等或對一個指針增減一個整數量等結點類型結點類型 ：復合數據類型：復合數據類型n復合類型是由基本數據類型組合而成的數據結構復合類型是由基本數據類型組合而成的數據結構類型類型q例如：在程序語言中常用的數組類型，結構例如：在程序語言中常用的數組類型，結構（記錄）類型等皆屬復合數據類型（記錄）類型等皆屬復合數據類型n復合數據類型本身，又可以復合數據類型本身，又可以參與定義參與定義結構更為復結構更為復雜的結點類型雜的結點類型n結點的類型不限于基本數據類型，可以根據應用結點的類型不限于基本數據類型，可以根據應用的需要來靈活定義的需要來靈活定義 結構的

12、分類結構的分類 n數據的邏輯結構（數據的邏輯結構（K, R）的討論，一般把重點放）的討論，一般把重點放在在關系集關系集R上；上；n根據根據 R的性質的性質 刻劃數據結構的特點，并對數據結刻劃數據結構的特點，并對數據結構進行分類：構進行分類： q線性結構（線性結構（linear structure）q樹型結構（樹型結構（tree structure） q圖結構（圖結構（graph structure）線性結構線性結構n關系關系r 是一種線性關系，或稱為是一種線性關系，或稱為“前后關系前后關系”，有，有時也稱為時也稱為“大小關系大小關系”。關系。關系 r 是有向的，且滿足是有向的，且滿足全序性和單

13、索性等約束條件全序性和單索性等約束條件q全序性是指，線性結構的全部結點兩兩皆可以比全序性是指，線性結構的全部結點兩兩皆可以比較前后（關系較前后（關系 r）q單索性是指，每一個結點單索性是指，每一個結點 x 都存在唯一的一個都存在唯一的一個直接后繼結點直接后繼結點 y。如果其他結點。如果其他結點 z 在在 y 之前，則之前，則這個這個 z 也一定在也一定在 x 之前，不會在之前，不會在x，y之間之間 樹型結構樹型結構n簡稱樹結構，或層次結構。其關系簡稱樹結構，或層次結構。其關系 r 稱為層次關稱為層次關系，或稱系，或稱“父子關系父子關系”、“上下級關系上下級關系”等等n每一個結點可以有每一個結點

14、可以有多于一個的多于一個的“直接下級直接下級”，但，但是它只能有是它只能有唯一的唯一的“直接上級直接上級”。q樹型結構的最高層次的結點稱為樹型結構的最高層次的結點稱為根（根（root）結點）結點。只有。只有它它沒有父結點沒有父結點n樹型結構存在著很多變種，如二叉樹結構，堆結樹型結構存在著很多變種，如二叉樹結構，堆結構等，都有各自獨特的有效應用構等，都有各自獨特的有效應用圖結構圖結構n有時稱為結點互聯的有時稱為結點互聯的網絡結構網絡結構，因特網的網頁鏈接關系就，因特網的網頁鏈接關系就是一個非常復雜的圖結構是一個非常復雜的圖結構n對于圖結構的關系對于圖結構的關系 r 沒有加任何約束。這樣也就無法象

15、線沒有加任何約束。這樣也就無法象線性結構及樹結構那樣，利用關系性結構及樹結構那樣，利用關系 r 的約束來設計圖結構的的約束來設計圖結構的存儲結構存儲結構n在日常應用中圖結構往往只是層次結構的一種擴展在日常應用中圖結構往往只是層次結構的一種擴展允允許結點具有多個許結點具有多個“直接上級結點直接上級結點” ，關系，關系 r 表現為樹型結表現為樹型結構約束的放松構約束的放松 n從數學上看，樹型結構和圖結構的基本區別就是從數學上看，樹型結構和圖結構的基本區別就是“每個結每個結點是否點是否僅僅從屬一個直接上級僅僅從屬一個直接上級”。而線性結構和樹型結構。而線性結構和樹型結構的基本區別是的基本區別是“每個

16、結點是否每個結點是否僅僅有一個直接后繼僅僅有一個直接后繼”結點和結構結點和結構 n對于數據結構（對于數據結構（K, R），結點數據類型不限），結點數據類型不限于基本數據類型，可以根據應用需要來靈活于基本數據類型，可以根據應用需要來靈活設計結點的數據類型設計結點的數據類型文庫專用22結點和結構結點和結構 n數據結構的設計也可采用數據結構的設計也可采用自頂向下自頂向下的方法的方法逐層進行逐層進行q先明確先明確數據結點數據結點，及其，及其主要關系主要關系 r q分析關系分析關系 r 的同時，也要分析其數據結點的的同時，也要分析其數據結點的數數據類型據類型q如果數據結點的邏輯結構比較復雜，那么把它如果

17、數據結點的邏輯結構比較復雜，那么把它作為下一個層次，再分析下一層次的邏輯結構作為下一個層次，再分析下一層次的邏輯結構數據的存儲結構數據的存儲結構n數據的存儲（主存、外存）數據的存儲（主存、外存）n計算機主存的特性計算機主存的特性q其存儲空間提供了一種具有其存儲空間提供了一種具有非負整數非負整數地址編碼的、地址編碼的、相鄰單元相鄰單元的集合，其基本的存儲單元是的集合，其基本的存儲單元是字節字節q計算機的指令具有計算機的指令具有按地址隨機訪問按地址隨機訪問存儲空間內任存儲空間內任意單元的能力，訪問不同地址所需的訪問時間基意單元的能力，訪問不同地址所需的訪問時間基本相同本相同 數據的存儲結構數據的存

18、儲結構n數據的存儲結構是建立一種映射，對于數據邏輯結數據的存儲結構是建立一種映射，對于數據邏輯結構（構（K ，r），其中），其中rRq對結點集合對結點集合 K 建立一個從建立一個從K到存儲器到存儲器M的單元的映射：的單元的映射：KM，對于每一個結點，對于每一個結點 jK 都對應一個都對應一個唯一唯一的的連續存連續存儲儲區域區域c Mq每一個關系元組（每一個關系元組（j1 ，j2）r（其中（其中j1， j2K是結點），是結點），亦即亦即j1， j2的邏輯后繼關系應映射為存儲單元的地址之間的邏輯后繼關系應映射為存儲單元的地址之間的順序關系（或指針的地址指向關系）的順序關系（或指針的地址指向關系）n

19、四種基本存儲映射方法：四種基本存儲映射方法：順序、鏈接、索引、散列順序、鏈接、索引、散列順序方法順序方法 n用一塊連續的存儲區域存儲數據稱為用一塊連續的存儲區域存儲數據稱為順序存儲順序存儲n順序存儲把一組結點存儲在按地址相鄰的順序存順序存儲把一組結點存儲在按地址相鄰的順序存儲單元里，結點間的邏輯后繼關系用儲單元里，結點間的邏輯后繼關系用存儲單元的存儲單元的自然順序關系自然順序關系來表達來表達 n順序存儲法為使用整數編碼來訪問數據結點提供順序存儲法為使用整數編碼來訪問數據結點提供了便利了便利 02136547S順序方法順序方法 n順序存儲結構稱為順序存儲結構稱為緊湊存儲結構緊湊存儲結構，其緊湊性

20、是指，其緊湊性是指它的存儲空間除了存儲有用數據外，沒有用于存它的存儲空間除了存儲有用數據外，沒有用于存儲其他附加的信息儲其他附加的信息n緊湊性可以用緊湊性可以用“存儲密度存儲密度”來度量：它是一個存來度量：它是一個存儲結構所存儲的儲結構所存儲的“有用數據有用數據”和該結構（包括附和該結構（包括附加信息）整個存儲空間大小之比加信息）整個存儲空間大小之比n有時為了有時為了“用空間換取時間用空間換取時間”，在存儲結構中存，在存儲結構中存儲一些附加信息還是很必要的儲一些附加信息還是很必要的q譬如，用于提高算法的執行速度，或者讓算法實現更為譬如，用于提高算法的執行速度，或者讓算法實現更為簡便等簡便等 鏈

21、接方法鏈接方法 n利用指針，在結點的存儲結構中附加指針字段稱利用指針，在結點的存儲結構中附加指針字段稱為為鏈接法鏈接法。兩個結點的邏輯后繼關系。兩個結點的邏輯后繼關系用指針用指針來表來表達達n任意的邏輯關系任意的邏輯關系 r，均可使用這種指針地址來表達。，均可使用這種指針地址來表達。一般的做法是將數據結點分為兩部分一般的做法是將數據結點分為兩部分:q一部分存放結點本身的數據，稱為一部分存放結點本身的數據，稱為數據字段數據字段q一部分存放指針，稱一部分存放指針，稱指針字段指針字段，鏈接到某個后繼結點，鏈接到某個后繼結點，指向它的存儲單元的開始地址。多個相關結點的依次鏈指向它的存儲單元的開始地址。

22、多個相關結點的依次鏈接就會形成接就會形成鏈索鏈索鏈接方法鏈接方法 n對于經常增刪結點的復雜數據結構，順序存儲往往對于經常增刪結點的復雜數據結構，順序存儲往往會難以應付，而鏈接方法結合動態存儲為這些復雜會難以應付，而鏈接方法結合動態存儲為這些復雜問題提供了解決方法問題提供了解決方法n缺點：缺點：q為了訪問結點集為了訪問結點集 K 中某個結點，必須用該結點的存儲指針中某個結點，必須用該結點的存儲指針q當不知道結點指針時，為了在結點集當不知道結點指針時，為了在結點集 K中尋找某個符合條中尋找某個符合條件的結點，就要沿著鏈接結點的鏈索，按結點逐個比較搜件的結點，就要沿著鏈接結點的鏈索，按結點逐個比較搜

23、索，得花費相當可觀的時間索，得花費相當可觀的時間索引方法索引方法 n順序存儲法的一種推廣，也使用順序存儲法的一種推廣，也使用整數編碼來整數編碼來訪問數據結點位置訪問數據結點位置n建造一個由整數域建造一個由整數域 Z 映射到存儲地址域映射到存儲地址域D 的的函數函數Y：ZD，把，把結點的整數索引值結點的整數索引值 zZ 映射到映射到結點的存儲地址結點的存儲地址 dD 。Y稱為稱為索引函數索引函數索引方法示意索引方法示意 一般而言，索引函數并不象數組那樣，是簡單的線性一般而言，索引函數并不象數組那樣，是簡單的線性函數。當數據結點長度不等的情況下，索引函數就無函數。當數據結點長度不等的情況下，索引函

24、數就無法用線性表達式給出法用線性表達式給出索引方法索引方法n為了構造任意的索引函數，可為索引函數提供附為了構造任意的索引函數，可為索引函數提供附加的存儲空間，稱為加的存儲空間，稱為索引表索引表Sn索引表中每一元素是指向數據結點的指針。因為索引表中每一元素是指向數據結點的指針。因為索引表索引表 S 由等長元素（指針）組成，故可進行線由等長元素（指針）組成，故可進行線性的索引計算：性的索引計算： 始址始址(元素元素Si) 始址始址(元素元素S0) i （指針尺寸）（指針尺寸）通過上述公式，由索引號通過上述公式，由索引號 i 可以計算出索引表中的單元可以計算出索引表中的單元Si的始址，再通過讀出的始

25、址，再通過讀出Si元素的內容（指針），訪問真元素的內容（指針），訪問真正需要訪問的數據結點正需要訪問的數據結點索引方法索引方法n索引方法付出了存儲的開銷，其數據結點要附加索引方法付出了存儲的開銷，其數據結點要附加用于指針的存儲空間用于指針的存儲空間n索引方法在程序設計中是一種經常使用的方法，索引方法在程序設計中是一種經常使用的方法，主要原因是對于非順序的存儲結構來說，使用索主要原因是對于非順序的存儲結構來說，使用索引表是快速地由整數索引值找到其對應數據結點引表是快速地由整數索引值找到其對應數據結點的的唯一唯一方法方法散列方法散列方法 n索引方法的一種延伸和擴展索引方法的一種延伸和擴展n利用一種

26、稱為利用一種稱為散列函數散列函數(hash functions)的機制來的機制來進行索引值的計算，然后通過索引表求出結點的進行索引值的計算，然后通過索引表求出結點的指針地址指針地址n散列函數是將字符串散列函數是將字符串 s（ 或關鍵碼）映射到非負或關鍵碼）映射到非負整數整數 z 的一類函數的一類函數 h: S Z ， 對任意的對任意的 s S，散列函數，散列函數 h(s)=z，z Z散列方法散列方法 n散列函數散列函數h(s)除了取非負整數值外，關鍵的除了取非負整數值外，關鍵的問題包括：問題包括：q如何恰當地選擇散列函數如何恰當地選擇散列函數q如何建造散列表如何建造散列表q如何在構建散列表時解

27、決如何在構建散列表時解決“碰撞碰撞”問題問題文庫專用35數據的運算數據的運算n作用于數據上的運算作用于數據上的運算q查、改、增、刪，等等查、改、增、刪，等等n不同的數據不同的數據文庫專用36數據結構數據結構n抽象數據類型抽象數據類型存存儲儲數據數據結構結構邏邏輯輯運運算算文庫專用37抽象抽象n計算機科學本身就是抽象的計算機科學本身就是抽象的科學科學 為問題建立適當的模為問題建立適當的模型并設計相應的技術解決它型并設計相應的技術解決它q相對于物理學相對于物理學n計算機本身的一些抽象計算機本身的一些抽象silicongatesregisters & processorsmachine la

28、nguagedevice drivers, : : :operating systemHigh level languageusern抽象的本質？抽象的本質？n簡化簡化n忽略非本質的部分忽略非本質的部分抽象數據類型抽象數據類型n模塊化的思想的發展，為模塊的劃分提供了模塊化的思想的發展，為模塊的劃分提供了理論依據理論依據 ，簡稱，簡稱ADT (Abstract Data Type)n目的目的q隱藏運隱藏運算實現的細節和內部數據結構算實現的細節和內部數據結構q提高復用的力度和粒度提高復用的力度和粒度ADTuser1user2usern.實現實現1 1實現實現2 2實現實現3 3抽象數據類型抽象數據

29、類型抽象數據類型抽象數據類型n用數學方法定義用數學方法定義對象對象集合和集合和運算運算集合，僅通過運算集合，僅通過運算的性質刻畫數據對象，而獨立于計算機中可能的表的性質刻畫數據對象，而獨立于計算機中可能的表示方法示方法q可看作是定義了一組操作的一個抽象模型可看作是定義了一組操作的一個抽象模型n例如，集合與集合的并、交、差運算就可定義為一個的抽例如，集合與集合的并、交、差運算就可定義為一個的抽象數據類型象數據類型q一個抽象數據類型要包括哪些操作，這一點由設計一個抽象數據類型要包括哪些操作，這一點由設計者根據需要確定者根據需要確定n例如，對于集合，如果需要，也可以把判別一個集合是否例如，對于集合，

30、如果需要，也可以把判別一個集合是否為空集或兩個集合是否相等作為集合上的操作為空集或兩個集合是否相等作為集合上的操作抽象數據類型抽象數據類型n由三元組由三元組 表示表示q數據對象數據對象Dq數據關系數據關系Sq數據操作數據操作P文庫專用42抽象數據類型抽象數據類型template / 模板參數為類型模板參數為類型Typeclass className private: / 數據結構的的取值類型和取值空間數據結構的的取值類型和取值空間Type dataList; / 定義數據及其存儲方式定義數據及其存儲方式. public: / 運算集運算集methodName(); / 定義對數據的操作定義對數

31、據的操作; 文庫專用43數據結構數據結構文庫專用44算法算法算法算法n對特定問題求解過程的描述，是指令的有限對特定問題求解過程的描述，是指令的有限序列，也即，為解決某一特定問題而采取的序列，也即，為解決某一特定問題而采取的具體有限的操作步驟。具體有限的操作步驟。n程序是算法的一種實現，計算機按照程序逐程序是算法的一種實現，計算機按照程序逐步執行算法，實現對問題的求解。步執行算法，實現對問題的求解。文庫專用46算法算法n用計算裝置能夠理解的語言描述的解題過用計算裝置能夠理解的語言描述的解題過程，具有如下性質：程，具有如下性質：q將它作用于所求解的問題的給定輸入集上，或將它作用于所求解的問題的給定

32、輸入集上，或作用于問題自身的描述上，將產生唯一確定的作用于問題自身的描述上，將產生唯一確定的動作序列，此序列是有限的；動作序列，此序列是有限的；q此序列或終止于給出問題的解，或終止于指出此序列或終止于給出問題的解，或終止于指出問題對此輸入無解問題對此輸入無解 有窮性；確定性；有窮性；確定性； 可行性；可行性； 輸入；輸入； 輸出輸出算法的特性算法的特性n 通用性通用性o對于符合輸入類型的任意輸入數據，都能根據算法進行對于符合輸入類型的任意輸入數據，都能根據算法進行問題求解，并保證計算結果的正確性問題求解，并保證計算結果的正確性n有效性有效性q組成算法的每一條指令都必須是能夠被（人或機器）確組成

33、算法的每一條指令都必須是能夠被（人或機器）確切執行的，且指令的類型應該明確規定，其結果應具有切執行的，且指令的類型應該明確規定，其結果應具有確定的數據類型，是能夠預期的確定的數據類型，是能夠預期的n確定性確定性q保證每一步之后都有關于下一步動作的指令，不能缺乏保證每一步之后都有關于下一步動作的指令，不能缺乏下一步指令（被鎖住）或僅僅含有模糊不清的指令下一步指令（被鎖住）或僅僅含有模糊不清的指令n有窮性有窮性q算法的執行必須在有限步內結束。換句話說，算法不能算法的執行必須在有限步內結束。換句話說，算法不能含有死循環含有死循環 算法分類算法分類n算法設計與算法分析是計算機科學的核心問題算法設計與算

34、法分析是計算機科學的核心問題n常用的設計方法常用的設計方法q窮舉法窮舉法(百錢買百雞百錢買百雞)q貪心法貪心法(Huffman樹、樹、Prim等等)q遞歸法遞歸法, 分治法分治法(二分檢索、快速排序等二分檢索、快速排序等)q回溯法回溯法(樹、圖等的深度優先搜索）樹、圖等的深度優先搜索）q動態規劃法動態規劃法(最佳二叉排序樹最佳二叉排序樹)q-裁剪和分枝界限法裁剪和分枝界限法q并行算法并行算法49計算復雜性和算法的效率計算復雜性和算法的效率n根據計算理論，存在著一類問題雖然能夠被準確定根據計算理論，存在著一類問題雖然能夠被準確定義，但卻不存在能夠解決該問題的算法。稱為義，但卻不存在能夠解決該問題

35、的算法。稱為不可不可解問題解問題n計算復雜性理論指出，理論上存在一大類難解問題計算復雜性理論指出，理論上存在一大類難解問題，它們雖然存在著求解算法，但在算法的計算時間，它們雖然存在著求解算法，但在算法的計算時間上，都是組合爆炸型的求解算法上，都是組合爆炸型的求解算法q隨著問題的規模隨著問題的規模 n 的增大，算法的時間開銷不能約束在的增大，算法的時間開銷不能約束在 n 的的 k 階多項式數量范圍內。（其中階多項式數量范圍內。（其中 k是任意不依賴于是任意不依賴于 n 的的常數）常數） q比較常見的難解問題有：圖論中的求最優巡游路徑問題，比較常見的難解問題有：圖論中的求最優巡游路徑問題，判定命題

36、邏輯公式是否為恒真等判定命題邏輯公式是否為恒真等算法的執行效率及其度量算法的執行效率及其度量n解決同一個問題存在多種算法，如何評估各算法的解決同一個問題存在多種算法，如何評估各算法的好壞？或據此設計出更好的算法？好壞？或據此設計出更好的算法？q運行該算法所需要的計算機資源的多寡，所需越大復雜性運行該算法所需要的計算機資源的多寡，所需越大復雜性越高越高q最重要的資源：時間（處理器）和空間（存儲器）最重要的資源：時間（處理器）和空間（存儲器）n評價一個算法優劣的重要依據是看執行該算法的程評價一個算法優劣的重要依據是看執行該算法的程序需要占用多少機器資源：序需要占用多少機器資源：q程序所用算法運行時

37、所要花費的時間代價程序所用算法運行時所要花費的時間代價q程序中使用的數據結構占有的空間代價程序中使用的數據結構占有的空間代價文庫專用51算法的執行效率及其度量算法的執行效率及其度量n需要明確：需要明確：n如何表達一個算法的復雜性如何表達一個算法的復雜性n怎樣計算一個算法的復雜性怎樣計算一個算法的復雜性算法時間復雜性算法時間復雜性n不能用諸如微秒、納秒這樣的真實時間單位不能用諸如微秒、納秒這樣的真實時間單位q一個運行在一個運行在Cray機上的算法若放在機上的算法若放在PC機會慢很多機會慢很多q一個運行在一個運行在Cray機上的效率極差的算法也許比一個機上的效率極差的算法也許比一個運行在運行在PC

38、上的效率很高的算法花費更少的時間上的效率很高的算法花費更少的時間q同樣的算法運行在同樣的機器上也會因使用不同的程同樣的算法運行在同樣的機器上也會因使用不同的程序語言而存在差異序語言而存在差異nC vs LISPq兩個不同的算法也許在輸入規模為兩個不同的算法也許在輸入規模為100時表現不相上時表現不相上下，而在輸入規模擴大下，而在輸入規模擴大10倍后卻表現迥異倍后卻表現迥異算法復雜性分析算法復雜性分析n算法分析感興趣的不是具體的資源占用量，算法分析感興趣的不是具體的資源占用量，而是與具體的平臺無關、具體的輸入實例無而是與具體的平臺無關、具體的輸入實例無關，且隨輸入規模增長的值是可預測的關，且隨輸

39、入規模增長的值是可預測的q與問題的規模之間的關系，用一定與問題的規模之間的關系，用一定“規模規模(size)”的數據作為輸入時程序運行所需的的數據作為輸入時程序運行所需的“基本操作基本操作(basic operation) ” 數來描述時間效率。數來描述時間效率。q完成一個完成一個“基本操作基本操作”所需的時間應該與具體所需的時間應該與具體的被操作的數無關的被操作的數無關算法的漸進分析算法的漸進分析nasymptotic analysis，簡稱算法分析q由于算法的復雜性與其所求解的問題規模直接由于算法的復雜性與其所求解的問題規模直接有關，因此通常將有關，因此通常將問題規模問題規模 n 作為一個

40、參照量作為一個參照量，求算法的時空開銷和，求算法的時空開銷和 n 的關系的關系q一般這種函數關系都相當復雜，計算時只考慮一般這種函數關系都相當復雜，計算時只考慮可以顯著影響函數量級的部分，即結果為原函可以顯著影響函數量級的部分，即結果為原函數的一個近似值數的一個近似值q對資源開銷的一種不精確估計，提供對于算法對資源開銷的一種不精確估計，提供對于算法資源開銷進行評估的簡單化模型資源開銷進行評估的簡單化模型算法的漸進分析算法的漸進分析n算法的漸進分析就是要估計，當數據規模算法的漸進分析就是要估計，當數據規模 n逐逐步增大時，資源開銷步增大時，資源開銷f(n)的增長趨勢的增長趨勢n得到如此精確的一個

41、界相對比較費時費力，且得到如此精確的一個界相對比較費時費力，且沒有必要沒有必要n從數量級大小的比較來考慮，當從數量級大小的比較來考慮，當n增大到一定值增大到一定值以后，資源開銷的計算公式中影響最大的就是以后，資源開銷的計算公式中影響最大的就是n的的冪次最高的項，其他的常數項和低冪次項都是可冪次最高的項，其他的常數項和低冪次項都是可以忽略的以忽略的 1000nlog100nn)n(f102算法漸進分析：算法漸進分析：大表式法大表式法n假設假設f 和和g為從自然數到非負實數集的兩個函數為從自然數到非負實數集的兩個函數定義定義1：如果存在正數：如果存在正數c和和N，使得對任意的，使得對任意的n N，

42、都有，都有f(n) cg(n)，則稱則稱f(n)在集合在集合O(g(n)中，或簡稱中，或簡稱f(n)是是O(g(n)的的 q說明了函數說明了函數 f 和和 g 關系：函數關系：函數g(n) 是函數是函數 f(n) 取值的上取值的上限（限（upper bound），或說函數），或說函數f的增長最終至多趨同于的增長最終至多趨同于g的增長的增長q大大O表示法提供了一種表達函數增長率上限的方法表示法提供了一種表達函數增長率上限的方法 q一個函數增長率的上限可能不止一個。大一個函數增長率的上限可能不止一個。大O表示法給出了表示法給出了所有上限中最所有上限中最“緊緊”（也即最小）的那個上限（也即最小）的那

43、個上限57大表式法的性質大表式法的性質n若符號若符號a是不依賴于是不依賴于n的任意常數的任意常數 q如果函數如果函數 f(n) 是是O(g(n)的，的，g(n)是是O(h(n)，那么，那么f(n)是是O(h(n)的的q如果函數如果函數f(n)是是O(h(n)的，的，g(n)是是O(h(n)，那么，那么f(n) + g(n) 是是O(h(n)的的q函數函數ank是是O(nk)的的q對任何正數對任何正數 j 而言，函數而言，函數nk 是是O(nk+j)的的q若若f(n) = cg(n)，則，則f(n) 是是O(g(n)的的q對于任何正數對于任何正數a和和b，且，且b 1，函數，函數logan 是是

44、O(logbn)的。的。即，任何對數函數無論底數為何，都具有相同的增長率即，任何對數函數無論底數為何，都具有相同的增長率1.對任何正數對任何正數 a 1，都有，都有logan 是是O(lg n)的，其中的，其中lg n = log2n大大O表示法的運算規則表示法的運算規則n單位時間單位時間q簡單布爾或算術運算簡單布爾或算術運算q簡單簡單I/Oq函數返回函數返回n加法規則加法規則: f1(n)+f2(n)=(max(f1(n), f2(n)q順序結構，順序結構，if 結構，結構，switch結構結構n乘法規則乘法規則: f1 (n)f2 (n) =(f1(n)f2 (n)qfor, while,

45、 do-while結構結構算法漸進分析：算法漸進分析： 表式法表式法n定義定義2 ：如果存在正數：如果存在正數c和和N，使得對所有的，使得對所有的n N，都有都有f(n) cg(n)，則稱則稱f(n)在集合在集合 (g(n) 中，或簡稱中，或簡稱f(n) 是是 (g(n)的的 q說明了說明了cg(n)是函數是函數f(n)取值的下限（取值的下限（lower bound），或說函數），或說函數f的增長最終至少是趨同于函的增長最終至少是趨同于函數數g的增長的增長q正如大正如大O表示法，表示法， 表示法也是在函數增值率的表示法也是在函數增值率的所有下限中那個最所有下限中那個最“緊緊”（即最大）的下限（

46、即最大）的下限算法漸進分析：算法漸進分析： 表式法表式法n當上、下限相同時則可用當上、下限相同時則可用 表示法。定義如表示法。定義如下：下：如果一個函數既在集合如果一個函數既在集合O (g(n)中又在集合中又在集合 (g(n)中，則稱其為中，則稱其為 (g(n)。 也即，也即，存在正常數存在正常數c1, c2，以及正整數，以及正整數n0，使得對于任意，使得對于任意的正整數的正整數n n0 ，有下列兩不等式同時成立，有下列兩不等式同時成立c1 g(n) f(n) c2 g(n)漸進分析示例漸進分析示例n對數組中的各個元素求和的代碼：對數組中的各個元素求和的代碼：for (i = sum = 0;

47、 in; i+） sum += ai;其中主要的操作為賦值運算，故該算法的時其中主要的操作為賦值運算，故該算法的時間代價主要體現在賦值操作的數目上間代價主要體現在賦值操作的數目上p在循環開始之前有兩次賦值，分別對在循環開始之前有兩次賦值，分別對 i 和對和對sum進行；進行；p循環進行了循環進行了n 次，每次循環中執行兩次賦值，分別對次，每次循環中執行兩次賦值，分別對 sum和對和對 i 進行更新操作；進行更新操作；p總共有總共有2 + 2n 次賦值操作次賦值操作其漸進復雜度為其漸進復雜度為O(n) 漸進分析示例漸進分析示例n依次求出給定數組的所有子數組中各元素之和：依次求出給定數組的所有子數

48、組中各元素之和：for (i = 0; i n; i+) for (j = 1, sum = a0; j = i; j+) sum += aj;)n(O)n(O) n(O) 1n( n3n1) 1n.21 ( 23n12i3n1221n1io循環開始前，有一次對i的賦值操作。o外層循環共進行n次，每個循環中包含一個內層循環，以及對i, j, sum分別進行賦值操作；n每個內層循環執行每個內層循環執行2個賦值操作，分別更新個賦值操作，分別更新sum 和和 j；共執行；共執行i次次（i=1,2, ,n-1）。）。o整個程序總共執行的賦值操作為：漸進分析示例漸進分析示例n若只對每個子數組的前若只對每

49、個子數組的前5個元素求和，則相應的代個元素求和，則相應的代碼可采用下面的方式：碼可采用下面的方式：for ( i=4; in; i+) for (j = i-3, sum = ai-4; j = i; j+) sum += aj; o外層循環進行外層循環進行n-4次次o對每個對每個 i 而言，內層循環只執行而言，內層循環只執行4次，每次的操次，每次的操作次數和作次數和 i 的大小無關：的大小無關：8次賦值操作次賦值操作o整個代碼總共進行整個代碼總共進行O(1)+O(n) +8(n-4)=O(n)次次 o看似雙重循環，其實線性時間看似雙重循環，其實線性時間增長率函數曲線增長率函數曲線各時間量級在

50、現實中對應的物體速度各時間量級在現實中對應的物體速度米米/ /秒秒英制度量衡英制度量衡現實世界的例子現實世界的例子1010-11-111010-10-101010-9-91010-8-81010-7-71010-6-61010-5-51010-4-41010-3-31010-2-21010-1-11 110101 110102 210103 310104 410105 510106 610107 710108 81.2 1.2 英寸英寸/ /世紀世紀1.21.2英寸英寸/ /十年十年1.2 1.2 英寸英寸/ /年年1 1 英尺英尺/ /年年1 1英尺英尺/ /月月 3.43.4英寸英寸/ /

51、天天1.41.4英寸英寸/ /時時1.21.2英尺英尺/ /時時2 2英寸英寸/ /分分2 2英尺英尺/ /分分2020英尺英尺/ /分分2.22.2英里英里/ /時時 2222英里英里/ /時時 220220英里英里/ /時時3737英里英里/ /分分370370英里英里/ /分分37003700英里英里/ /分分620620英里英里/ /秒秒62006200英里英里/ /秒秒62,00062,000英里英里/ /秒秒鐘乳石的生長速度鐘乳石的生長速度大陸板塊的漂移速度大陸板塊的漂移速度指甲的生長速度指甲的生長速度頭發的生長速度頭發的生長速度雜草的生長速度雜草的生長速度冰河的流動速度冰河的流動

52、速度表的分針轉動速度表的分針轉動速度胃腸的蠕動速度胃腸的蠕動速度蝸牛的速度蝸牛的速度螞蟻的速度螞蟻的速度巨龜的速度巨龜的速度人類的散步速度人類的散步速度人類疾跑速度人類疾跑速度螺旋槳飛機的速度螺旋槳飛機的速度噴氣式飛機的速度噴氣式飛機的速度宇宙飛船的速度宇宙飛船的速度流星撞擊地球的速度流星撞擊地球的速度地球自轉速度地球自轉速度衛星從洛杉磯到紐約的速度衛星從洛杉磯到紐約的速度光速的三分之一光速的三分之一運行時間估算運行時間估算n例：假設例：假設CPU每秒處理每秒處理10 6 個指令，對于輸入規個指令，對于輸入規模為模為108的問題，時間代價的問題，時間代價T(n) = 2n2的算法要運的算法要運

53、行多長時間？行多長時間？q操作次數為操作次數為T(n) = T(108) = 2(108)2 = 21016q運行時間為運行時間為21016/106 = 21010秒秒q一天有一天有86,400秒，故需要秒，故需要231,480 天，即天，即634年年運行時間估算運行時間估算n例：假設例：假設CPU每秒處理每秒處理106個指令，對于輸入個指令，對于輸入規模為規模為108的問題，時間代價為的問題，時間代價為nlog n 的算的算法要運行多長時間？法要運行多長時間？q操作次數為操作次數為 T(n) = T(108) = 108 log 108 = 2.66109q運行時間為運行時間為2.66109

54、/106 = 2.66103秒，即秒，即44.33分鐘分鐘規定時間內處理問題的規模規定時間內處理問題的規模n設設CPU每秒處理每秒處理106個指令，則每小時能夠個指令，則每小時能夠解決的最大問題規模解決的最大問題規模 T(n) / 106 3600n對對T(n) = 2n2，q即即2n2 3600 106qn 42 , 426nT(n) = nlog nq即即nlogn 3600 106q n 133 , 000 , 000加快硬件速度？加快硬件速度？T(n)處理輸入規模為處理輸入規模為n=108 1小時內解決的問題規模小時內解決的問題規模106指令指令/秒秒108指令指令/秒秒106指令指令

55、/秒秒108指令指令/秒秒n log n 44.33 秒秒0.4433秒秒1.33億億100億億2n2634年年6.34年年42,426424,264 CPU每秒處理每秒處理個指令（快個指令（快100倍）倍）處理時間降為原來的處理時間降為原來的1/100- 解決問題的規模解決問題的規模對對規模增加規模增加10倍倍規模增加規模增加75倍倍最差、最佳、平均情況最差、最佳、平均情況n在進行算法增長率估計時，有些算法，即使問題規在進行算法增長率估計時，有些算法，即使問題規模相同，若輸入數據不同，其時間復雜度也不同模相同，若輸入數據不同，其時間復雜度也不同q由于算法實際執行的操作往往依賴于分支條件的走向

56、由于算法實際執行的操作往往依賴于分支條件的走向，而輸入數據的取值又影響這些分支走向，因此很多，而輸入數據的取值又影響這些分支走向，因此很多算法都無法得出獨立于輸入數據的漸進估計算法都無法得出獨立于輸入數據的漸進估計n針對這一情況，提出了最差情況估計、平均情況估針對這一情況，提出了最差情況估計、平均情況估計、最佳情況估計等三種方法計、最佳情況估計等三種方法 示例示例n求一個數組的所有有序子數組中最長的一個：求一個數組的所有有序子數組中最長的一個：for (i = 0, length=1; in-1; i+) for (j1 = j2 = k = i; k n-1 & ak ak+1; k

57、+, j2+);if (length j2 - j1 - 1)length = j2 - j1 + 1;譬如，在數組譬如，在數組1, 8, 1, 2, 5, 0, 11, 9中，這個最長的中，這個最長的有序子數組為有序子數組為1，2，5，長度為，長度為3。時間代價和數組時間代價和數組 a 中元素的實際取值狀態很相關中元素的實際取值狀態很相關示例：最佳示例：最佳n數組數組a的所有元素是以降序方式輸入的所有元素是以降序方式輸入q外層循環執行外層循環執行n-1次，次，q每次內層循環只執行每次內層循環只執行1次次q整個的時間開銷為整個的時間開銷為O(n)min complexity(size(y) | y Input示例：最差示例：最差n數組數組 a 的所有元素是以升序方式輸入的所有元素是以升序方式輸入q外層循環執行