數(shù)據(jù)結(jié)構(gòu)-第一章2

1、 Software College Northeastern University Autumn 2005數(shù)據(jù)結(jié)構(gòu)Data Structure東北大學(xué)軟件學(xué)院 董傲霜本課程學(xué)習(xí)的目的通過本課程的學(xué)習(xí)掌握常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)特征、存儲結(jié)構(gòu)及相關(guān)算法。學(xué)會從問題入手，分析研究計算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的操作算法，并初步掌握時間和空間分析技術(shù)。 學(xué)會書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀，能上機(jī)調(diào)試并排除錯誤。 本課程學(xué)習(xí)要求要求掌握線性表、棧、隊列、串、數(shù)組、廣義表、樹、圖及文件等常用的一些數(shù)據(jù)結(jié)構(gòu)的邏輯形式、存

2、儲形式以及實現(xiàn)各種操作的算法。掌握在上述各種數(shù)據(jù)結(jié)構(gòu)上經(jīng)常實現(xiàn)的查找和排序的基本方法。能對工作中遇到的一些算法的時間復(fù)雜性和空間復(fù)雜性進(jìn)行分析。能根據(jù)用戶的要求及系統(tǒng)提供的數(shù)據(jù)，設(shè)計或選擇合適的數(shù)據(jù)結(jié)構(gòu)并能編寫正確的算法解決實際問題。 教材及參考書(1) 教材嚴(yán)蔚敏，吳偉民編著：數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2004.11 嚴(yán)蔚敏，吳偉民，米寧編著：數(shù)據(jù)結(jié)構(gòu)題集（C語言版） 清華大學(xué)出版社，2004.7教材及參考書(2) 參考書算法與數(shù)據(jù)結(jié)構(gòu)-C語言描述,張乃孝主編,高等教育出版社。Mark Allen Weiss, Data Structures and Problem Solvin

3、g Using C+, published by Addison Wesley Longman, 2000.5。學(xué)時分配及考核方式學(xué)時分配：授課 60學(xué)時 上機(jī)實驗 20學(xué)時課程成績： 平時成績 期末考試成績 平時成績 20 書面作業(yè)、上機(jī)練習(xí) 期末考試 80 閉卷筆試教師答疑方式Email： dongaoshuang固定答疑 時間：周二下午13：0016：00 地點：易購425課件及實驗報告格式下載 郵箱：sjkxt- 密碼：sjkxtsjkxt內(nèi)容安排(1) 常用數(shù)據(jù)結(jié)構(gòu)第章：緒論第章：線性表第章：棧和隊列第章：串第章：數(shù)組和廣義表第章：樹和二叉樹內(nèi)容安排(2)第章：圖 常用查找和排序算法

4、第章：動態(tài)存儲管理第章：查找第章：內(nèi)部排序第章：外部排序第章：文件學(xué)時安排教學(xué)內(nèi)容講課上機(jī)時間小計第1章 緒論44第3章 線性表8412第4章 棧與隊列44第5章 字符串33第6章 數(shù)組、廣義表和遞歸算法448第7章 樹與二叉樹10414第8章 圖88第9章 查找8412第10章 內(nèi)部排序7411第11章 文件44總 計602080上機(jī)實驗內(nèi)容上機(jī)實驗內(nèi)容 實驗1：順序表和鏈表的應(yīng)用 （4學(xué)時） 實驗2：堆棧和隊列、串和數(shù)組的應(yīng)用 （4學(xué)時） 實驗3：樹和圖的應(yīng)用 （4學(xué)時） 實驗4：查找的應(yīng)用 （4學(xué)時） 實驗5：排序的應(yīng)用 （4學(xué)時） 上機(jī)軟件Visual C+ 6.0 第一章 緒論 第一

5、章 緒論 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型 1.4 算法及其分析 本章教學(xué)要求： (1) 了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù)語. (2) 了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法. (3) 掌握算法的定義及特性，算法設(shè)計的要求. 重點: (1) 了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù)語。 (2) 抽象數(shù)據(jù)類型表示法、類C語言語法。 (3) 算法的特性，算法設(shè)計要求，算法分析。 難點: (1) 數(shù)據(jù)元素間的四種結(jié)構(gòu)關(guān)系。 (2) 抽象數(shù)據(jù)類型表示法。 (3) 算法分析。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)一、計算機(jī)解決問題 步驟程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)(1)、分析階段-從問題抽象出

6、模型(分析問題,建模)(2)、設(shè)計階段-依模型找出解法(重點是數(shù)據(jù)結(jié)構(gòu)的設(shè)計和算法的設(shè)計)(3)、編碼階段依設(shè)計要求，用適當(dāng)?shù)某绦蛘Z言編寫出可執(zhí)行的程序(4)、測試與維護(hù)-發(fā)現(xiàn)和排除前幾個階段的錯誤1.1 什么是數(shù)據(jù)結(jié)構(gòu)二、 數(shù)值問題與非數(shù)值問題1）數(shù)值問題1.1 什么是數(shù)據(jù)結(jié)構(gòu)主要特點是其數(shù)學(xué)模型可以用數(shù)學(xué)方程來表示。 2）非數(shù)值問題主要特點是其數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是表、樹或圖之類的數(shù)據(jù)結(jié)構(gòu)。 非數(shù)值問題的一些示例 學(xué)號 姓名 性別 出生日期 籍貫 入學(xué)成績 所在班級 00201 楊潤生 男 82/06/01 廣州 561 00計算機(jī)200102 石磊 男 83/12/21 汕頭 51

7、2 00計算機(jī)100202 李梅 女 83/02/23 陽江 532 00計算機(jī)200301 馬耀先 男 82/07/12 廣州 509 00計算機(jī)3 已知某年級學(xué)生情況 , 要求分班按入學(xué)成績排列順序。 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 在這類文檔管理的數(shù)學(xué)模型中, 計算機(jī)處理的對象之間通常存在著一種最簡單的線性關(guān)系 , 這類數(shù)學(xué)模型稱為線性模型 -表，線性的數(shù)據(jù)結(jié)構(gòu)例1.1 圖書館信息管理系統(tǒng)書目表按書名按作者名按分類號索引表登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片例1.2 1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.1 什么是數(shù)據(jù)結(jié)構(gòu) 迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。

8、計算機(jī)處理的這類對象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹” 入口 出口例1.3 人機(jī)對奕樹.例1.4 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 多叉路口交通燈問題CEBDAC和E是單行線,其他是雙行線。要求：設(shè)計交通信號燈管理(“圖”結(jié)構(gòu))1.1 什么是數(shù)據(jù)結(jié)構(gòu)例1.5 多叉路口交通燈問題CEDABABACADBABCBDDADBDCEAEBECED 1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.1 什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究問題： 非數(shù)值型數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲，如何處理。數(shù)據(jù)結(jié)構(gòu) 討論描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機(jī)中的表示和實現(xiàn)。 12

9、基本概念和術(shù)語一、數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 1、數(shù)據(jù)：所有能被輸入到計算機(jī)中，且被計算機(jī)處理的符號的集合 ； 是計算機(jī)操作的對象的總稱； 是計算機(jī)處理的信息的某種特定的符號表示形式 。 2、數(shù)據(jù)元素：數(shù)據(jù)中的一個“個體”，也稱 “數(shù)據(jù)記錄” 。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位 。 3、數(shù)據(jù)項: 相當(dāng)于記錄的“域”, 是數(shù)據(jù)的不可分割的最小單位。是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位 。 (原子項、組合項) 1.2 基本概念和術(shù)語舉例：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項及其關(guān)系12 基本概念和術(shù)語4、數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合. 5、數(shù)據(jù)處理：指對數(shù)據(jù)進(jìn)行檢索、插入、刪除、合并、拆分、排序、統(tǒng)計和轉(zhuǎn)換等的操作。6、數(shù)據(jù)結(jié)構(gòu)：是

10、相互間存在關(guān)系的數(shù)據(jù)元素集合。例如：一個含12位數(shù)的十進(jìn)制數(shù)可以用三個4位的十進(jìn)制數(shù)表示 3214,6587,9345 記 a1(3214),a2(6587),a3(9345) 在a1、a2和a3 之間存在“次序”關(guān)系 a1,a2、a2,a3 12 基本概念和術(shù)語二、數(shù)據(jù)結(jié)構(gòu)的三方面 1） 數(shù)據(jù)的邏輯結(jié)構(gòu) 2） 數(shù)據(jù)的存儲結(jié)構(gòu) 3） 數(shù)據(jù)的運(yùn)算 數(shù)據(jù)的邏輯結(jié)構(gòu)： 是數(shù)據(jù)元素之間的邏輯關(guān)系。形式化描述： Data_structure=(D,S) D數(shù)據(jù)元素的有限集合；SD上關(guān)系的有限集合。12 基本概念和術(shù)語 數(shù)據(jù)的存儲結(jié)構(gòu) (物理結(jié)構(gòu))： 數(shù)據(jù)的各元素及其之間的關(guān)系在計算機(jī)中的存儲表示。 數(shù)據(jù)

11、運(yùn)算： 定義于邏輯結(jié)構(gòu)、實現(xiàn)于存儲結(jié)構(gòu)，對數(shù)據(jù)的檢索、插入、刪除、更新、排序等操作。 1） 線性結(jié)構(gòu) 2） 樹形結(jié)構(gòu) 3） 圖結(jié)構(gòu) 4） 集合 某班學(xué)生基本情況登記表，記錄了每個學(xué)生的學(xué)號、姓名 、專業(yè)、政治 面貌 ，表中的記錄是按學(xué)生的學(xué)號順序排列的。 學(xué)號 姓名 專業(yè) 政治面藐 001 王洪 計算機(jī) 黨員 002 孫文 計算機(jī) 團(tuán)員 003 謝軍 計算機(jī) 團(tuán)員 004 李輝 計算機(jī) 團(tuán)員 005 沈祥 計算機(jī) 黨員 006 余斌 計算機(jī) 團(tuán)員 007 鞏力 計算機(jī) 團(tuán)員 008 孔輝 計算機(jī) 團(tuán)員學(xué)生基本情況登記表的圖示 001003002004006005008007學(xué)生間學(xué)號順序關(guān)系是

12、一種線性結(jié)構(gòu)關(guān)系例1.6(1)常用的數(shù)據(jù)(邏輯)結(jié)構(gòu) 線性結(jié)構(gòu)：元素之間是一對一的關(guān)系。 12 基本概念和術(shù)語 家族的族譜 假設(shè)某家族有10個成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關(guān)系可以用如右圖表示。12 基本概念和術(shù)語例1.7 樹形結(jié)構(gòu)：元素之間是一對多的關(guān)系。 JIACBDHGFE 圖結(jié)構(gòu): 元素之間是多對多的關(guān)系。 如交通網(wǎng)、計算機(jī)網(wǎng)絡(luò)等。 集合: 元素間為松散的關(guān)系。例如： 12 基本概念和術(shù)語數(shù)據(jù)(邏輯)結(jié)構(gòu)的二種常用表示方法 圖示表示 圖示表示是由頂點和邊構(gòu)成的圖，其中頂點表示數(shù)據(jù) ，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系； 0010030020040060

13、05008007例如：學(xué)生基本情況表的圖示表示JIACBDHGFE再如：家族樹的圖示表示12 基本概念和術(shù)語例如：學(xué)生基本情況表的二元組表示（D，S） 二元組表示 二元組表示是用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)， 其中 D 是數(shù)據(jù)元素集合，S 是 D 上關(guān)系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 再如：家族樹的二元組表示（D，S） D = A，B，C，D，E，F(xiàn)，G，H，I，J S = R R = A,B, 12 基本概念和術(shù)語JIACBDHGFE 00100300200400600500800712 基本概念和術(shù)語(2)數(shù)據(jù)的存

14、儲(物理)結(jié)構(gòu)-邏輯結(jié)構(gòu)在存儲器中的映象 數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素 。 例如： (321)10 (101000001)2 A (001000001)2 關(guān)系的映象方法：有以下 4種 順序結(jié)構(gòu) 鏈接結(jié)構(gòu) 索引結(jié)構(gòu) 散列結(jié)構(gòu) 鏈接結(jié)構(gòu)： 使用附加的 指針表示元素間的關(guān)系。 順序結(jié)構(gòu)： 以計算機(jī)存儲器中存儲單元之間的相鄰關(guān)系表示元素間的相鄰關(guān)系。xyz 特點：使用連續(xù)存儲空間，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。 x y z順序結(jié)構(gòu)與鏈接結(jié)構(gòu)的比較： 可以從空間利用率和運(yùn)算兩方面進(jìn)行比較。12 基本概念和術(shù)語12 基本概念和術(shù)語 索引結(jié)構(gòu)： 使用索引表和基本表實現(xiàn)

15、數(shù)據(jù)結(jié)構(gòu)。 散列結(jié)構(gòu)： 根據(jù)結(jié)點的值確定結(jié)點存儲地址。 說明： 4種存儲方法可結(jié)合使用。12 基本概念和術(shù)語 三、數(shù)據(jù)類型和抽象數(shù)據(jù)類型的概念 數(shù)據(jù)類型（Data Type） 在高級語言中指數(shù)據(jù)的一個值的集合及其上可進(jìn)行的一組操作的總稱。 例:C語言中 提供int基本數(shù)據(jù)類型，可以進(jìn)行+，*，/，%等操作 按值的類型劃分： 原子類型 結(jié)構(gòu)類型12 基本概念和術(shù)語 抽象數(shù)據(jù)類型（Abstract Data Type） 是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作抽象數(shù)據(jù)類型和數(shù)據(jù)類型的區(qū)別 數(shù)據(jù)類型注重運(yùn)算，忽略了數(shù)據(jù)元素（值）之間的關(guān)系 抽象數(shù)據(jù)類型注重數(shù)據(jù)元素的關(guān)系 抽象的是數(shù)據(jù)元素本身的值

16、的類型14 算法與算法分析 1.3 抽象數(shù)據(jù)類型13 抽象數(shù)據(jù)類型一、抽象數(shù)據(jù)類型的定義(ADTAbstract Data Type)： ADT是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 例如： 矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值） 構(gòu)成一個矩陣的抽象數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作 = 抽象數(shù)據(jù)類型 二、抽象數(shù)據(jù)類型的描述方法 抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象和數(shù)

17、據(jù)關(guān)系用偽碼描述 基本操作名（參數(shù)表） 初始條件：（初始條件描述） 操作結(jié)果：（操作結(jié)果描述）13 抽象數(shù)據(jù)類型名稱線性表數(shù)據(jù)對象D=ai| aiElemSet,i=1,2,.,n,n=0任意數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R1=| ai-1,ai D,i=2,.,n除第一個和最后一個外，每個元素有唯一的直接前趨和唯一的直接后繼基本操作ListInsert(&L,i,e)ListDelete(&L,i,e)L為線性表，i為位置，e為數(shù)據(jù)元素。例：線性表抽象數(shù)據(jù)類型的表示13 抽象數(shù)據(jù)類型13 抽象數(shù)據(jù)類型三、類C語言語法(1)1、預(yù)定義常量和類型#define TRUE 1#define FALSE 0

18、#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; /Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼。2、數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)typedef ElemType first;3、基本操作的算法函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）/算法說明語句序列/函數(shù)名 13 抽象數(shù)據(jù)類型類C語言語法(2)4、賦值語句簡單賦值：變量名=表達(dá)式； 串聯(lián)賦值：變量名1=變量名2=.=變量名k=表達(dá)式； 成組賦值: （變量名1，.,變量名k）=（表達(dá)式1，.,表達(dá)式k);結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1，

19、.，值k);變量名=表達(dá)式；變量名起始下標(biāo).終止下標(biāo)=變量名起始下標(biāo).終止下標(biāo)； 交換賦值：變量名變量名；條件賦值：變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F13 抽象數(shù)據(jù)類型類C語言語法(3)5、選擇語句1、if（表達(dá)式） 語句；2、if（表達(dá)式） 語句；else 語句；3、switch(表達(dá)式） case 值1：語句序列1；break; . case 值n：語句序列n；break; default:語句序列n+1；break; 4、switchcase 條件1：語句序列1；break;.case 條件n：語句序列n；break; default:語句序列n+1；break; 類C語言語法(4)

20、13 抽象數(shù)據(jù)類型6、循環(huán)語句for（賦初值表達(dá)式；條件；修改表達(dá)式序列）語句；while（條件）語句；do 語句序列 while（條件）；7、結(jié)束語句return 表達(dá)式；return; /函數(shù)結(jié)束語句break; /case結(jié)束語句exit(異常代碼); /異常結(jié)束語句8、輸入和輸出語句scanf（格式串，&變量1，.,&變量n）；printf(格式串,表達(dá)式1,表達(dá)式n);9、注釋/文字序列10、基本函數(shù)max（表達(dá)式1，.，表達(dá)式n）min,abs,floor,ceil,eof,eoln 11、邏輯運(yùn)算&與運(yùn)算；|或運(yùn)算ADT List /線性表的類C表示數(shù)據(jù)對象: D=ai| ai(

21、-ElemSet,i=1,2,.,n,n=0 數(shù)據(jù)關(guān)系: R1=| ai-1,ai(- D,i=2,.,n 基本操作：InitList(&L)；DestroyList(&L)；ListInsert(&L,i,e)；ListDelete(&L,i,&e)；ADT ListListInsert(List &L,int i,ElemType e)if (iL.length+) return ERROR;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p;*q=e;+L.length;return OK;13 抽象數(shù)據(jù)類型14 算法與算

22、法分析 1.4 算法及其分析一、算法的概念 算法是描述求解問題的操作序列的有窮規(guī)則集合。 算法的5個基本特征：1）輸入：0個或多個輸入；2）輸出：1個或多個輸出；3）有窮性：算法必須在有限步內(nèi)結(jié)束；4）確定性：組成算法的操作必須清晰無二義性。5）可行性：組成算法的操作必須能夠在計算機(jī)上實現(xiàn)。 求兩個正整數(shù) m，n 中的大者M(jìn)AX的算法。 （1）若 m n 則 max=m （2）若 m = n 則 max=n 例1.814 算法及其分析 算法的描述流程圖自然語言偽代碼高級語言14 算法及其分析例1.7從n個整數(shù)中查找最大數(shù)算法的描述描述方法一 ： 使用流程圖開始輸入n個整數(shù)a1anxa1,i2i

23、xii+1輸出x結(jié)束NYYN14 算法及其分析描述方法二：使用自然語言給n個元素a1an輸入數(shù)值把第一個元素a1值賦給用于保存最大值元素的變量x把2賦給表示下標(biāo)的變量i如果ix，則把a(bǔ)i賦給x，否則不改變x的值使下標(biāo)i增加1轉(zhuǎn)向第(4)步繼續(xù)執(zhí)行14 算法及其分析描述方法三：使用偽語言-類C語言 DataType Max(int n) /設(shè)n個數(shù)已存于數(shù)組A x=A0; i=1; while (ix) x=Ai; i+; return x; 14 算法及其分析描述方法四：使用高級語言-C語言#define N 10 #include void Max() int i,x,AN; for (i=

24、0;iN;i+) scanf(“%d”,&ai); x=A0; i=1; while (ix) x=Ai; i+; printf(“max=%dn”,x); 14 算法及其分析二、算法的設(shè)計14 算法及其分析“自頂向下,逐步求精”，使算法層次化、模塊化。三個階段：數(shù)學(xué)模型非形式化算法抽象數(shù)據(jù)類型偽語言算法數(shù)據(jù)類型高級語言源程序算法設(shè)計的要求14 算法及其分析1正確性2. 可讀性 3健壯性 4高效率與低存儲量需求 int sign(int x)int y; if(x 0) y = 1; else if(x = 0) y = 0; else y = -1; return y;第一個層次程序不包含語

25、法錯誤int sign(int x)int y; if(x 1) y = 1; else if(x = 0) y = 0; else y = -1; return y;第二個層次輸入100 輸出1輸入0 輸出0輸入100 輸出1int sign(int x)int y; if(x = 1) y = 1; else if(x = 0) y = 0; else y = -1;return y;第三個層次輸入100 輸出1輸入1 輸出1輸入0 輸出0輸入-1 輸出-1輸入-100 輸出-1int sign(int x)int y; if(x 0) y = 1; else if(x = 0) y =

26、0; else y = -1; if(x =0 x1234) y= 0; return y;第四個層次所有可能的輸入14 算法及其分析三、算法的分析 好算法的特性： 正確性、可讀性、健壯性、高效率和低存儲量等。 1、算法效率的度量-算法時間復(fù)雜度1) 兩種衡量算法效率的方法: 事后統(tǒng)計方法 :例如Visual C+ 中的Profiler 缺點：不利于較大范圍內(nèi)的算法比較。 （異地，異時，異境） 事前分析估算方法：評估方法 可克服事后統(tǒng)計方法的缺點。 14 算法及其分析程序在計算機(jī)上運(yùn)行所需時間的影響因素算法本身選用的策略問題的規(guī)模：輸入量的數(shù)目規(guī)模越大，消耗時間越多書寫程序的語言語言越高級，消

27、耗時間越多編譯產(chǎn)生的機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令的速度為便于比較算法本身的優(yōu)劣，應(yīng)排除其它影響算法效率的因素。 14 算法及其分析例1.8計算下列算法的執(zhí)行時間(包含的簡單操作個數(shù))int sum(int A,int n) int s=0; for (i=0;in;i+) s+=Ai; return s;假設(shè)以語句為單位進(jìn)行統(tǒng)計：T(n)=1+1+n+1+n+n+n+1=4n+4 14 算法及其分析 s=0; i=0;Loop: if(in) s+=Ai; i+; goto loop; return s;一個特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），即它是問題規(guī)模的

28、函數(shù)。 算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作） 從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時間的度量。 14 算法及其分析例1.8原操作：加法操作的次數(shù)int sum(int A,int n) int s=0; for (i=0;in;i+) s+=Ai; return s;T(n) = n 14 算法及其分析 多數(shù)情況下只要求出最深層次循環(huán)語句中原操作量級2) 算法時間復(fù)雜度的估算 - 大“O”記號算法的漸進(jìn)時間復(fù)雜度，簡稱算法時間復(fù)雜度記作： T(n) = O(f(n) 表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率

29、與f(n) 的增長率相同。-算法執(zhí)行時間的數(shù)量級 14 算法及其分析例1.9 兩個n 階矩陣相乘的算法 矩陣相乘的基本運(yùn)算：乘法、 加法；for ( i = 1; i=n; i+ ) for (j = 1; j=n; j+ ) c i j = 0 ; for (k = 1; k= n; k+ ) c i j += a i k * b k j ; 乘法 加法執(zhí)行次數(shù)均為 n3 O（n3） 稱為矩陣相乘算法時間復(fù)雜度；O（n3）表示矩陣相乘算法執(zhí)行時間與n3成正比, 即O（n3）與n3 同一數(shù)量級； 14 算法及其分析例1.10選擇排序void sele_sort(int A,int n) for

30、 (i=0;in-1;i+) index=i; for (j=i+1;jn;j+) if (AjAindex) index=j; if (index!=i) temp=Aindex; Aindex=Ai; Ai=temp; T(n)=? 請思考! 14 算法及其分析原操作：比較(n-1)+(n-2)+1=n(n-1)/2算法時間復(fù)雜度：O(n2) 常見算法時間復(fù)雜度表示及增長速度排序：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)說明：logn指log2n常用公式： n n n 1=n , i=n(n+1)/2 , i2=n(n+1)(2n+1)/6 1

31、 1 1 14 算法及其分析各種數(shù)量級的T(n) 14 算法及其分析算法時間復(fù)雜度的表示： 算法執(zhí)行時間的數(shù)量級數(shù)量級的含義： 忽略這個數(shù)量級的系數(shù) 低于這個數(shù)量級的其他項問題： T(n) = 5n2+100n 什么情況下會考慮系數(shù)和低數(shù)量級項的因素？ 14 算法及其分析 最好、最壞、平均時間復(fù)雜度例1.11對一維數(shù)組進(jìn)行順序查找。int search(int a,int n,int key) for (i=0;in;i+) if (ai= =key) return i; return -1;最好情況：?最壞情況：?平均情況：? 14 算法及其分析算法執(zhí)行的時間: 和數(shù)據(jù)集的具體值和值的分布有關(guān)系 概念：最好時間復(fù)雜度：指算法對所有可能的輸入集的最小執(zhí)行時間最壞時間復(fù)雜度：指算法對所有可能的輸入集的最大執(zhí)行時間平均時間復(fù)雜度：指算法對所有可能的輸入集的執(zhí)行時間的數(shù) 學(xué)期望值。 14 算法及其分析 14 算法及其分析例1.122 算法空間復(fù)雜度 -算法存儲空間的度量 用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。 S（n）= O(g(n)