數(shù)據(jù)結(jié)構(gòu)教材:自考《數(shù)據(jù)結(jié)構(gòu)》

蘇仕華編著

授課教師：涂風(fēng)華開始日期：2014年3月1日

1.1基本概念和術(shù)語

1.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

1.3算法的描述和分析第1章概論數(shù)據(jù)（data)—是信息的載體。它能夠被計(jì)算機(jī)識別、存儲和加工處理，是計(jì)算機(jī)程序加工的"原料"。

數(shù)據(jù)元素（dataelement）—是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項(xiàng)組成，也稱結(jié)點(diǎn)、元素、頂點(diǎn)或記錄。數(shù)據(jù)項(xiàng)（dataitem）—是具有獨(dú)立含義的最小標(biāo)識單位，有時也稱為域（field），即數(shù)據(jù)表中的字段。1.1基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)(datastructure)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。

數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：①數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）；②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（StorageStructure）；③數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。①數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。

②數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱為映象），它依賴于計(jì)算機(jī)語言。對機(jī)器語言而言，存儲結(jié)構(gòu)是具體的。一般，只在高級語言的層次上討論存儲結(jié)構(gòu)。③數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運(yùn)算的集合。最常用的檢索、插入、刪除、更新、排序等運(yùn)算實(shí)際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。所謂抽象的操作，是指我們只知道這些操作是"做什么"，而無須考慮"如何做"。只有確定了存儲結(jié)構(gòu)之后，才考慮如何具體實(shí)現(xiàn)這些運(yùn)算。

3為了增加對數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識，下面舉例來說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念。

【例1．1】學(xué)生成績表，見下表。

（1）邏輯結(jié)構(gòu)

表中的每一行是一個數(shù)據(jù)元素（或記錄、結(jié)點(diǎn)），它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。

表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對表中任一個結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)（亦稱為直接前趨（ImmediatePredecessor））最多只有一個；與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)（亦稱為直接后繼（ImmediateSuccessor））也最多只有一個。表中只有第一個結(jié)點(diǎn)沒有直接前趨，故稱為開始結(jié)點(diǎn)；也只有最后一個結(jié)點(diǎn)沒有直接后繼。故稱之為終端結(jié)點(diǎn)。例如，表中"李四"所在結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)分別是"張三"和"王五"所在的結(jié)點(diǎn)，上述結(jié)點(diǎn)間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。

（2）存儲結(jié)構(gòu)

該表的存儲結(jié)構(gòu)是指用計(jì)算機(jī)語言如何表示結(jié)點(diǎn)之間的這種關(guān)系，即表中的結(jié)點(diǎn)是順序鄰接地存儲在一片連續(xù)的單元之中，還是用指針將這些結(jié)點(diǎn)鏈接在一起？

（3）數(shù)據(jù)的運(yùn)算

在上面的學(xué)生成績表中，可能要經(jīng)常查看某一學(xué)生的成績；當(dāng)學(xué)生退學(xué)時要刪除相應(yīng)的結(jié)點(diǎn)；進(jìn)來新學(xué)生時要增加結(jié)點(diǎn)。究竟如何進(jìn)行查找、刪除、插入，這就是數(shù)據(jù)的運(yùn)算問題。

搞清楚了上述三個問題，也就弄清了學(xué)生成績表這個數(shù)據(jù)結(jié)構(gòu)。2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分類

在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：（1）線性結(jié)構(gòu)

線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個直接前趨和一個直接后繼。

線性表是一個典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。（2）非線性結(jié)構(gòu)

非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點(diǎn)可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。3．?dāng)?shù)據(jù)的四種基本存儲方法

數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：

（1）順序存儲方法

該方法把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。

由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。

該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實(shí)現(xiàn)順序存儲。（2）鏈接存儲方法

該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)（LinkedStorageStructure）,通常借助于程序語言的指針類型描述。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲1536元素21400元素11346元素3∧元素41345h存儲地址存儲內(nèi)容指針

1345元素1

1400

1346元素4∧…….……..…….

1400

元素2

1536…….……..…….

1536元素3

1346

鏈?zhǔn)酱鎯?/p>

h（3）索引存儲方法

該方法通常在儲存結(jié)點(diǎn)信息的同時，還建立附加的索引表。

索引表由若干索引項(xiàng)組成。若每個結(jié)點(diǎn)在索引表中都有一個索引項(xiàng)，則該索引表稱之為稠密索引（DenseIndex）。若一組結(jié)點(diǎn)在索引表中只對應(yīng)一個索引項(xiàng)，則該索引表稱為稀疏索引(SpareIndex)。索引項(xiàng)的一般形式是：

(關(guān)鍵字、地址)

關(guān)鍵字是能唯一標(biāo)識一個結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲位置；稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲位置。（4）散列存儲方法

該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。

四種基本存儲方法，既可單獨(dú)使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映像。

同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運(yùn)算方便及算法的時空要求。

4．?dāng)?shù)據(jù)結(jié)構(gòu)三方面的關(guān)系

數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算這三方面是一個整體。孤立地去理解一個方面，而不注意它們之間的聯(lián)系是不可取的。

存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面：同一邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識。

【例】線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲表示，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒ǎ瑒t可稱其為鏈表；若采用散列存儲方法，則可稱為散列表。

數(shù)據(jù)的運(yùn)算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運(yùn)算集合及其運(yùn)算的性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。

【例】若對線性表上的插入、刪除運(yùn)算限制在表的一端進(jìn)行，則該線性表稱之為棧；若對插入限制在表的一端進(jìn)行，而刪除限制在表的另一端進(jìn)行，則該線性表稱之為隊(duì)列。更進(jìn)一步，若線性表采用順序表或鏈表作為存儲結(jié)構(gòu)，則對插入和刪除運(yùn)算做了上述限制之后，可分別得到順序棧或鏈棧，順序隊(duì)列或鏈隊(duì)列。

5．?dāng)?shù)據(jù)類型和抽象數(shù)據(jù)類型

數(shù)據(jù)類型（DataType）

自20世紀(jì)70年代以來，幾乎所有的高級程序設(shè)計(jì)語言都提供了這一概念。在用高級語言編寫的程序中間，程序中出現(xiàn)的每個變量，常量或表達(dá)式，都必須事先說明它們所屬的數(shù)據(jù)類型，每個類型都明顯或隱含的規(guī)定了在程序執(zhí)行期間它的變量，它的表達(dá)式所允許取值的范圍，以及允許進(jìn)行的操作，因此所謂數(shù)據(jù)類型是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

【例1．2】C語言的"整數(shù)類型"就定義了一個整數(shù)可取值的范圍（其最大值INT-MAX依賴于具體機(jī)器）以及對整數(shù)可施加的加、減、乘、除和取模等操作。

按"值"是否可分解，可將數(shù)據(jù)類型劃分為兩類：

①原子類型：其值不可分解。通常是由語言直接提供。

【例】C語言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡單的導(dǎo)出類型；

②結(jié)構(gòu)類型：其值可分解為若干個成分（或稱為分量）。是用戶借助于語言提供的描述機(jī)制自己定義的，它通常是由標(biāo)準(zhǔn)類型派生的，故它也是一種導(dǎo)出類型。

【例】C的數(shù)組、結(jié)構(gòu)等類型。用戶也可用typedef

自己定義數(shù)據(jù)類型typedef

struct{

intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;抽象數(shù)據(jù)類型ADT（AbstractDataType)定義：是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作。可以看作是數(shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。

數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作=抽象數(shù)據(jù)類型

一個ADT可描述為：

ADTADT-Name{

Data://數(shù)據(jù)說明

數(shù)據(jù)元素之間邏輯關(guān)系的描述

Operations://操作說明

Operation1://操作1，它通常可用C或C﹢﹢的函數(shù)原型來描述

Input:對輸入數(shù)據(jù)的說明

Preconditions:執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)//可看作初始條件

Process:對數(shù)據(jù)執(zhí)行的操作

Output:對返回?cái)?shù)據(jù)的說明

Postconditions:執(zhí)行本操作后系統(tǒng)的狀態(tài)//"系統(tǒng)"可看作某個數(shù)據(jù)結(jié)構(gòu)

Operation2://操作2

……

}//ADT

描述方法形式定義：我們用一個三元組（D，S，P）來表示一個抽象數(shù)據(jù)類型，其中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ù)表）初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)引用參數(shù)，以“＆”打頭例：抽象數(shù)據(jù)類型三元組的定義：

ADTTriplet{

數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3∈Elemset}

數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,v1,v2,v3)

操作結(jié)果：構(gòu)造了三元組T，元素e1，e2和e3分別被賦以參數(shù)v1,v2和v3的值。

DestroyTriplet（&T）操作結(jié)果：三元組T被銷毀。

Get（T,i,&e）

初始條件：三元組T已存在，1<=i<=3.

操作結(jié)果：用e返回T的第i元的值。Put(&T,i,e)

初始條件：三元組T已存在，1<=i<=3.

操作結(jié)果：改變T的第i元的值為e。

IsAscending(T)

初始條件：三元組T已存在。操作結(jié)果：如果T的3個元素按升序排列，則返回1，否則返回0。IsDescending(T)

初始條件：三元組T已存在。操作結(jié)果：如果T的3個元素按降序排列，則返回1，否則返回0。Max(T,&e)

初始條件：三元組T已存在。操作結(jié)果：用e返回T的3個元素中的最大值。Min(T,&e)

初始條件：三元組T已存在。操作結(jié)果：用e返回T的3個元素中的最小值。}ADTTriplet抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨(dú)立于具體實(shí)現(xiàn)。它的優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實(shí)現(xiàn)了信息隱藏。在C﹢﹢中，我們可以用類（包括模板類）的說明來表示ADT，用類的實(shí)現(xiàn)來實(shí)現(xiàn)ADT。因此，C﹢﹢中實(shí)現(xiàn)的類相當(dāng)于是數(shù)據(jù)的存儲結(jié)構(gòu)及其在存儲結(jié)構(gòu)上實(shí)現(xiàn)的對數(shù)據(jù)的操作。

ADT和類的概念實(shí)際上反映了程序或軟件設(shè)計(jì)的兩層抽象：ADT相當(dāng)于是在概念層（或稱為抽象層）上描述問題，而類相當(dāng)于是在實(shí)現(xiàn)層上描述問題。此外，C﹢﹢中的類只是一個由用戶定義的普通類型，可用它來定義變量（稱為對象或類的實(shí)例）。因此，在C﹢﹢中，最終是通過操作對象來解決實(shí)際問題的，所以我們可將該層次看作是應(yīng)用層。例如，main程序就可看作是用戶的應(yīng)用程序。

由于C語言中沒有提供"類"這一數(shù)據(jù)類型，因此無法實(shí)現(xiàn)ADT，故我們不采用ADT的形式來描述數(shù)據(jù)結(jié)構(gòu)，以節(jié)省篇幅。大家只要記住，它實(shí)際上等價于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作。1.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義著名計(jì)算機(jī)科學(xué)家、Pascal語言發(fā)明者N.沃思教授提出：

程序=算法+數(shù)據(jù)結(jié)構(gòu)

程序:

處理問題編制一組指令集算法:處理問題的策略數(shù)據(jù)結(jié)構(gòu):問題的數(shù)學(xué)模型也就是說，計(jì)算機(jī)按照程序所描述的算法對某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。1．計(jì)算機(jī)處理問題的分類

（1）數(shù)值計(jì)算問題

在計(jì)算機(jī)發(fā)展初期，人們使用計(jì)算機(jī)主要是處理數(shù)值計(jì)算問題。

【例】線性方程的求解

該類問題涉及的運(yùn)算對象是簡單的整型、實(shí)型或布爾型數(shù)據(jù)。程序設(shè)計(jì)者的主要精力集中于程序設(shè)計(jì)的技巧，無須重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，“非數(shù)值性問題”越來越顯得重要。據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值性問題占用了90%以上的機(jī)器時間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。程序設(shè)計(jì)的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。（2）非數(shù)值計(jì)算的程序設(shè)計(jì)問題：例1書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表算法：需要檢索的書目？如何檢索？用戶界面？模型：？例2人機(jī)對奕問題樹……..……..…...…...…...…...算法：對奕的規(guī)則和策略模型：？例3教學(xué)計(jì)劃編排問題

圖課程代號課程名稱先修課程C1計(jì)算機(jī)導(dǎo)論無C2數(shù)據(jù)結(jié)構(gòu)C1,C4C3匯編語言C1C4C語言C1C5計(jì)算機(jī)圖形學(xué)C2,C3,C4C6接口技術(shù)C3C7數(shù)據(jù)庫原理C2,C9C8編譯原理C4C9操作系統(tǒng)C2C1C3C4C7C6C5C2C8C9算法：如何確定課程的次序關(guān)系?模型：？從上述例子不難看出：解決問題的一個關(guān)鍵步驟是，選取合適的數(shù)據(jù)結(jié)構(gòu)表示該問題，然后才能寫出有效的算法。

1.3算法的描述和分析有窮性：對于任意一組合法輸入值，在執(zhí)行有窮步之后結(jié)束，且算法中的每個步驟都能在有限時間內(nèi)完成；確定性：每條指令都有確切的含義，在任何條件下算法都只有一條執(zhí)行路徑；算法五個重要特性：算法：是對特定問題求解步驟的一種描述，它是指令的有限序列。可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；輸入：有零個或多個輸入，取自特定的對象集合輸出：有一個或多個輸出，是算法進(jìn)行信息加工后得到的結(jié)果。二、算法分析

1．評價算法好壞的標(biāo)準(zhǔn)

求解同一計(jì)算問題可能有許多不同的算法，究竟如何來評價這些算法的好壞以便從中選出較好的算法呢？

選用的算法首先應(yīng)該是"正確"的。此外，主要考慮如下三點(diǎn)：

①執(zhí)行算法所耗費(fèi)的時間；

②執(zhí)行算法所耗費(fèi)的存儲空間，其中主要考慮輔助存儲空間；

③算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。

2．算法性能選擇

一個占存儲空間小、運(yùn)行時間短、其它性能也好的算法是很難做到的。原因是上述要求有時相互抵觸：要節(jié)約算法的執(zhí)行時間往往要以犧牲更多的空間為代價；而為了節(jié)省空間可能要耗費(fèi)更多的計(jì)算時間。因此我們只能根據(jù)具體情況有所側(cè)重：

①若該程序使用次數(shù)較少，則力求算法簡明易懂；

②對于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；

③若待解決的問題數(shù)據(jù)量極大，機(jī)器的存儲空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。

3．算法的時間性能分析

（1）算法耗費(fèi)的時間和語句頻度

一個算法所耗費(fèi)的時間=算法中每條語句的執(zhí)行時間之和

每條語句的執(zhí)行時間=語句的執(zhí)行次數(shù)(即頻度(FrequencyCount))×語句執(zhí)行一次所需時間

算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。

若要獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來分析算法的時間耗費(fèi)，則設(shè)每條語句執(zhí)行一次所需的時間均是單位時間，一個算法的時間耗費(fèi)就是該算法中所有語句的頻度之和。算法執(zhí)行時間的衡量方法和準(zhǔn)則

有兩種衡量算法效率的方法:

1.事后統(tǒng)計(jì)法：利用計(jì)算機(jī)內(nèi)記時功能，用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分。

2.事前分析估計(jì)法：求出算法的一個時間界限函數(shù)。和算法執(zhí)行時間相關(guān)的因素：算法選用的策略

問題的規(guī)模

書寫程序的語言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度（2）時間復(fù)雜度：程序運(yùn)行從開始到結(jié)束所需要的時間。設(shè)解決一個問題的規(guī)模為n，基本操作被重復(fù)執(zhí)行的次數(shù)是n的一個函數(shù)f（n），假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作：

T(n)=O(f(n))

其中T(n)叫算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。P8例1：NXN矩陣相乘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]=c[i][j]+a[i][k]*b[k][j];} 顯然，被稱做問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的原操作，多數(shù)情況下是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句頻度相同。例2．{++x;s=0;}例３．for(i=1;

i<=n;

++i){++x;

s+=x;}例４.for(i=2;

i<=n;

++i)for(j=2;

j<=i-1;

++j){++x;

a[i,j]=x;}T(n)=Ｏ(1)

常量階

T(n)=O(n)

線性階++x語句頻度為：1+2+3+…+n-2