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

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

2、儲形式以及實現(xiàn)各種操作的算法。掌握在上述各種數(shù)據(jù)結(jié)構(gòu)上經(jīng)常實現(xiàn)的查找和排序的基本方法。能對工作中遇到的一些算法的時間復雜性和空間復雜性進行分析。能根據(jù)用戶的要求及系統(tǒng)提供的數(shù)據(jù)，設計或選擇合適的數(shù)據(jù)結(jié)構(gòu)并能編寫正確的算法解決實際問題。 教材及參考書(1) 教材嚴蔚敏，吳偉民編著：數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學出版社，2004.11 嚴蔚敏，吳偉民，米寧編著：數(shù)據(jù)結(jié)構(gòu)題集（C語言版） 清華大學出版社，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。學時分配及考核方式學時分配：授課 60學時 上機實驗 20學時課程成績： 平時成績 期末考試成績 平時成績 20 書面作業(yè)、上機練習 期末考試 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)部排序第章：外部排序第章：文件學時安排教學內(nèi)容講課上機時間小計第1章 緒論44第3章 線性表8412第4章 棧與隊列44第5章 字符串33第6章 數(shù)組、廣義表和遞歸算法448第7章 樹與二叉樹10414第8章 圖88第9章 查找8412第10章 內(nèi)部排序7411第11章 文件44總 計602080上機實驗內(nèi)容上機實驗內(nèi)容 實驗1：順序表和鏈表的應用 （4學時） 實驗2：堆棧和隊列、串和數(shù)組的應用 （4學時） 實驗3：樹和圖的應用 （4學時） 實驗4：查找的應用 （4學時） 實驗5：排序的應用 （4學時） 上機軟件Visual C+ 6.0 第一章 緒論 第一

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

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

7、2 00計算機100202 李梅 女 83/02/23 陽江 532 00計算機200301 馬耀先 男 82/07/12 廣州 509 00計算機3 已知某年級學生情況 , 要求分班按入學成績排列順序。 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 在這類文檔管理的數(shù)學模型中, 計算機處理的對象之間通常存在著一種最簡單的線性關(guān)系 , 這類數(shù)學模型稱為線性模型 -表，線性的數(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、計算機處理的這類對象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹” 入口 出口例1.3 人機對奕樹.例1.4 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 多叉路口交通燈問題CEBDAC和E是單行線,其他是雙行線。要求：設計交通信號燈管理(“圖”結(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ù)學模型及其上的操作在計算機中的表示和實現(xiàn)。 12

9、基本概念和術(shù)語一、數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 1、數(shù)據(jù)：所有能被輸入到計算機中，且被計算機處理的符號的集合 ； 是計算機操作的對象的總稱； 是計算機處理的信息的某種特定的符號表示形式 。 2、數(shù)據(jù)元素：數(shù)據(jù)中的一個“個體”，也稱 “數(shù)據(jù)記錄” 。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位 。 3、數(shù)據(jù)項: 相當于記錄的“域”, 是數(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ù)進行檢索、插入、刪除、合并、拆分、排序、統(tǒng)計和轉(zhuǎn)換等的操作。6、數(shù)據(jù)結(jié)構(gòu)：是

10、相互間存在關(guān)系的數(shù)據(jù)元素集合。例如：一個含12位數(shù)的十進制數(shù)可以用三個4位的十進制數(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ù)的運算 數(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)系在計算機中的存儲表示。 數(shù)據(jù)

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

12、一種線性結(jié)構(gòu)關(guān)系例1.6(1)常用的數(shù)據(jù)(邏輯)結(jié)構(gòu) 線性結(jié)構(gòu)：元素之間是一對一的關(guān)系。 12 基本概念和術(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)、計算機網(wǎng)絡等。 集合: 元素間為松散的關(guān)系。例如： 12 基本概念和術(shù)語數(shù)據(jù)(邏輯)結(jié)構(gòu)的二種常用表示方法 圖示表示 圖示表示是由頂點和邊構(gòu)成的圖，其中頂點表示數(shù)據(jù) ，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系； 0010030020040060

13、05008007例如：學生基本情況表的圖示表示JIACBDHGFE再如：家族樹的圖示表示12 基本概念和術(shù)語例如：學生基本情況表的二元組表示（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ù)元素的映象方法：用二進制位(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)： 以計算機存儲器中存儲單元之間的相鄰關(guān)系表示元素間的相鄰關(guān)系。xyz 特點：使用連續(xù)存儲空間，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。 x y z順序結(jié)構(gòu)與鏈接結(jié)構(gòu)的比較： 可以從空間利用率和運算兩方面進行比較。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ù)的一個值的集合及其上可進行的一組操作的總稱。 例:C語言中 提供int基本數(shù)據(jù)類型，可以進行+，*，/，%等操作 按值的類型劃分： 原子類型 結(jié)構(gòu)類型12 基本概念和術(shù)語 抽象數(shù)據(jù)類型（Abstract Data Type） 是指一個數(shù)學模型以及定義在該模型上的一組操作抽象數(shù)據(jù)類型和數(shù)據(jù)類型的區(qū)別 數(shù)據(jù)類型注重運算，忽略了數(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ù)學模型以及定義在此數(shù)學模型上的一組操作。 例如： 矩陣 +（求轉(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、預定義常量和類型#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、賦值語句簡單賦值：變量名=表達式； 串聯(lián)賦值：變量名1=變量名2=.=變量名k=表達式； 成組賦值: （變量名1，.,變量名k）=（表達式1，.,表達式k);結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1，

19、.，值k);變量名=表達式；變量名起始下標.終止下標=變量名起始下標.終止下標； 交換賦值：變量名變量名；條件賦值：變量名=條件表達式？表達式T：表達式F13 抽象數(shù)據(jù)類型類C語言語法(3)5、選擇語句1、if（表達式） 語句；2、if（表達式） 語句；else 語句；3、switch(表達式） 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（賦初值表達式；條件；修改表達式序列）語句；while（條件）語句；do 語句序列 while（條件）；7、結(jié)束語句return 表達式；return; /函數(shù)結(jié)束語句break; /case結(jié)束語句exit(異常代碼); /異常結(jié)束語句8、輸入和輸出語句scanf（格式串，&變量1，.,&變量n）；printf(格式串,表達式1,表達式n);9、注釋/文字序列10、基本函數(shù)max（表達式1，.，表達式n）min,abs,floor,ceil,eof,eoln 11、邏輯運算&與運算；|或運算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）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)。 求兩個正整數(shù) m，n 中的大者MAX的算法。 （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賦給表示下標的變量i如果ix，則把ai賦給x，否則不改變x的值使下標i增加1轉(zhuǎn)向第(4)步繼續(xù)執(zhí)行14 算法及其分析描述方法三：使用偽語言-類C語言 DataType Max(int n) /設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 算法及其分析二、算法的設計14 算法及其分析“自頂向下,逐步求精”，使算法層次化、模塊化。三個階段：數(shù)學模型非形式化算法抽象數(shù)據(jù)類型偽語言算法數(shù)據(jù)類型高級語言源程序算法設計的要求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、算法效率的度量-算法時間復雜度1) 兩種衡量算法效率的方法: 事后統(tǒng)計方法 :例如Visual C+ 中的Profiler 缺點：不利于較大范圍內(nèi)的算法比較。 （異地，異時，異境） 事前分析估算方法：評估方法 可克服事后統(tǒng)計方法的缺點。 14 算法及其分析程序在計算機上運行所需時間的影響因素算法本身選用的策略問題的規(guī)模：輸入量的數(shù)目規(guī)模越大，消耗時間越多書寫程序的語言語言越高級，消

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

28、函數(shù)。 算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作） 從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的度量。 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) 算法時間復雜度的估算 - 大“O”記號算法的漸進時間復雜度，簡稱算法時間復雜度記作： T(n) = O(f(n) 表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率

29、與f(n) 的增長率相同。-算法執(zhí)行時間的數(shù)量級 14 算法及其分析例1.9 兩個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） 稱為矩陣相乘算法時間復雜度；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算法時間復雜度：O(n2) 常見算法時間復雜度表示及增長速度排序：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 算法及其分析算法時間復雜度的表示： 算法執(zhí)行時間的數(shù)量級數(shù)量級的含義： 忽略這個數(shù)量級的系數(shù) 低于這個數(shù)量級的其他項問題： T(n) = 5n2+100n 什么情況下會考慮系數(shù)和低數(shù)量級項的因素？ 14 算法及其分析 最好、最壞、平均時間復雜度例1.11對一維數(shù)組進行順序查找。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)系 概念：最好時間復雜度：指算法對所有可能的輸入集的最小執(zhí)行時間最壞時間復雜度：指算法對所有可能的輸入集的最大執(zhí)行時間平均時間復雜度：指算法對所有可能的輸入集的執(zhí)行時間的數(shù) 學期望值。 14 算法及其分析 14 算法及其分析例1.122 算法空間復雜度 -算法存儲空間的度量 用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。 S（n）= O(g(n)