數(shù)據(jù)結(jié)構(gòu)概念-樹圖的劃分ppt課件

1、第一章 數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)電子教案數(shù)據(jù)結(jié)構(gòu)電子教案第一章第一章 數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)概念 學學 號號 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚劉激揚 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 島島 1979.07 3 98165 盧聲凱盧聲凱 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北 京京 1981.01

2、8 98310 蔡曉莉蔡曉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12 課程編號課程編號 課課 程程 名名 學時學時 024002 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計算機原理計算機原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機技術(shù)微機技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 48學生學生( (學號學號, ,姓名姓名, ,性別性別, ,籍貫籍貫) )課程課程( (課程號課程號, ,課程名課程名, ,學分學分) )選課選課( (

3、學號學號, ,課程號課程號, ,成果成果) )UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp數(shù)據(jù)數(shù)據(jù)datadata）n數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。機程序識別和處理的符號的集合。n數(shù)據(jù)的分類：數(shù)據(jù)的分類：n 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)n 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)姓名姓名 所在院系所在院系 性別性別 出生日期出生日期 年年

4、 月月職務(wù)職務(wù) 業(yè)績業(yè)績數(shù)據(jù)元素數(shù)據(jù)元素 (data element)(data element)n數(shù)據(jù)的基本單位。在計算機程序中常作為數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。一個整體進行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data Item)(Data Item)組成。數(shù)據(jù)項是具有獨立含義組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。的最小標識單位。n數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)定義定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元

5、素之間的關(guān)系組成。記為：數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = D, R 其中，其中，D 是某一數(shù)據(jù)元素的集合，是某一數(shù)據(jù)元素的集合，R 是該是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。例：例：N N 個網(wǎng)點之間的連通關(guān)系個網(wǎng)點之間的連通關(guān)系 156152436243數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n包括三個方面：包括三個方面：n數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；構(gòu)；n數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示；即數(shù)據(jù)的存

6、儲表示；n數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)；與數(shù)據(jù)的存儲無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；象出來的數(shù)據(jù)模型；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；內(nèi)容無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)。置無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)n 線性表線性表n非線性結(jié)構(gòu)非線

7、性結(jié)構(gòu)n 樹樹n 圖或網(wǎng)絡(luò)）圖或網(wǎng)絡(luò)）線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹樹 二叉樹二叉樹 二叉搜索樹二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311堆結(jié)構(gòu)堆結(jié)構(gòu)123548711102916410121151236987圖結(jié)構(gòu)圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)n數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；的實現(xiàn)；n數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。n 順序存儲表示順序存儲表示n

8、鏈接存儲表示鏈接存儲表示n 索引存儲表示索引存儲表示n 散列存儲表示散列存儲表示主要用于內(nèi)存的主要用于內(nèi)存的存儲表示存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍頽數(shù)據(jù)類型數(shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合定義：一組性質(zhì)相同的值的集合, 以及定以及定義于這個值集合上的一組操作的總稱義于這個值集合上的一組操作的總稱.nC語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型n char int float double voidn 字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無無值值 n構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)構(gòu)造數(shù)

9、據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。類型組成。n構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。n基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。n數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。者的角度來使用的。n數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。類型的變量，才能參加運算。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)n抽象數(shù)據(jù)類型

10、是由用戶定義，用以表示應抽象數(shù)據(jù)類型是由用戶定義，用以表示應用問題的數(shù)據(jù)模型。用問題的數(shù)據(jù)模型。n特點是：信息隱蔽和數(shù)據(jù)封裝，使用與實特點是：信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離?，F(xiàn)相分離。n抽象數(shù)據(jù)類型可用抽象數(shù)據(jù)類型可用D, S, P三元組表示，三元組表示，其中，其中，D 是數(shù)據(jù)元素的集合簡稱數(shù)據(jù)對是數(shù)據(jù)元素的集合簡稱數(shù)據(jù)對象），象），S 是是 D上的關(guān)系集合，上的關(guān)系集合，P 是對是對 D 的的基本操作集合?；静僮骷?。 n抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修正修正 符符 號號 表表抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述n其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描其中數(shù)據(jù)對

11、象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名參數(shù)表）基本操作名參數(shù)表）前置條件：先決條件描述前置條件：先決條件描述后置條件：操作結(jié)果描述后置條件：操作結(jié)果描述n基本操作有兩種參數(shù)：賦值參數(shù)只為操作提基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以供輸入值；引用參數(shù)以&打頭，除可提供輸打頭，除可提供輸入值外，還將返回操作結(jié)

12、果。入值外，還將返回操作結(jié)果。n “前置條件前置條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應滿足的先決條件，若不滿足，則構(gòu)和參數(shù)應滿足的先決條件，若不滿足，則操作失敗，并返回相應出錯信息。操作失敗，并返回相應出錯信息。n “后置條件后置條件說明了操作正常完成之后，說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應返回的結(jié)果。若前數(shù)據(jù)結(jié)構(gòu)的變化狀況和應返回的結(jié)果。若前置條件為空，則省略之。置條件為空，則省略之。自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合一個整數(shù)的有序子集合,它開始于它開始于0, 結(jié)束

13、于機器能表示的最大整數(shù)結(jié)束于機器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的對于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是等都是可用的服務(wù)?？捎玫姆?wù)。 Zero( ) : NaturalNumber /前置條件：無前置條件：無 /后置條件：返回自然數(shù)后置條件：返回自然數(shù)0 面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍頽面向?qū)ο竺嫦驅(qū)ο?= = 對象類承繼通訊對象類承繼通訊n對象對象n在應用問題中出現(xiàn)的各種實體、事件、規(guī)在應用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等。格說明等。n由一組屬性值和在這組值上的一組服務(wù)由一組屬性

14、值和在這組值上的一組服務(wù)或稱操作構(gòu)成?；蚍Q操作構(gòu)成。n與與C C中構(gòu)造數(shù)據(jù)類型不同在于：中構(gòu)造數(shù)據(jù)類型不同在于：C C中的構(gòu)造中的構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與操作分數(shù)據(jù)類型的變量僅涉及屬性值，與操作分離，而離，而C+C+中的對象則不然。中的對象則不然。n類類 (class)，實例，實例 (instance)n具有相同屬性和服務(wù)的對象歸于同一類，具有相同屬性和服務(wù)的對象歸于同一類，形成類。形成類。n類中的對象為該類的實例。類中的對象為該類的實例。n同一類的實例同一類的實例n共享類的屬性和類的操作；共享類的屬性和類的操作；n通過繼承共享其父類的公共的和保護性的通過繼承共享其父類的公共的和保護

15、性的屬性和操作；屬性和操作；n同一類的不同實例有不同的屬性值。同一類的不同實例有不同的屬性值。四邊形類及其對象四邊形類及其對象屬性aPoint1 aPoint2aPoint3 aPoint4效力效力Draw( )move(x, y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)

16、效力效力效力效力quadrilateraln承繼承繼n派生類子類）：四邊形，三角形，派生類子類）：四邊形，三角形，n基類父類）：多邊形基類父類）：多邊形派生類派生類繼承的特性繼承的特性+特有的特性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形n通訊通訊n消息傳遞消息傳遞nC+中消息傳遞的方式：中消息傳遞的方式：n定義：定義：Point p; void move(int x, inty);n運用：運用：p.move(x, y);nC中則不同，需使用函數(shù)調(diào)用方式：中則不同，需使用函數(shù)調(diào)用方式：n定義：定義：Point p; void move(Point q, int x, i

17、nty);n運用：運用：move(p, x, y); Draw( )move(x, y)contains(aPoint)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral算法定義算法定義n定義：一個有窮的指令集，這些指令為解定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列決某一特定任務(wù)規(guī)定了一個運算序列n特性：特性：n輸入輸入 有有0個或多個輸入個或多個輸入

18、n輸出輸出 有一個或多個輸出有一個或多個輸出(處理結(jié)果處理結(jié)果)n確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的n有窮性有窮性 算法應在執(zhí)行有窮步后結(jié)束算法應在執(zhí)行有窮步后結(jié)束n有效性有效性 每一條運算應足夠基本每一條運算應足夠基本n事例學習：選擇排序問題事例學習：選擇排序問題n明確問題：遞增排序明確問題：遞增排序n解決方案：逐個選擇最小數(shù)據(jù)解決方案：逐個選擇最小數(shù)據(jù)n算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查到檢查到an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak;n n細化程序：程序細化程序：程序

19、SelectSort 算法設(shè)計算法設(shè)計 自頂向下，逐步求精自頂向下，逐步求精 void selectSort ( int a , const int n ) /對對n個整數(shù)個整數(shù)a0,a1,an-1按遞增順序排序按遞增順序排序 for (int i = 0; i n-1; i+) int k = i; /從從ai查到查到an-1, 找最小整數(shù)找最小整數(shù), 在在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; 模板模板 (template)(template)定義定義 適合多種數(shù)據(jù)

20、類型的類定義或算法，在特適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡單地代換，變成針對具體某定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。種數(shù)據(jù)類型的類定義或算法。用模板定義用于排序的數(shù)據(jù)表類用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H#define DATALIST_H#include /K是表項關(guān)鍵是表項關(guān)鍵碼類型碼類型template / /E是是表項類型表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (in

21、t low, int high); public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 類中所

22、有操作作為模板函數(shù)的實現(xiàn)類中所有操作作為模板函數(shù)的實現(xiàn)template void dataList : swap (int m1, int m2) /交換由交換由m1, m2為下標的數(shù)組元素的值為下標的數(shù)組元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;template int dataList:minKey (int low, int high) /查找數(shù)組查找數(shù)組Elementlow到到Elementhigh中具中具/有最小關(guān)鍵碼值的表項，函數(shù)返回其位置有最小關(guān)鍵碼值的表項，函數(shù)返回其位置 int

23、 min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義的重載操作定義的重載操作template ostream& operator (ostream& outStream, dataList outList) outStream “輸出數(shù)組內(nèi)容輸出數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl; ouStr

24、eam “輸出數(shù)組當前大小輸出數(shù)組當前大小 : ” outList.listSize endl; return outStream; template istream& operator (istream& inStream, dataList inList) /輸入對象為輸入對象為inList，輸入流對象為，輸入流對象為inStream cout inList.listSize; cout “輸入數(shù)組元素值輸入數(shù)組元素值 : n”; for (int i = 0; i inList.listSize; i+) cout “元素元素” i inList.elementi; re

25、turn inStream; template void dataList : sort ( ) /按非遞減順序?qū)Π捶沁f減順序?qū)istSize個關(guān)鍵碼個關(guān)鍵碼element0到到/elementArraySize-1排序排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i); #endif 使用模板的選擇排序算法的主函數(shù)使用模板的選擇排序算法的主函數(shù) #include #include “dataList.h” const int SZ = 10; int m

26、ain ( ) struct sick /患者患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; 定義對象時，代定義對象時，代入實際數(shù)據(jù)類型入實際數(shù)據(jù)類型重載友元操作重載友元操作標準標準IO操作操作消息通信消息通信算法簡單性能分析與度量算法簡單性能

27、分析與度量算法的性能標準算法的性能標準算法的后期測試算法的后期測試n對一個算法要作出全面的分析可分成兩個階對一個算法要作出全面的分析可分成兩個階段進行，即事前分析和事后測試段進行，即事前分析和事后測試n事前分析要求事前求出該算法的一個時間界事前分析要求事前求出該算法的一個時間界限函數(shù)。限函數(shù)。n事后測試則要求在算法執(zhí)行后通過算法執(zhí)行事后測試則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分析。的時間和實際占用空間的統(tǒng)計資料來分析。n事后分析要求在算法中的某些部位插裝時間事后分析要求在算法中的某些部位插裝時間函數(shù)函數(shù) time ( )time ( )，測定算法完成某一功能所，測定算

28、法完成某一功能所花費時間?；ㄙM時間。例如，給出順序搜索例如，給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an-1中搜索與給定值中搜索與給定值 x 相等的元相等的元/素，函數(shù)返回其位置，失敗返回素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i; 插裝 time( ) 的計時程序 double start, stop; time(&start); in

29、t k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout n runTime endl;事實上，算法運行時間要受輸入規(guī)模、利用編譯程序生成的目標代碼的質(zhì)量、計算機程序指令系統(tǒng)的品質(zhì)和速度等制約。算法的事前估計算法的事前估計n算法的事前估計主要包括時間復雜性和空算法的事前估計主要包括時間復雜性和空間復雜性的分析：間復雜性的分析：n問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。個數(shù)、被分類序列的正整數(shù)個數(shù)等。n時間復雜性：算法所需時間和問題

30、規(guī)模的時間復雜性：算法所需時間和問題規(guī)模的函數(shù)，記為函數(shù)，記為 T(n)T(n)。當。當 n n 時的時間復時的時間復雜性，稱為漸進時間復雜性。雜性，稱為漸進時間復雜性。n空間復雜性：算法所需空間和問題規(guī)模的空間復雜性：算法所需空間和問題規(guī)模的函數(shù)。記為函數(shù)。記為 S(n)S(n)。當。當 n n 時的時間復時的時間復雜性，稱為漸進空間復雜性。雜性，稱為漸進空間復雜性?？臻g復雜度度量空間復雜度度量時間復雜度度量時間復雜度度量n程序步確定方法程序步確定方法n插入計數(shù)全局變量插入計數(shù)全局變量countn建表，列出個語句的程序步建表，列出個語句的程序步例例 以迭代方式求累加和的函數(shù)以迭代方式求累加和

31、的函數(shù) float sum (float a , int n) float sum (float a , int n) float s = 0.0; float s = 0.0; for (int i = 0; i n; for (int i = 0; i n; i+)i+) s = s + ai; s = s + ai; return s; return s; 在求累加和程序中加入在求累加和程序中加入 count 語句語句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計執(zhí)行語統(tǒng)計執(zhí)行語句條數(shù)句條數(shù) for (int i

32、 = 0; i n; i+) count += 2; /針對針對 for 語句語句s += ai;count+; /針對賦值語句針對賦值語句 count += 2; /針對針對 for 的最后一的最后一次次 count+; /針對針對 return 語句語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步數(shù) count = 3*n+4留意：留意： 一個語句本身的程序步數(shù)可能不等于該語一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。句一次執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語句賦值語句x = sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為 1；一次執(zhí)行對函數(shù)一次

33、執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程序的調(diào)用需要的程序步數(shù)為步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+5計算累加和程序計算累加和程序程序步數(shù)計算工作表格程序步數(shù)計算工作表格時間復雜度的漸進表示法時間復雜度的漸進表示法例例 求兩個求兩個n階方陣的乘積階方陣的乘積C = ABvoid MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2n+2) Cij = 0; n2 for (int k

34、= 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3 + 5n2 + 4n +2時間復雜度的漸進表示法時間復雜度的漸進表示法n算法中所有語句的頻度之和是矩陣階數(shù)算法中所有語句的頻度之和是矩陣階數(shù)n的的函數(shù)函數(shù)n T(n) = 3n3 + 5n2 + 4n +2n一般地，稱一般地，稱 n 是問題的規(guī)模。則時間復雜是問題的規(guī)模。則時間復雜度度 T(n) 是問題規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。n當當n趨于無窮大時，把時間復雜度的數(shù)量級趨于無窮大時，把時間復雜度的數(shù)量級階稱為算法的漸進時間復雜度階稱為算法的漸進時間復雜度n T(n) = O(n3

35、) 大大O表示法表示法n加法規(guī)則加法規(guī)則 針對并列程序段針對并列程序段 n T(n, m) = T1 (n) + T2 (m)n = O(max (f (n), g (m)n各種函數(shù)的增長趨勢各種函數(shù)的增長趨勢 n c log2n n nlog2n n2 n3 2n 3n n!T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y =

36、 0;for ( int k = 0; k n; k + ) x +;n乘法規(guī)則乘法規(guī)則 針對嵌套程序段針對嵌套程序段n T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n漸進的空間復雜度漸進的空間復雜度n S (n) = O(f (n)n兩個并列循環(huán)的例子兩個并列循環(huán)的例子 void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行中各行 sumi = 0.0; /數(shù)據(jù)累加數(shù)據(jù)累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行數(shù)據(jù)和打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; 漸進時間復雜度為漸進時間復雜度為 O(max (m*n, m)起泡排序起泡排序 void bubbleSort (int a , int n ) /對表對表 a 逐趟比較逐趟比較, n 是表當前長度是表當前長度 for (int i =