數(shù)據(jù)結(jié)構(gòu)一章緒論ppt課件

1、第一章第一章 緒論緒論11 根本術(shù)語根本術(shù)語12 數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容121 數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造122 數(shù)據(jù)的存儲構(gòu)造數(shù)據(jù)的存儲構(gòu)造123 數(shù)據(jù)的運算數(shù)據(jù)的運算13 算法算法131 算法的概念及特性算法的概念及特性132 算法的描畫算法的描畫133 算法的評價算法的評價14 學(xué)習(xí)數(shù)據(jù)構(gòu)造的意義和目的學(xué)習(xí)數(shù)據(jù)構(gòu)造的意義和目的 11 根本術(shù)語 數(shù)據(jù)Data是人們商定的符號，用它來表示客觀事物及其活動，是信息的載體。數(shù)據(jù)是計算機程序加工處置的對象。 數(shù)據(jù)元素Data Element是數(shù)據(jù)的根本單位，在計算機程序中通常作為一個整體進展思索和處置，在不同的情況下

2、，又可以稱為元素、結(jié)點、頂點或記錄。數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的。 數(shù)據(jù)項Data Item是構(gòu)成數(shù)據(jù)元素不可分割的具有獨立含義的最小標(biāo)識單位。假設(shè)數(shù)據(jù)元素可再分，那么數(shù)據(jù)元素是由假設(shè)干個數(shù)據(jù)項組成；如數(shù)據(jù)元素不可再分，數(shù)據(jù)元素和數(shù)據(jù)項是同一概念，如整型數(shù)據(jù)就是不可再分的。 數(shù)據(jù)類型Data Type是一個值的集合和定義在這個值集上一組操作的總稱。按值的不同特性，高級程序設(shè)計言語中的數(shù)據(jù)類型可分為原子類型和構(gòu)造類型兩類。 第一章第一章 緒論緒論12 數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造的定義及研討的內(nèi)容數(shù)據(jù)構(gòu)造Data Structure：按照某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，用一定的存儲方式存儲在計算

3、機的存儲器中，并在這些數(shù)據(jù)上定義一個運算的集合，就稱為一個數(shù)據(jù)構(gòu)造Data Structure。數(shù)據(jù)構(gòu)造重點研討的內(nèi)容：1數(shù)據(jù)的邏輯構(gòu)造：即數(shù)據(jù)之間的邏輯關(guān)系。2數(shù)據(jù)的存儲構(gòu)造：即數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系在計算機存儲器中的表示。3數(shù)據(jù)的運算：即對數(shù)據(jù)施加的各種操作。 數(shù)據(jù)的邏輯構(gòu)造 數(shù)據(jù)的邏輯構(gòu)造Logical Structure：的是數(shù)據(jù)元素之間的邏輯關(guān)系。它是人們根據(jù)實踐問題的需求和問題本身所含數(shù)據(jù)之間的內(nèi)在聯(lián)絡(luò)而籠統(tǒng)出來的數(shù)學(xué)模型，與如何利用計算機存儲和處置無關(guān)，所以被稱為數(shù)據(jù)的邏輯構(gòu)造。由于數(shù)據(jù)的邏輯構(gòu)造是數(shù)學(xué)模型，可以借助數(shù)學(xué)方法來表示，詳細的可以用離散數(shù)學(xué)中關(guān)系代數(shù)的二元組表示：Dat

4、a_Structure =D，S通常取S中的一個關(guān)系rj來進展討論，rj可以表示為數(shù)據(jù)元素的序偶的集合。假設(shè)集合中有序偶，表示數(shù)據(jù)元素di和dj之間有rj這種關(guān)系。用二元組表示的數(shù)據(jù)的邏輯構(gòu)造，有如下的常用術(shù)語1前趨結(jié)點、后繼結(jié)點、相鄰結(jié)點2開場結(jié)點、終端結(jié)點、內(nèi)部結(jié)點數(shù)據(jù)的邏輯構(gòu)造還可以利用更籠統(tǒng)的圖形表示 v數(shù)據(jù)的邏輯構(gòu)造有兩大類：數(shù)據(jù)的邏輯構(gòu)造有兩大類：v1線性構(gòu)造：經(jīng)典的線性構(gòu)造是線性表。線性構(gòu)造：經(jīng)典的線性構(gòu)造是線性表。v 線性構(gòu)造的邏輯特征是：有且僅有一個開場結(jié)點和一個終端結(jié)點線性構(gòu)造的邏輯特征是：有且僅有一個開場結(jié)點和一個終端結(jié)點，其他的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點和一個后繼結(jié)

5、點，也就是，其他的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點和一個后繼結(jié)點，也就是說構(gòu)造中的數(shù)據(jù)元素間存在著一對一的相互關(guān)系。說構(gòu)造中的數(shù)據(jù)元素間存在著一對一的相互關(guān)系。v2非線性構(gòu)造：經(jīng)典的非線性構(gòu)造有樹形構(gòu)造和圖形構(gòu)造。非線性構(gòu)造：經(jīng)典的非線性構(gòu)造有樹形構(gòu)造和圖形構(gòu)造。v 樹形構(gòu)造的邏輯特征是：有且僅有一個開場結(jié)點，可有假設(shè)干樹形構(gòu)造的邏輯特征是：有且僅有一個開場結(jié)點，可有假設(shè)干個終端結(jié)點，其他的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點，可以有假設(shè)個終端結(jié)點，其他的內(nèi)部結(jié)點都有且僅有一個前趨結(jié)點，可以有假設(shè)干個后繼結(jié)點，也就是說構(gòu)造中的數(shù)據(jù)元素間存在著一對多的層次關(guān)干個后繼結(jié)點，也就是說構(gòu)造中的數(shù)據(jù)元素間存在著

6、一對多的層次關(guān)系。系。v 圖形構(gòu)造的邏輯特征是：可有假設(shè)干個開場結(jié)點和終端結(jié)點，圖形構(gòu)造的邏輯特征是：可有假設(shè)干個開場結(jié)點和終端結(jié)點，其他的內(nèi)部結(jié)點可以有假設(shè)干個前趨結(jié)點和假設(shè)干個后繼結(jié)點，也就其他的內(nèi)部結(jié)點可以有假設(shè)干個前趨結(jié)點和假設(shè)干個后繼結(jié)點，也就是說構(gòu)造中的數(shù)據(jù)元素間存在著多對多的網(wǎng)狀關(guān)系。是說構(gòu)造中的數(shù)據(jù)元素間存在著多對多的網(wǎng)狀關(guān)系。表1.1 某校圍棋社團學(xué)生簡表學(xué)號姓名性別出生日期職務(wù)01黃家正男1982-08-05團長02趙 芳女1981-08-15組長03王 明女1983-04-01組長04王 紅女1982-06-28組員05張小才男1984-03-17組員06馬立偉男1983

7、-10-12組員07孫 剛男1982-07-05組員08劉 永男1982-12-09組員 例例1.1 在表在表1.1中，八名學(xué)生按學(xué)號從小到大陳中，八名學(xué)生按學(xué)號從小到大陳列，構(gòu)成一個線性構(gòu)造。假設(shè)表示這種邏輯構(gòu)列，構(gòu)成一個線性構(gòu)造。假設(shè)表示這種邏輯構(gòu)造的關(guān)系為造的關(guān)系為r1，那么，那么r1可以定義為學(xué)生按學(xué)號可以定義為學(xué)生按學(xué)號順序遞增陳列的關(guān)系，該線性構(gòu)造的邏輯構(gòu)造順序遞增陳列的關(guān)系，該線性構(gòu)造的邏輯構(gòu)造可用二元組表示為：可用二元組表示為：L =D，S，r1SD =01，02，03，04，05，06，07，08 r 1 =， ，圖1.1 線性構(gòu)造的圖示 例例1.2 在表在表1.1中，學(xué)生之

8、間還存在著指點與被指中，學(xué)生之間還存在著指點與被指點關(guān)系，其中點關(guān)系，其中01號學(xué)生為團長，直接指點號學(xué)生為團長，直接指點02和和03號學(xué)生，他們分別是組長，號學(xué)生，他們分別是組長，02號學(xué)生直接指點號學(xué)生直接指點04和和05號學(xué)生，號學(xué)生，03號學(xué)生直接指點號學(xué)生直接指點06、07和和08號學(xué)生號學(xué)生，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為r2，那么，那么r2可以可以定義為學(xué)生之間的指點與被指點關(guān)系，該數(shù)據(jù)構(gòu)造定義為學(xué)生之間的指點與被指點關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：的邏輯構(gòu)造可用二元組表示為：T =D，S，r2SD =01，02，03，04，05，06，0

9、7，08r2 =， ， 0 10 20 30 40 50 60 70 8圖1.2 樹形構(gòu)造的圖示例例1.3 在表在表1.1中，學(xué)生之間還有好友關(guān)系，如中，學(xué)生之間還有好友關(guān)系，如01和和02、03、05號是好友，號是好友，02和和04號是好友，號是好友，03和和05號是好友，號是好友，04和和05、06號是好友，號是好友，06和和07之間是好友，之間是好友，08無好友，假設(shè)表示無好友，假設(shè)表示這種邏輯構(gòu)造的關(guān)系為這種邏輯構(gòu)造的關(guān)系為r3，那么，那么r3可以定義為學(xué)生之間的好可以定義為學(xué)生之間的好友關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：友關(guān)系，該數(shù)據(jù)構(gòu)造的邏輯構(gòu)造可用二元組表示為：G =D

10、，S，r3SD =01，02，03，04，05，06，07，08r3 =，數(shù)據(jù)的存儲構(gòu)造 數(shù)據(jù)的存儲構(gòu)造Storage Structure，是指數(shù)據(jù)的邏輯構(gòu)造到計算機存儲器的映射。對于數(shù)據(jù)的邏輯構(gòu)造G =D，S，在映射中，一方面要將數(shù)據(jù)集D中的數(shù)據(jù)元素存放到存儲器中，另一方面還要表達關(guān)系集S，常見的表達關(guān)系S的方式有顯示和隱含兩種。常用的實現(xiàn)數(shù)據(jù)存儲構(gòu)造的方法有如下四種：1順序存儲2鏈接存儲3索引存儲4散列存儲四種存儲方法，可以單獨運用，也可以組合起來對數(shù)據(jù)構(gòu)造進展存儲映象。同一種邏輯構(gòu)造采用不同的存儲方法，可以得到不同的存儲構(gòu)造。針對詳細的運用，某種數(shù)據(jù)構(gòu)造選擇何種存儲構(gòu)造主要思索運算的方便

11、及效率。存儲構(gòu)造的描畫：數(shù)據(jù)的存儲構(gòu)造是數(shù)據(jù)的邏輯構(gòu)造用計算機言語的實現(xiàn)，它是依賴于計算機言語的，因此可以借用高級言語中提供的數(shù)據(jù)類型如數(shù)組、指針等來描畫它。l1順序存儲順序存儲l根本思想是：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相鄰的根本思想是：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相鄰的存儲單元里。存儲單元里。l數(shù)據(jù)元素間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來表達，也就是說數(shù)據(jù)元素間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來表達，也就是說邏輯關(guān)系上相鄰物理位置上也相鄰，數(shù)據(jù)元素的邏輯次序與物理邏輯關(guān)系上相鄰物理位置上也相鄰，數(shù)據(jù)元素的邏輯次序與物理次序一致。這是一種隱含表達關(guān)系的存儲方法，關(guān)系隱含在存儲次

12、序一致。這是一種隱含表達關(guān)系的存儲方法，關(guān)系隱含在存儲位置上。位置上。 l數(shù)據(jù)元素在存儲區(qū)域中是延續(xù)存放的，這種存儲方法稱為順序存數(shù)據(jù)元素在存儲區(qū)域中是延續(xù)存放的，這種存儲方法稱為順序存儲構(gòu)造儲構(gòu)造Sequential Storage Structure，通常用計算機高級，通常用計算機高級言語中的數(shù)組來描畫。言語中的數(shù)組來描畫。 l2鏈接存儲鏈接存儲l根本思想是：經(jīng)過附加指針域表示數(shù)據(jù)元素之間的關(guān)系。根本思想是：經(jīng)過附加指針域表示數(shù)據(jù)元素之間的關(guān)系。l這種存儲方法不要求邏輯上相鄰的數(shù)據(jù)元素存儲位置上也相鄰，這種存儲方法不要求邏輯上相鄰的數(shù)據(jù)元素存儲位置上也相鄰，數(shù)據(jù)元素間的邏輯關(guān)系是經(jīng)過附加指

13、示其他數(shù)據(jù)元素位置的地址數(shù)據(jù)元素間的邏輯關(guān)系是經(jīng)過附加指示其他數(shù)據(jù)元素位置的地址信息指針而得到的，這是一種顯示表達關(guān)系的存儲方法。信息指針而得到的，這是一種顯示表達關(guān)系的存儲方法。l數(shù)據(jù)元素在存儲區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常數(shù)據(jù)元素在存儲區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常用計算機高級言語中的指針來描畫，稱為鏈接存儲構(gòu)造用計算機高級言語中的指針來描畫，稱為鏈接存儲構(gòu)造Linked Storage Structure。 l由于不要求存儲空間的延續(xù)性，很適宜動態(tài)存儲管理由于不要求存儲空間的延續(xù)性，很適宜動態(tài)存儲管理 例例1.4 用上述兩種方法存儲有序序列用上述兩種方法存儲有序序

14、列A=99， 123，134，假設(shè)每個數(shù)據(jù)元素占，假設(shè)每個數(shù)據(jù)元素占2個字個字 節(jié)，即一個存儲單元為兩個字節(jié)。節(jié)，即一個存儲單元為兩個字節(jié)。圖1.4 關(guān)系的映像方法l 3索引存儲索引存儲l 根本思想是：除了存儲數(shù)據(jù)元素，還要建立一個或假設(shè)干個附加的根本思想是：除了存儲數(shù)據(jù)元素，還要建立一個或假設(shè)干個附加的索引表來標(biāo)識數(shù)據(jù)元素的地址。索引表來標(biāo)識數(shù)據(jù)元素的地址。l 索引表中的每一項稱為索引項，是用來標(biāo)識一個或一組數(shù)據(jù)元素的索引表中的每一項稱為索引項，是用來標(biāo)識一個或一組數(shù)據(jù)元素的存儲位置。索引項普通方式為關(guān)鍵字，地址，其中的關(guān)鍵字是存儲位置。索引項普通方式為關(guān)鍵字，地址，其中的關(guān)鍵字是用來標(biāo)識數(shù)

15、據(jù)元素的數(shù)據(jù)項。用來標(biāo)識數(shù)據(jù)元素的數(shù)據(jù)項。l 假設(shè)每個數(shù)據(jù)元素對應(yīng)一個索引項，那么該索引表為稠密索引假設(shè)每個數(shù)據(jù)元素對應(yīng)一個索引項，那么該索引表為稠密索引Dense Index。假設(shè)一組數(shù)據(jù)元素對應(yīng)一個索引項，那么該索引。假設(shè)一組數(shù)據(jù)元素對應(yīng)一個索引項，那么該索引表稱為稀疏索引表稱為稀疏索引Sparse Index。l 索引存儲方法主要是用于實現(xiàn)快速查找而設(shè)計的一種存儲方式。索引存儲方法主要是用于實現(xiàn)快速查找而設(shè)計的一種存儲方式。l 4散列存儲散列存儲l 根本思想是：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該結(jié)點的存儲地址根本思想是：根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該結(jié)點的存儲地址，通常稱為關(guān)鍵字地址轉(zhuǎn)換

16、法。在此方法中需求設(shè)計一個散列函，通常稱為關(guān)鍵字地址轉(zhuǎn)換法。在此方法中需求設(shè)計一個散列函數(shù)，以關(guān)鍵字為自變量，散列函數(shù)值即為地址。數(shù)，以關(guān)鍵字為自變量，散列函數(shù)值即為地址。l 用這種存儲方法設(shè)計的存儲構(gòu)造最適宜按關(guān)鍵字進展查找，但數(shù)據(jù)用這種存儲方法設(shè)計的存儲構(gòu)造最適宜按關(guān)鍵字進展查找，但數(shù)據(jù)元素之間的關(guān)系曾經(jīng)無法在存儲構(gòu)造上表達。元素之間的關(guān)系曾經(jīng)無法在存儲構(gòu)造上表達。 數(shù)據(jù)的運算數(shù)據(jù)的運算也稱操作是指對數(shù)據(jù)元素進展加工和處置。運算的種類很多，詳細視運用的要求而設(shè)置運算的種類。對每種數(shù)據(jù)構(gòu)造設(shè)置一些根本運算操作，使得不同運用都能經(jīng)過這些操作實現(xiàn)對數(shù)據(jù)構(gòu)造的各種訪問，是數(shù)據(jù)構(gòu)造中研討的一個重要方

17、面。數(shù)據(jù)構(gòu)造的根本操作普通包括查找、插入、刪除、更新、排序等。這些根本運算實踐是在籠統(tǒng)的數(shù)據(jù)上所施加的一系列籠統(tǒng)的操作，所謂籠統(tǒng)的操作，就是不涉及詳細的運用，只知道這些操作應(yīng)該完成的功能，但無須思索“如何完成。這些運算的粒度很小，是構(gòu)造復(fù)雜運算的根底。數(shù)據(jù)根本運算的定義是基于數(shù)據(jù)的邏輯構(gòu)造，每種經(jīng)典的邏輯構(gòu)造都有一個運算的集合。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯構(gòu)造上而實如今數(shù)據(jù)的存儲構(gòu)造上的 。 數(shù)據(jù)的運算是經(jīng)過算法來描畫的 。在討論任何一種數(shù)據(jù)構(gòu)造時，都應(yīng)該將數(shù)據(jù)的邏輯構(gòu)造、數(shù)據(jù)的存儲構(gòu)造和數(shù)據(jù)的運算這三方面看成一個整體，不要孤立地了解一個方面，而要留意它們之間的聯(lián)絡(luò) 13 算法算法的概念及特性

18、算法Algorithm是處理特定問題的方法和步驟，是由假設(shè)干條指令組成的有限序列。一個算法必需具有以下五個特性：1有窮性：對于恣意一組合法輸入值，一個算法必需總是在執(zhí)行有窮步驟后終了，有限時間內(nèi)完成。2確定性：算法中每條指令都確切地規(guī)定了所應(yīng)執(zhí)行的操作，使算法的執(zhí)行者或閱讀者能明確其含義及如何執(zhí)行，不致產(chǎn)生二義性或多義性；另外，在同一條件下，一個算法只能有一條執(zhí)行途徑。3可行性：算法中的每一步都是可行的，都可以經(jīng)過手工或機器可以接受的有限次操作在有限時間內(nèi)完成。4輸入：一個算法有0個或多個輸入，這些輸入是算法所需的初始量或待處置的對象，來自某個特定的對象集合。 5輸出：一個算法有1個或多個輸出

19、，這些輸出與輸入有著某種特定的關(guān)系。算法的描畫算法的描畫 算法普通可以采用自然言語、程序流程圖、偽碼、算法普通可以采用自然言語、程序流程圖、偽碼、高級程序設(shè)計言語等描畫。高級程序設(shè)計言語等描畫。算法的評價算法的評價 通常從定性和定量兩方面來評價一個算法通常從定性和定量兩方面來評價一個算法 算法的定性評價，是從算法的設(shè)計者和運用者角度算法的定性評價，是從算法的設(shè)計者和運用者角度來衡量優(yōu)劣的來衡量優(yōu)劣的 1正確性正確性Correctness是指算法該當(dāng)滿足是指算法該當(dāng)滿足詳細問題的需求，即對合理的輸入，算法都會得出詳細問題的需求，即對合理的輸入，算法都會得出正確的結(jié)果，這是設(shè)計和評價一個算法的首要

20、條件正確的結(jié)果，這是設(shè)計和評價一個算法的首要條件，否那么其他的評價規(guī)范也就無從談起。，否那么其他的評價規(guī)范也就無從談起。2可讀性可讀性Readablity是指算法被了解的難是指算法被了解的難易程度。易程度。3強壯性強壯性Robustness是指算法對輸入的非是指算法對輸入的非法數(shù)據(jù)恰當(dāng)?shù)刈鞒龇从郴蜻M展相應(yīng)處置的才干。法數(shù)據(jù)恰當(dāng)?shù)刈鞒龇从郴蜻M展相應(yīng)處置的才干。4簡單性簡單性Simplicity是指一個算法所采用的是指一個算法所采用的邏輯構(gòu)造、存儲構(gòu)造以及處置過程的簡單程度。邏輯構(gòu)造、存儲構(gòu)造以及處置過程的簡單程度。 l 算法的定量評價l1時間復(fù)雜度Time Complexity是一個算法運轉(zhuǎn)時所

21、耗費的系統(tǒng)時間，也就是算法的時間效率。 l每條語句反復(fù)執(zhí)行的次數(shù)稱為語句的頻度Frenquency countl當(dāng)不思索算法運轉(zhuǎn)的軟硬件環(huán)境時，算法所耗費的時間就是該算法中一切簡單語句的頻度之和。 l普通情況，在討論算法的時間效率時，主要思索當(dāng)問題規(guī)模n趨向無窮大時，時間復(fù)雜度T(n)的數(shù)量級，亦稱為算法的漸近時間復(fù)雜度，那么T(n)= O(f(n) 。l 記號“O是一個數(shù)學(xué)符號，其數(shù)學(xué)定義是： l 設(shè)T(n)和f(n)均為正整數(shù)n的函數(shù)，假設(shè)存在兩個正整數(shù)M和n0，使得當(dāng)nn0時，都有 | T(n)| M | f(n)| 存在，那么T(n)= O(f(n)。lim T(n) / f(n) =

22、 Mnu在多數(shù)情況下，當(dāng)一個算法中有假設(shè)干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套循環(huán)中最內(nèi)層循環(huán)語句的頻度決議的。需求留意的是，假設(shè)算法中包括對其他函數(shù)或算法的調(diào)用，計算算法的時間復(fù)雜度時還要分析被調(diào)用算法或函數(shù)的時間復(fù)雜度。例例1.5 求一維數(shù)組元素中的最大值求一維數(shù)組元素中的最大值 int sum(int a,int n) int i,s; 1 s= a0; /*1次次*/2 for(i=1;in; i+; ) /*n次次*/3 if (s ai) s= ai; /*n-1次次*/4 return s; /*1次次*/ T1(n)= 1+n+n-1+1=2n+1 T1(n)=O(n) ，即

23、，即f(n)=n例例1.6 兩個兩個n階方陣相加階方陣相加void Matrixadd(int a ,int b ,int c ,int n) int i,j;1 for (i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=aij+bij; /* n2次次*/T2(n)= n+1+ n(n+1)+ n2=2n2+2n+1T2(n)=O(n2)，即，即f(n)=n2 例例1.7 求兩個求兩個n階方陣的乘積階方陣的乘積void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k;1 for

24、(i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=0; /* n2次次*/4 for (k=0;kn;k+) /* n2(n+1)次次*/5 cij= cij+aik*bkj; /* n3次次*/ T3(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1T3(n)= O(n3) ，即，即f(n)=n3 l最好時間復(fù)雜度、最壞時間復(fù)雜度和平均時間復(fù)雜度最好時間復(fù)雜度、最壞時間復(fù)雜度和平均時間復(fù)雜度 l例例1.8 在一維數(shù)組中查找指定的元素在一維數(shù)組中查找指定的元素l int search(int a,int x,int n)l int i;l1 for(i=0;in; i+; ) l2 if (ai=x) ruturn i+1; l3 return 0; l l最好時間復(fù)雜度為最好時間復(fù)雜度為O(1)l最壞時間復(fù)雜度為最壞時間復(fù)雜度為O(n)l平均