數(shù)據(jù)結(jié)構(gòu)新——用面向?qū)ο蠓椒ㄅc

1、數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE 用面向?qū)ο蠓椒ㄅcC+描述n 課程特點(diǎn)n 介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的傳遞和轉(zhuǎn)換；、n 課程采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)；n 兼有面向過程和面向?qū)ο箅p重特色的C+語言作為算法的描述工具；n 強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識和面向?qū)ο蟪绦蛟O(shè)計(jì)基本能力的雙基訓(xùn)練。2n 課程要求n “聽課”“自學(xué)”“實(shí)踐”并舉n 掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實(shí)現(xiàn)技術(shù)；n 學(xué)會(huì)做簡單的算法分析，包括算法的時(shí)間代價(jià)和空間代價(jià)。3參考資料n 數(shù)據(jù)結(jié)構(gòu)（C語言版）n 嚴(yán)蔚敏、吳偉民nn 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+語言描述）n 殷人昆nn 數(shù)據(jù)結(jié)構(gòu) C+與面向?qū)ο蟮耐緩絥 張乃孝、裘

2、忠燕n 高等教育n 新編實(shí)用算法分析與程序設(shè)計(jì)n 王建德、吳永輝郵電nn 數(shù)據(jù)結(jié)構(gòu)-Java版n （美）D.S.Malik, P.S.Nair 著，楊浩譯nn 數(shù)據(jù)結(jié)構(gòu)與算法C+版（美）Adam Drozdek編著，鄭巖，戰(zhàn)曉蘇 翻譯nn4n 如何評價(jià)成績？（擬訂待調(diào)整，三個(gè)班級統(tǒng)一 ）n 期末閉卷筆試（約60%左右）n 期中閉卷筆試（約15%左右）n 項(xiàng)目實(shí)踐（約35%左右）n 上機(jī)實(shí)踐n 作業(yè)及出勤情況成績?yōu)閮?yōu)者不超過30%5前四周上機(jī)實(shí)踐課程內(nèi)容簡介n 第一周：C+程序設(shè)計(jì)語言n 基礎(chǔ)知識n 語法、數(shù)據(jù)類型、指針、函數(shù)、傳遞參數(shù)和地址n C+開發(fā)環(huán)境n VC的使用技巧n 上機(jī)操作實(shí)例（如

3、何創(chuàng)建工程，如何加入頭文件、cpp文件等；怎樣編譯；怎樣調(diào)試）n 用具體實(shí)例來說明上述概念和使用技巧6n 第二周：面向?qū)ο蟮某绦蛟O(shè)計(jì)OOPn 類和對象n 構(gòu)造/析構(gòu)函數(shù)n 類的繼承n 派生類n 虛函數(shù)與多態(tài)n 重載類型referencenn 友元7n 第三周：template介紹n template及其優(yōu)勢n 模板的多態(tài)性n template使用方法n 函數(shù)模板/類模板n 以一些具體實(shí)例來介紹template的應(yīng)用8n 第四周：程序設(shè)計(jì)風(fēng)格及設(shè)計(jì)實(shí)踐n 編程規(guī)范n 好程序的定義n 命名規(guī)則n 表達(dá)式和語句n 函數(shù)n 如何寫Documentn 注釋n 什么樣的編碼是好的編程風(fēng)格9n 數(shù)據(jù)結(jié)構(gòu)的概

4、念n 數(shù)據(jù)結(jié)構(gòu)的抽象形式n 作為ADT的C+類n 算法定義n 算法性能分析與度量n 本章小結(jié)1.1 數(shù)據(jù)結(jié)構(gòu)的概念n 宇宙三要素：物質(zhì)、能量和信息n 信息是客觀世界在人腦中的反映。n 數(shù)據(jù)是信息的載體。n 數(shù)據(jù)是怎樣在計(jì)算機(jī)中n 舉例說明和組織的？11“學(xué)生”表格12345678912學(xué) 號姓 名籍 貫出生年月98131劉激揚(yáng)男北 京1979.1298164衣春生男青 島1979.0798165盧聲凱男天 津1981.0298182袁秋慧女廣 州1980.1098224洪 偉男太 原1981.0198236熊南燕女蘇 州1980.0398297宮 力男北 京1981.0198310蔡曉莉女昆

5、明1981.0298318陳 健男杭 州1979.12“課程”表格13課程編號課 程 名學(xué)時(shí)024002程序設(shè)計(jì)基礎(chǔ)64024010匯編語言48024016計(jì)算機(jī)原理64024020數(shù)據(jù)結(jié)構(gòu)64024021微機(jī)技術(shù)64024024操作系統(tǒng)48024026數(shù)據(jù)庫原理48“選課單”包含如下信息學(xué)生選課系統(tǒng)中實(shí)體的網(wǎng)狀關(guān)系14選課(學(xué)號,課程號,成績)課程(課程號,課程名,學(xué)分)學(xué)生(學(xué)號,姓名,籍貫)學(xué)號課程編號成績時(shí)間UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖binetcswyintaoxie15Tree.cppStack.cppQueue.cppdsmathuserlib/ (root)基本概念：數(shù)據(jù) (D

6、ata)n 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號的集合。u 數(shù)值性數(shù)據(jù)(int)u 非數(shù)值性數(shù)據(jù) (char)16基本概念：數(shù)據(jù)元素 (Data Element)n 數(shù)據(jù)的基本，在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。n 有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有含義的最小標(biāo)識。n 數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、。17基本概念:數(shù)據(jù)對象 (Data Object)n 數(shù)據(jù)的子集，具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。N=0, ±1, ±2, u 整數(shù)數(shù)據(jù)對象u 學(xué)生數(shù)據(jù)對象n 數(shù)據(jù)

7、對象中所有成員之間存在某種關(guān)系，如學(xué)生按學(xué)號的排序；按的分類等。n 數(shù)據(jù)成員及其之間關(guān)系，是數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容。18什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：Data_Structure=D, R其中，D是某一數(shù)據(jù)對象，R是該對象中所 有數(shù)據(jù)成員之間關(guān)系的有限集合。19N個(gè)之間的連通關(guān)系3網(wǎng)狀關(guān)系樹形關(guān)系20數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n 數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；n 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示，即數(shù)據(jù)的表示；n 數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)元素施加的操作。例如：座位/學(xué)生（按班級）21DS第一部分：數(shù)據(jù)的邏輯結(jié)構(gòu)n 數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描

8、述數(shù)據(jù)，與數(shù)據(jù)的無關(guān)；n 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；n 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)。22數(shù)據(jù)的邏輯結(jié)構(gòu)分類n 線性結(jié)構(gòu)u 線性表n 非線性結(jié)構(gòu)u 樹u 圖（或網(wǎng)絡(luò)）23線性結(jié)構(gòu)：useretcdevbinlib樹形結(jié)構(gòu)：樹1二叉樹1二叉搜索樹6313269453109111224堆結(jié)構(gòu)（樹的特例）：1211971066373548289“最小”堆“最大”堆25121221663113335454網(wǎng)絡(luò)結(jié)構(gòu)圖結(jié)構(gòu)26DS第二個(gè)重要部分：數(shù)據(jù)的n 數(shù)據(jù)的結(jié)構(gòu)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)；n 數(shù)據(jù)的u 順序結(jié)構(gòu)依賴于計(jì)算機(jī)語言。表示表示表示表示主要用于內(nèi)存的

9、表示uu 索引u 散列主要用于外存（文件）的表示27數(shù)據(jù)結(jié)構(gòu)的抽象層次28n 線性類u 直接存取類u 順序存取類u 廣義索引類數(shù)組、文件表、棧、隊(duì)列、優(yōu)先隊(duì)列線性索引、搜索樹n 非線性u 層次u 群類類樹、二叉樹、堆類集合、圖29數(shù)據(jù)結(jié)構(gòu)的課程內(nèi)容體系方面層次數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)結(jié)構(gòu)算法評價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析1.2 數(shù)據(jù)結(jié)構(gòu)的抽象形式1.2.1 數(shù)據(jù)類型定義：一組性質(zhì)相同的值的集合，以及定義于這個(gè)值集合上的一組操作的總稱。n C語言中的數(shù)據(jù)類型char字符型int整型floatdoublevoid無值浮點(diǎn)型 雙精度型int取值范圍-32768, 32767；每個(gè)數(shù)

10、據(jù)類型對應(yīng)一組操作int(6/4)=1(float)(6.0/4.0)=1.531n 數(shù)據(jù)類型由n 基本數(shù)據(jù)類型 或n 構(gòu)造數(shù)據(jù)類型組成n 構(gòu)造數(shù)據(jù)類型由不同成分類型。n 基本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。n 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過是從編程者的角度來使用。321.2.2 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型(ADTs: AbstractData Types)§ 由用戶定義， 用以表示應(yīng)用問題的數(shù)據(jù)模型。§ 抽象的本質(zhì)：抽取反映問題本質(zhì)的東西， 忽略非本質(zhì)的細(xì)節(jié)。§ ADT：由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)的服務(wù)（或稱操作）。§ 信息隱蔽和數(shù)據(jù)封裝

11、，使用與實(shí)現(xiàn)相分離。33使用者抽象數(shù)據(jù)類型查找登錄刪除修改符號表34自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個(gè)整數(shù)的有序子集合,它開始于0，能表示的最大整數(shù)(MaxInt)。結(jié)束于Function: 對于所有的 x, yÎNaturalNumber；False, TrueÎBoolean, +、-、<、=、=等都是可用的服務(wù)。Zero( ): NaturalNumber返回自然數(shù)035IsZero(x):Boolean Add (x, y):if (x=0)返回Trueelse返回Falseif (x+y<=MaxIn

12、t)返回 x+yNaturalNumber else返回MaxIntSubtract(x, y):if (x<y)返回0NaturalNumber else返回 x-yEqual(x, y) :Boolean Successor(x):if (x=y)返回Trueelse返回Falseif (x=MaxInt)返回xNaturalNumber elseend NaturalNumber返回x+11.3 作為ADT的C+類n 面向?qū)ο蟮母拍頽 Codd and Yourdonn Rational Rose, IBMn 面向?qū)ο?對象類繼承通信n 實(shí)現(xiàn)信息隱藏和封裝37n 對象u 實(shí)體、規(guī)格

13、說明等。u 由一組屬性值和在這組值上的一組服務(wù)（或稱操作）。n 類(Class)，實(shí)例(Instance)u 具有相同屬性和服務(wù)的對象歸于同一類， 形成類。u 類中的對象為該類的實(shí)例。38quadrilateral1 屬性值(35, 10) (50, 10)quadrilateral2 屬性值(45, 65) (50, 45)quadrilateral 屬性aPoint1 aPoint2aPoint3aPoint4(35, 25)(50, 25)(65, 66)(60, 70)服務(wù) 服務(wù) Draw( ) move(Dx, Dy)contains(aPoint) 服務(wù) Draw( ) move(

14、Dx, Dy)contains(aPoint)Draw( ) move(Dx, Dy) contains(aPoint)四邊形類及其對象39n 繼承u 派生類：四邊形，三角形，子類特化類（特殊化類）u 基類：多邊形父類泛化類（一般化類）n 通信u 消息傳遞40PolygonQuadrilateralreferencePoint VerticesreferencePoint VerticesDraw( ) move(Dx, Dy) contains(aPoint)Draw( ) move(Dx, Dy) contains(aPoint)Polygon 類Polygon的子類Quadrilater

15、al類41用C+描述面向?qū)ο蟪绦騨 C+的函數(shù)特征n C+的數(shù)據(jù)n C+的作用域n C+的類n C+的對象n C+的輸入/輸出n C+的函數(shù)n C+的參數(shù)傳遞C+的函數(shù)名重載和操作符重載nC+的動(dòng)態(tài)分配n友元(friend)函數(shù)內(nèi)聯(lián)(inline)函數(shù)結(jié)構(gòu)(struct)與類(union)與類nnnn42詳細(xì)介紹上機(jī)實(shí)踐課模板(template)目的：實(shí)現(xiàn)軟件重用定義適合多種數(shù)據(jù)類型的類定義或算法， 在特定環(huán)境下通過簡單地代換，變成具體某種數(shù)據(jù)類型的類定義或算法。43用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H #define DATALIST_H #include <

16、;iostream.h>template <class Type> class dataListprivate:Type *Element; int ArraySize;void Swap(int m1, int m2); int MaxKey(int low, int high);44public:dataList(int size=10) : ArraySize(size), Element(new Type Size) dataList( ) delete Element; void Sort( );friend ostream & operator <&

17、lt; (ostream &outStream, datalist <Type> &outList);friend istream & operator >> (istream &inStream, datalist <Type> &inList);#endif45類中所有操作作為模板函數(shù)的實(shí)現(xiàn)#ifndef SELECTTM_H #define SELECTTM_H #include “datalist.h”template <class Type> void dataList <Type>

18、:Swap(int m1,int m2)/交換由m1, m2為下標(biāo)的數(shù)組元素的值Type temp=Elementm1;Elementm1=Elementm2; Elementm2=temp;46template <class Type> int dataList <Type> :MaxKey(int low, int high)/查找數(shù)組Elementlow到Elementhigh/中的最大值，函數(shù)返回其位置int max=low;for (int k=low+1; k<=high; k+) if (Elementmax<Elementk)max=k; r

19、eturn max;47template <class Type>ostream & operator << (ostream &OutStream,dataList <Type> OutList)OutStream<<“數(shù)組內(nèi)容：n”;for (int i=0; i<OutList.ArraySize; i+)OutStream<<OutList.Elementi<< ;OutStream<<endl;OuStream<<“數(shù)組當(dāng)前大?。骸?lt;<OutList.Ar

20、raySize<<endl;return OutStream;48template <class Type>istream & operator >> (istream &InStream,dataList <Type> InList)/輸入對象為InList，輸入流對象為InStreamcout<<“錄入數(shù)組當(dāng)前大小：”;Instream>>InList.ArraySize;cout<<“錄入數(shù)組元素值：n”;for (int i=0; i<InList.ArraySize; i+) c

21、out<<“元素”<<i<<“：”;InStream>>InList.Elementi; return InStream;49template <class Type> void dataList <Type> : Sort( )/按非遞減順序?qū)rraySize個(gè)關(guān)鍵碼/Element0到ElementArraySize-1排序for (int i=ArraySize-1; i>0; i-)int j=MaxKey(0, i);if (j!=i)swap(j, i);#endif50使用模板的選擇排序算法的主函數(shù)#

22、include “selecttm.h” const int SIZE=10; int main( ) dataList <int> TestList(SIZE); cin>>TestList; cout<<TestList<<endl; TestList.Sort( ); cout<<TestList<<endl; return 0;模板的詳細(xì)介紹上機(jī)實(shí)踐課1.4 算法定義n 定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定一個(gè)運(yùn)算序列。n 特性：u 輸入Input有0個(gè)或多個(gè)輸入；u 輸出Output有一個(gè)或多個(gè)

23、輸出（處理結(jié)果）；u 確定性u 有窮性u 有效性每步定義都是確切無歧義的；算法應(yīng)在執(zhí)行有窮步后結(jié)束； 每一條運(yùn)算應(yīng)足夠基本。52算法Algorithm=程序Program？n 算法是有窮性結(jié)束。算法應(yīng)在執(zhí)行有窮步后n 程序可能持續(xù)運(yùn)行，直到系統(tǒng)例如操作系統(tǒng)wait函數(shù)。n 算法是面向問題的。n 程序是算法的具體語言實(shí)現(xiàn)。，53算法設(shè)計(jì)自頂向下，逐步求精u 事例學(xué)習(xí)：n個(gè)整數(shù)的選擇排序問題基本思想: 在一組對象ViVn-1中選擇具有最小排序碼的對象； 若它不是這組對象中的第一個(gè)對象，則將它與這組對象中的第一個(gè)對象對調(diào)； 在這組對象中剔除這個(gè)具有最小排序碼的對象，在剩下的對象Vi+1Vn-1中重復(fù)

24、執(zhí)行第、步，直到剩余對象只有一個(gè)為止。54初始4925125*32101640852最小者 08交換21, 08i=0492525*211608最小者 16交換25, 16i=1492525*211608最小者 21交換49, 21i=24925*25211608各趟排序后的結(jié)果55最小者 25*無交換i=34925*25211610802345最小者 25無交換i=44925*25211608結(jié)果4925*25211608各趟排序后的結(jié)果56u 明確問題：遞增排序u 解決方案：逐個(gè)選擇最小數(shù)據(jù)u 算法框架：for (int i=0; i<n-1; i+)/n-1趟從ai檢查到an-1若

25、最小整數(shù)在ak，交換ai與ak;u 細(xì)化程序：程序SelectSort57void selectSort(int a , const int n)/對n個(gè)整數(shù)a0到an-1按遞增順序排序for (int i=0; i<n-1; i+)int k=i;/從ai查到an-1，找最小整數(shù)，在ak for (int j=i+1; j<n; j+)if (aj<ak)k=j;int temp=ai;ai=ak;ak=temp;1.5 算法性能分析與度量u 如何度量數(shù)據(jù)結(jié)構(gòu)和算法的性能好壞？u 算法的性能標(biāo)準(zhǔn)u 算法的后期測試u 算法的事前估計(jì)59算法的性能標(biāo)準(zhǔn)u 正確性u 可使用性用戶

26、友u 可讀性u 程序設(shè)計(jì)風(fēng)格，軟件產(chǎn)業(yè)，對大項(xiàng)目非常重要，CMM (Capability Maturity Mu 上機(jī)實(shí)踐課詳細(xì)介紹u 效率時(shí)間與空間代價(jià)u 確定問題規(guī)模與算法時(shí)間和空間的關(guān)系u 健壯性容錯(cuò)性u 簡單性 for Software )算法的后期測試在算法中的某些部位插裝時(shí)間函數(shù)time( )測定算法完成某花費(fèi)時(shí)間。能所舉例說明61順序搜索 (Sequenial Search)int seqsearch(int a , const int n, const int x)/在a0, , an-1中搜索xint i=0;while (i<n && ai!=x) i

27、+;if (i=n) return i;return -1;62插裝time( )的計(jì)時(shí)程序double start, stop; time(&start);int k=seqsearch(a, n, x); time(&stop);double runTime=stop-start;cout<<“ ”<<n<<“ ”<<runTime<<endl;缺點(diǎn):1、與環(huán)境配置有關(guān)，不同的PC，不同的系統(tǒng)性能，產(chǎn)生 不同的時(shí)間差值;2、需要確定合適的計(jì)數(shù)方法，處理器自帶的計(jì)數(shù)函數(shù)是毫秒級，因此如果少于毫秒的數(shù)量級，計(jì)數(shù)。63v

28、oid TimeSearch( )int a1000, n20;for (int j=1; j<=1000; j+)aj-1=j;/a0=1, a1=2, 初始化afor (j=0; j<10; j+) nj=10*j;/n0=0, n1=10, n2=20nj+10=100*(j+1);/n10=100, n11=200, n12=300 .cout<<“n time”<<endl;64for (j=0; j<20; j+) long start, stop;/得到計(jì)算時(shí)間time(&start);/開始計(jì)時(shí)int k=seqsearch(a

29、, nj, 0);/不查找time(&stop);/停止計(jì)時(shí)long runTime=stop-start;/計(jì)算運(yùn)行時(shí)間cout<<“ ”<<nj<<“ ”<<runTime<<endl;/輸出cout<<“Times are in hundredths of a second.”<<endl;65程序測試結(jié)果輸出假設(shè)時(shí)間函數(shù)time( )的測量精度為0.01秒，程序測試結(jié)果都是0，表明時(shí)間函數(shù)的測試精度不夠。66n100 200 300 400 500 600 700 800 900 1000run

30、 Time0000000000n0102030405060708090run Time0000000000改進(jìn)的計(jì)時(shí)程序void TimeSearch( ) int a1000, n20;const long r20=300000, 300000, 200000, 200000,100000, 100000, 100000, 80000, 80000, 50000, 50000,25000, 15000, 15000, 10000, 7500, 7000, 6000, 5000,5000;for (int j=1; j<=1000; j+)aj-1=j;/初始化afor (j=0; j&

31、lt;10; j+) /為n賦值nj=10*j;nj+10=100*( j+1);cout<<“n totalTime runTime”<<endl;67for (j=0; j<20; j+) /得到計(jì)算時(shí)間long start, stop; time(&start); /開始計(jì)時(shí)for (long b=1; b<=rj; b+)int k=seqsearch(a, nj, 0);/不查找，執(zhí)行rj次time(&stop); /停止計(jì)時(shí)long totalTime=stop-start;float runTime=(float)(totalT

32、ime)/(float)(rj);/總時(shí)間除以重復(fù)執(zhí)行次數(shù)cout<<“ ”<<nj<<“ ”<<totalTime<<“ ”<<runTime<<endl;68程序修改后的測試結(jié)果輸出測量數(shù)據(jù)與n基本呈線性關(guān)系69n0102030405060708090總的運(yùn)行時(shí)間241533582736467565659604681472單個(gè)運(yùn)行時(shí)間0.00080.00180.00290.00370.00470.00560.00660.00750.00850.0094n100200300400500600700800900

33、1000總的運(yùn)行時(shí)間527505451593494439484467434484單個(gè)運(yùn)行時(shí)間0.01050.02020.03010.03950.04940.05850.06910.07780.08680.0968/矩陣相乘：將aNN和bNN兩個(gè)N*N矩陣相乘/最終的結(jié)果放在cNN中返回給用戶void matrix_multi(int aNN, int bMN, int cNN)int i=j=k=0; int tmp;for (i=0; i<N; i+) for (j=0; j<N; j+)ci, j=0;for (i=0; i<N; i+) for (j=0; j<N

34、; j+)for (k=0; k<N; k+)ci, j=ai, k*bk, j+ci, j;return 0;70/增加了time( )函數(shù)后的矩陣相乘程序void multi( )int aNN, int bNN, int cNN; int i, j, k=0;for (i=0; i<N; i+) for (j=0; i<N; i+)ai, j=k+; for (i=0; i<N; i+)for (j=0; i<N; i+) bi, j=k+;long start, stop; time(&start);matrix-multi(a, b, c); t

35、ime(&stop);long runtime=stop-start; cout<<“time is ”<<runtime<< endl;71n 算法的運(yùn)行時(shí)間依賴于所使用的計(jì)算機(jī)系統(tǒng)、 編譯器、可用空間大小等。n 同樣的算法在速度不同的計(jì)算機(jī)上，執(zhí)行速度 相差非常大。n 算法用不同的編譯器編譯出的目標(biāo)代碼不一樣 長，完成同樣功能所需時(shí)間不同。n 如果可用空間不夠，算法需要的運(yùn)行時(shí)間很多；如果空間足夠大，則時(shí)間明顯減少。n 算法運(yùn)行時(shí)間的測量用于評估算法的正確性和可用性，并不能算法的優(yōu)劣。n 通過比較算法的復(fù)雜性來評價(jià)。n 算法復(fù)雜性與具體運(yùn)行環(huán)境和

36、編譯器無關(guān)。算法的事前估計(jì)u 空間復(fù)雜度(Space Complexity)u 時(shí)間復(fù)雜度(Time Complexity)u 用來確定問題規(guī)模n（比如學(xué)生人數(shù)）與算法空間f(n)，程序步數(shù)或者時(shí)實(shí)現(xiàn)時(shí)需要的間開銷g(n)的關(guān)系。u 在目前的研究領(lǐng)域，對算法進(jìn)行分析時(shí)，時(shí)空復(fù)雜性是最重要的基本功，最理想的算法評價(jià)標(biāo)準(zhǔn)。73空間復(fù)雜度度量空間的固定部分程序指令代碼的空間，常數(shù)、簡單變量、定n長成分（如數(shù)組元素、結(jié) 據(jù)成員等）變量所占空間。n 可變部分分、對象的數(shù)與實(shí)例特性有關(guān)的成分變量所占空間、變量所占空間、遞歸棧所用空間、通過new和delete命令動(dòng)態(tài)使用空間。74例1：計(jì)算表達(dá)式float

37、 abc(float a, folat b, float c) return a+b+b*c+(a+b-c)/(a+b)+4.0;例2：以迭代方式求累加和的函數(shù)float sum(float a , int n) float s=0.0;for (int i=0; i<n; i+) s+=ai;return s;例3：以遞歸方式求累加和的函數(shù)float rsum(float a , int n) if (n<=0)return 0;else returnrsum(a, n-1)+an-1;75時(shí)間復(fù)雜度度量n 編譯時(shí)間n 與編譯程序有關(guān)，與實(shí)例性質(zhì)無關(guān)。n 運(yùn)行時(shí)間u 程序步F 語

38、法上或語義上有意義的一段指令序列。F 執(zhí)行時(shí)間與實(shí)例特性無關(guān)。語句程序步數(shù)為0，表達(dá)式程序F 例如，步數(shù)為1。76程序步確定方法w計(jì)數(shù)全局變量count；w 建表，列出各語句的程序步。77例1：以迭代方式求累加和的函數(shù)float sum(float a , int n)float s=0.0;for (int i=0; i<n; i+) s+=ai;return s;78在求累加和程序中加入count語句float sum(float a , int n)float s=0.0;count+;/count統(tǒng)計(jì)執(zhí)行語句條數(shù)for (int i=0; i<n; i+) count+;

39、/ s+=ai; count+;for語句/賦值語句count+; count+; return s;/for的最后一次return語句執(zhí)行結(jié)束得程序步數(shù)？ count=2*n+379程序的簡化形式void sum(float a , int n)for (int i=0; i<n; i+) count+=2;count+=3;80注意：一個(gè)語句本身的程序步數(shù)，可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。例如：賦值語句x=sum(R, n)本身的程序步數(shù)為 1；一次執(zhí)行對函數(shù)sum(R, n)的調(diào)用需要的程序步數(shù)為 2*n+3；一次執(zhí)行的程序步數(shù)為1+2*n+3=2*n+481第二種方法:

40、計(jì)算累加和程序程序步數(shù)計(jì)算工作表格82程 序 語 句一次執(zhí)行所需程序步數(shù)執(zhí)行頻度程序步數(shù)010float s=0.0;111for (int i=0; i<n; i+)1n+1n+1s+=ai;1nnreturn s;111010總程序步數(shù)2n+3例2：以遞歸方式求累加和的函數(shù)float rsum(float a , int n)if (n<=0)return 0;else return rsum(a, n-1)+an-1;83在求累加和程序中加入count語句float rsum(float a , int n)count+;/if語句if (n<=0) count+; r

41、eturn 0;else /return語句count+=2;/else與return語句return rsum(a, n-1)+an-1;84設(shè)count初始值為0，Trsum(n)是程序執(zhí)行后的count值。n=0，Trsum(0)=2; n>0，Trsum(n)=Trsum(n-1)+3;Trsum(n)=3+Trsum(n-1)=3+3+Trsum(n-2)=3*2+Trsum(n-2)=3+3+3+Trsum(n-3)=3*3+Trsum(n-3)=3*n+Trsum(0)=3n+285計(jì)算累加和程序程序步數(shù)計(jì)算工作表格86程 序 語 句一次執(zhí)行所需程序步數(shù)執(zhí)行頻度程序步數(shù)n=

42、0n>0n=0n>001100if (n<=0)11111return 0;11010else return2+Trsum(n-1)0102+Trsum (n-1)rsum(a, n-1)+an-1;101100總程序步數(shù)23+Trsum (n-1)87程序執(zhí)行代價(jià)執(zhí)行次數(shù)int i=j=k=0; int tmp;for (i=0; i<N; i+) for (j=0; j<N; j+)ci, j=0;for (i=0; i<N; i+) for (j=0; j<N; j+)for (k=0; k<N; K+)ci, j=ai, k*bk, j+

43、ci, j; return 0;C1 C2 C3 C4 C5 C6 C7 C8 C9 C1011N+1 N*(N+1)N*NN+1N*N+1） N*N*(N+1)N*N*N 1n 程序步本身就不是一個(gè)準(zhǔn)確的概念，而是一個(gè)抽象的概念。n 再作一次抽象，從由多種因素的時(shí)間復(fù)雜性中抽取出其主要因素，將常數(shù)抽象為1，有利于抓住主要雜性分析。n 大O表示法，簡化復(fù)88時(shí)間復(fù)雜度的漸進(jìn)表示法例：求兩個(gè)n階方陣的乘積C=A´Bvoid MatrixMultiply(int Ann, int Bnn, int Cnn)for (int i=0; i<n; i+) for (int j=0; j

44、<n; j+) Cij=0;for (int k=0; k<n; k+) n+1 n(n+1) n2 n2(n+1)Cij=Cij+Aik*Bkj; n32n3+3n2+2n+189n 算法中所有語句的頻度之和是矩陣階數(shù)n 的函數(shù)T(n)=2n3+3n2+2n+1n 一般地，稱n是問題的規(guī)模。則時(shí)間復(fù)雜度T(n)是問題規(guī)模n的函數(shù)。n 當(dāng)n趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度。T(n)=O(n3)-大O表示法90n 大O表示法最壞情況n 當(dāng)且僅當(dāng)存在正整數(shù)c和n0，使得T(n)cf(n) 對所有的nn0成立，則稱該算法的漸進(jìn)時(shí)間復(fù)雜度為T(n)=O(f(

45、n)。n 當(dāng)實(shí)例特性n充分大時(shí)，算法的時(shí)間復(fù)雜度隨n變化，在最壞情況下若存在一個(gè)增長的上界，即cf(n)，則該算法的時(shí)間復(fù)雜度增長的數(shù)量級為f(n)，即稱該算法的漸進(jìn)時(shí)間復(fù)雜度為T(n)=O(f(n)。91n 大O表示法的使用n 需要考慮關(guān)鍵操作的程序步數(shù)。n 關(guān)鍵操作大多在循環(huán)和遞歸中；n 在多數(shù)場合中，程序步驟與執(zhí)行頻度一一對應(yīng)。n 如果給出的是漸進(jìn)值，可直接考慮關(guān)鍵操作的執(zhí)行頻度，提出其與實(shí)例特性n的函數(shù)關(guān)系g(n)。92n 漸進(jìn)時(shí)間復(fù)雜度的計(jì)算n 單個(gè)循環(huán)n 循環(huán)內(nèi)的簡單語句即為關(guān)鍵操作，該程序段的 漸進(jìn)時(shí)間復(fù)雜度應(yīng)是此關(guān)鍵操作的執(zhí)行頻度的 大O表示。n 幾個(gè)并列的循環(huán)n 分析每個(gè)循環(huán)

46、的漸進(jìn)時(shí)間復(fù)雜度，然后利用大O表示法的加n 多層的嵌套循環(huán)n 關(guān)鍵操作應(yīng)該在最內(nèi)層循環(huán)中，先自外向內(nèi)層 層分析每層循環(huán)的時(shí)間漸進(jìn)復(fù)雜度，然后利用則來計(jì)算漸進(jìn)時(shí)間復(fù)雜度。大O表示法的乘則來計(jì)算漸進(jìn)時(shí)間復(fù)雜度。93n 加則并列程序段T(n, m)=T1(n)+T2(m)=O(max(f(n), g(m)94c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!n 取c、log2n、n、nlog2n時(shí)間效率比較高；n 取n2、n3時(shí)間效率差強(qiáng)人意；n 取2n、3n、n!當(dāng)n稍微大一點(diǎn)，算法的時(shí)間代價(jià)變?yōu)楹艽?，以?/p>

47、于不能計(jì)算。T(n)=T1(n)+T2(n)+T3(n)=O(max(1, n, n2)= O(n2)95變量計(jì)數(shù)T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)for (int i=0; i<n; i+) for (int j=0; j<n; j+)y+;for (int k=0; k<n; k+)x+;x=0; y=0;兩個(gè)并列循環(huán)的例子void exam(float x , int m, int n)float sum ;for (inti=0; i<m; i+) /x中各行sumi=0.0;/數(shù)據(jù)累加for (int j=0; j<n; j+

48、) sumi+=xij;for (i=0; i<m; i+)/打印各行數(shù)據(jù)和cout<<i<<“: ”<<sumi<<endl;漸進(jìn)時(shí)間復(fù)雜度為 O(max(m*n, m)96n 乘則嵌套程序段T(n, m)=T1(n)*T2(m)=O(f (n)*g(m)97如果一個(gè)程序的循環(huán)中有一個(gè)包含有循環(huán)的函 數(shù)調(diào)用語句，也可在被調(diào)用函數(shù)內(nèi)部尋找關(guān)鍵操作，使用乘 則來計(jì)算漸進(jìn)時(shí)間復(fù)雜度。兩個(gè)嵌套循環(huán)的例子起泡排序（遞增）基本思想：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€(gè)數(shù)為n。最多作n-1趟，i=1, 2, ¼, n-1。在第i趟中從后向前，n-2, ¼,j=n-1,i ， 順次兩兩比較Vj-1.key和Vj.key。如果發(fā)生逆序，則交換Vj-1和Vj。984925125*32101640852i=exchang=1i=exchang=1i=08exchang=149i=42525*211608exchang=0各趟排序后的結(jié)果99template <class Type> void dataList <Type> :bubbleSort( ) /對表逐趟比較，ArraySize是表當(dāng)前長度int i=1;int exchange=1;/當(dāng)