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

數(shù)據(jù)結(jié)構(gòu)新疆大學(xué)軟件學(xué)院孫華

電話-mail:xj_sh@163.com2015-2016學(xué)年第一學(xué)期

使用教材：嚴(yán)蔚敏吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社參考書：1、曹桂琴編著，數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，大連理工大學(xué)出版社。2、晉良穎編，數(shù)據(jù)結(jié)構(gòu)，人民郵電出版社3、BrunoR.Preiss，數(shù)據(jù)結(jié)構(gòu)與算法，電子工業(yè)出版社使用教材及參考書課程教學(xué)目的在計算機(jī)及其應(yīng)用的各個領(lǐng)域中，都會用到各種各樣的數(shù)據(jù)結(jié)構(gòu)，通過本課程使學(xué)生學(xué)會分析和研究計算機(jī)加工對象的特性，選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲表示，以及編制相應(yīng)的實現(xiàn)算法．課程教學(xué)基本要求:本課程介紹各種最常用的數(shù)據(jù)結(jié)構(gòu)，闡述各種數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系，討論它們在計算機(jī)中的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上的運算和實際的執(zhí)行算法，并對算法的效率進(jìn)行簡要的分析和討論。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機(jī)硬件（特別是編碼理論、存儲裝置和存取方法）的研究范圍，而且和計算機(jī)軟件的研究有著密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。課程介紹數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程。程序＝算法＋數(shù)據(jù)結(jié)構(gòu)目前在我國，《數(shù)據(jù)結(jié)構(gòu)》已經(jīng)不僅僅是計算機(jī)專業(yè)的教學(xué)計劃中的核心課程之一，而且是其它非計算機(jī)專業(yè)的主要選修課程之一。通過對這門課程的學(xué)習(xí)可增強(qiáng)選擇合適的數(shù)據(jù)結(jié)構(gòu)與編寫高效的程序的能力。課程介紹教學(xué)安排及考試講課學(xué)時：50學(xué)時上機(jī)時間：4次（共8學(xué)時）考試成績計算：平時成績（考勤、作業(yè)及上機(jī)）30分考試（70分）

目錄第1章緒論第2章線性表第3章棧和隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章內(nèi)部排序第10章文件計算機(jī)的應(yīng)用已不再局限于科學(xué)計算，而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作。與此對應(yīng)，計算機(jī)加工處理的對象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)。為了編寫出一個“好”的程序，必須分析待處理的對象的特征以及各對象之間存在的關(guān)系，這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。第一章緒論第一章緒論用計算機(jī)解決一個具體問題時，大致需要經(jīng)多下列幾個步驟：首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型然后設(shè)計一個解此數(shù)學(xué)模型的算法，最后編出程序、進(jìn)行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。然而，更多的非數(shù)值問題無法用數(shù)學(xué)方程描述。什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個例子。1.1什么是數(shù)據(jù)結(jié)構(gòu)書目文件按書名按作者名按分類號索引表線性表例1書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片樹……..……..…...…...…...…...例2人機(jī)對奕問題對于一個多叉路口，設(shè)計一個交通信號燈的管理系統(tǒng)。首先需要分析一下所有車輛的行駛路線的沖突問題。這個問題可以歸結(jié)為對車輛的可能行駛方向作某種分組，對分組的要求是使任一個組中各個方向行駛的車輛可以同時安全行駛而不發(fā)生碰撞。CEDAB例3多叉路口交通燈管理問題可通行方向ABACADBABCBDDADBDCEAEBECEDCEDAB例3多叉路口交通燈管理問題有些通行方向顯然不能同時進(jìn)行，相應(yīng)的結(jié)點間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型CEDAB圖把圖1.2中的結(jié)點進(jìn)行分組，使得有結(jié)點相連的結(jié)點不在同一個組里。

地圖著色問題如果把上圖中的一個結(jié)點理解為一個國家，結(jié)點之間的連線看作兩國有共同邊界，上述問題就變成著名的“著色問題”：即求出最少要幾種顏色可將圖中所有國家著色，使得任意兩個相鄰的國家顏色都不相同。通過上面的分析，我們就獲得了該交通管系統(tǒng)的數(shù)學(xué)模型。下面就可以著手進(jìn)行算法的設(shè)計。例3多叉路口交通燈管理問題算法設(shè)計2.“貪心法”

while有結(jié)點未著色；{選擇一種新顏色；

在未著色的結(jié)點中,給盡可能多的彼此結(jié)點之間沒有邊點著色；}1.對n個結(jié)點，逐個測試其所有組合；例3多叉路口交通燈管理問題ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型圖ABACADBABCBDDADBDCEAEBECEDCEDAB著色結(jié)果把上面方法應(yīng)用于圖1.2，得到下面的分組：

綠色：AB,AC,AD,BA,DC,ED

藍(lán)色：BC,BD,EA

紅色：DA,DB

白色：EB,EC例3多叉路口交通燈管理問題描述非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。第一章緒論數(shù)據(jù)(Data):是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。對計算機(jī)科學(xué)而言，數(shù)據(jù)的含義極為廣泛，如圖像、聲音等都可以通過編碼而歸之于數(shù)據(jù)的范疇。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。例如，例1－2中的“樹”中的一個棋盤格局，例1－3中的“圖”中的一個園圈都被稱為一個數(shù)據(jù)元素。1.2基本概念和術(shù)語一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。例如，例1－1中一本書的書目信息為一個數(shù)據(jù)元素，而書目信息中的每一項（如書名、作者名等）為一個數(shù)據(jù)項。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是集合N＝{0，±1，±2，…}，字母字符數(shù)據(jù)對象是集合C＝{A，B，C，…}。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：

Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Complex=(C，R)其中：C是含兩個實數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中有兩種不同的表示方法：

順序表示和非順序表示由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。1.2基本概念和術(shù)語元素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

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

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

h

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯€性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：1.2基本概念和術(shù)語數(shù)據(jù)類型：數(shù)據(jù)類型是一個值的集合和定義在這個值集范圍上的一組操作的總稱。例如，C語言中的整型變量，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作為：加、減、乘、除和取模等算術(shù)運算。按“值”的不同特性，高級程序語言中的數(shù)據(jù)類型可分為：一類是非結(jié)構(gòu)的原子類型。原子類型的值是不可分解的。如：C語言中的基本類型（整型、實型、字符型和枚舉類型）、指針類型和空類型。另一類是結(jié)構(gòu)類型。結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。例如數(shù)組的值由若干分量組成。每個分量可以是整數(shù)，也可以是數(shù)組等。1.2基本概念和術(shù)語抽象數(shù)據(jù)類型：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。和數(shù)據(jù)結(jié)構(gòu)的形式定義相對應(yīng)，抽象數(shù)據(jù)類型可用三元組描述如下：（Ｄ，Ｓ，Ｐ）D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。1.2基本概念和術(shù)語本書采用以下格式定義抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的定義：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)邏輯關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名基本操作的定義格式為：

基本操作名（參數(shù)表）

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>1.2基本概念和術(shù)語抽象數(shù)據(jù)類型三元組的定義：ADTTriplet{數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3ElemSet}數(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的值。}ADTTriplet1.2基本概念和術(shù)語ADTTriplet{數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3ElemSet}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：Get(T，i，&e)初始條件：三元組T已存在，1i3操作結(jié)果：用e返回T的第i元的值。}ADTTriplet1.2基本概念和術(shù)語抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。由于本書在高級程序設(shè)計語言的虛擬層次上討論抽象數(shù)據(jù)類型的表示和實現(xiàn)，并且討論的數(shù)據(jù)結(jié)構(gòu)及其算法主要是面向讀者，故采用介于偽碼和C語言之間的類C語言作為描述工具，有時也用偽碼描述一些只含抽象操作的抽象算法。這使得數(shù)據(jù)結(jié)構(gòu)和算法的描述和討論簡明清晰，不拘泥于C語言的細(xì)節(jié)，又能容易轉(zhuǎn)換成C或者C＋＋程序。1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)本書采用的類C語言精選了C語言的一個核心子集，同時作了若干擴(kuò)充，增強(qiáng)了語言的描述功能。以下對其作簡要說明。（1）預(yù)定義常量和類型

//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼

TypedefintStatus;1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（2）數(shù)據(jù)結(jié)構(gòu)的表示用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為Elemtype，由用戶在使用該數(shù)據(jù)類型時定義。（3）基本操作的算法都用以下形式的函數(shù)描述：函數(shù)類型

函數(shù)名（函數(shù)參數(shù)表）{//算法說明語句序列}//函數(shù)名

1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（4）賦值語句有簡單賦值變量名=表達(dá)式；串值賦值變量名1=變量名2=……=表達(dá)式成組賦值（變量名1，。。。，）=（表達(dá)式1，）交換賦值變量名變量名條件賦值變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（5）選擇語句有條件語句1if（表達(dá)式）語句；條件語句2if（表達(dá)式）語句；Else語句開關(guān)語句1switch(表達(dá)式){case值1：語句序列1；break;Default:語句序列n+1;}開關(guān)語句2switch{case條件1：語句序列1；break;Default:語句序列n+1;}1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（6）循環(huán)語句有For語句for（賦初值表達(dá)式；條件；修改表達(dá)式序列）語句；While語句while（條件）語句；do-while語句do{語句序列}while（條件）；1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（7）結(jié)束語句函數(shù)結(jié)束語句return表達(dá)式；return；Case結(jié)束語句break;異常結(jié)束語句exit(異常代碼)（8）輸入和輸出語句輸入語句scanf([格式串]，變量1，變量n)；輸出語句printf([格式串]，表達(dá)式1，表達(dá)式2)；1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（9）注釋單行注釋//文字序列（10）基本函數(shù)有求最大值max(表達(dá)式1，表達(dá)式n）求最小值min(表達(dá)式1，表達(dá)式n）求絕對值abs(表達(dá)式)求不足整數(shù)值floor（表達(dá)式）判定行結(jié)束eoln（文件變量）或eoln1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)（11）邏輯運算約定與運算&&:對于A&&B,當(dāng)A的值為0時,不再對B求值?；蜻\算||：對于A||B,當(dāng)A的值為非0時,不再對B求值。1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)例題：抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)//--------采用動態(tài)分配的順序存儲結(jié)構(gòu)----------------TypedefElemType*Triplet://--------基本操作的函數(shù)原形說明----------------//initTriplet分配三個元素存儲空間StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3）；//操作結(jié)果：構(gòu)造了三元組T，元素e1，e2和e3分別賦以參數(shù)v1，v2和v3的值。1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)StatusDestroyTriplet(Triplet&T）；//操作結(jié)果：三元組T被消除。StatusGet(Triplet&T，inti，ElemType&e）；//初始條件：三元組T已存在，1i3。

//操作結(jié)果：用e返回T的第i元的值。1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)//--------基本操作的實現(xiàn)----------------StatusGet(Triplet&T，inti，ElemType&e）{//1i3,用e返回T的第i元的值。

If(i<1||i>3)returnERROR;e=T[i-1]；

returnOK;}//Get}ADTTriplet1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)算法是對特定問題求解步驟的一種描述，它是指令的有限序列，每一條指令表示一個或多個操作。算法有五個特性：1.4算法和算法分析（1）有窮性一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。（2）確定性算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。（3）可行性一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。（4）輸入一個算法有零個或多個輸入。（5）輸出一個算法有一個或多個輸出。評價一個好的算法有以下幾個標(biāo)準(zhǔn):（1）正確性（2）可讀性算法應(yīng)該好讀。（3）健狀性算法應(yīng)具有容錯處理。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。（4）效率與存儲量需求效率是指算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。2、算法設(shè)計的要求程序不含語法錯誤。程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明的結(jié)果。正確性（算法應(yīng)滿足具體問題的需求）算法執(zhí)行時間需要通過依據(jù)該算法編制的程序在計算機(jī)上運行時所消耗的時間度量。度量一個程序的執(zhí)行時間通常有兩種方法。事后統(tǒng)計的方法

一是必須先運行依據(jù)算法編制的程序二是所得時間的統(tǒng)計量依賴于計算機(jī)的硬件、軟件等環(huán)境因素求出該算法的一個時間界限函數(shù)事前分析估算的方法

依據(jù)的算法選用何種策、問題的規(guī)模、書寫的語言、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量、機(jī)器執(zhí)行指令的速度。所以，人們常常采用事前分析估算的方法。3、算法效率的度量使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機(jī)硬件軟件有關(guān)的因素，可以認(rèn)為一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量表示），或者說，它是問題規(guī)模的函數(shù)。一個算法是由控制結(jié)構(gòu)（順序分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于研究問題（或算法類型）來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。3、算法效率的度量一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間度量記作T(n)=O(f(n))它表示隨著問題規(guī)模n的增加，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。3、算法效率的度量顯然，被稱作問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度是指的是該語句重復(fù)執(zhí)行的次數(shù)。例２{++x;s=0;}將x自增看成是基本操作，則語句頻度為１，即時間復(fù)雜度為Ｏ(1)。如果將s=0也看成是基本操作，則語句頻度為２，其時間復(fù)雜度仍為Ｏ(1)，即常量階。3、算法效率的度量例３、for(i=1;i<=n;++i){++x;s+=x;}語句頻度為：2n

其時間復(fù)雜度為：O(n)即時間復(fù)雜度為線性階。例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}語句頻度為：2n2時間復(fù)雜度為：O(n2)即時間復(fù)雜度為平方階。3、算法效率的度量定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，則A(n)=O(nm)。證略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}語句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2時間復(fù)雜度為O(n2),

即此算法的時間復(fù)雜度為平方階。3、算法效率的度量for(i=1;i<=n;++