數(shù)據(jù)結(jié)構(gòu)課堂用-第1章緒論

第一章緒論第一章 緒論（Introduction）內(nèi)容提要數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法和算法分析開發(fā)的過程:系統(tǒng)分析系統(tǒng)實現(xiàn)系統(tǒng)設(shè)計確定系統(tǒng)所要達到的目標(biāo)確定實現(xiàn)方案并生成系統(tǒng)實地安裝調(diào)試系統(tǒng)修整完善1.1數(shù)據(jù)結(jié)構(gòu)程序設(shè)計:算法:數(shù)據(jù)結(jié)構(gòu):為計算機處理問題編制一組指令集處理問題的策略問題的數(shù)學(xué)模型1.1

數(shù)據(jù)結(jié)構(gòu)Niklaus

WirthAlgorithm

+

Data

Structures

=

Programs數(shù)值問題非數(shù)值問題1.1

數(shù)據(jù)結(jié)構(gòu)兩類問題數(shù)值問題的求解，如:雞兔同籠問題二元一次代數(shù)方程組結(jié)構(gòu)靜力分析問題全球天氣預(yù)報高次線性代數(shù)方程組球面坐標(biāo)系下的環(huán)流模式方程1.1數(shù)據(jù)結(jié)構(gòu)非數(shù)值計算問題的求解，如：例一 對一組(n個)整數(shù)進行排序例二 交叉路口的交通 問題例三 煤氣管道的鋪設(shè)問題例四

海外華僑 的族譜問題1.1數(shù)據(jù)結(jié)構(gòu)①建立問題的數(shù)學(xué)模型（如，線性模型、樹狀模型、網(wǎng)狀模型等）②按照數(shù)學(xué)模型設(shè)計解決問題的算法③根據(jù)算法編寫程序，運行程序得到問題的解答1.1

數(shù)據(jù)結(jié)構(gòu)非數(shù)值性問題的求解方法：舉例：檢索系統(tǒng)----線性模型問題棋類對弈--------樹狀模型問題煤氣管道鋪設(shè)--------網(wǎng)狀模型問題1.1數(shù)據(jù)結(jié)構(gòu)書庫登錄號書名分類作者單價……………0011數(shù)據(jù)結(jié)構(gòu)CS26.000012C程序設(shè)計CS25.00……………0035數(shù)據(jù)結(jié)構(gòu)CS善16.00……………0125BASIC語言CS13.000126C程序設(shè)計CS寬復(fù)旦26.00……………0200高等數(shù)學(xué)MA高教18.00……………書名索引表1數(shù)據(jù)結(jié)構(gòu)2C程序設(shè)計3BASIC語言4高等數(shù)學(xué)…00110035

∧00120126∧0125∧0200∧作者索引表1234善…00120125∧0011∧0200∧0035∧一個結(jié)點線性模型問題樹狀模型問題井字棋的對弈樹煤氣管道鋪設(shè)問題：1.1

數(shù)據(jù)結(jié)構(gòu)非數(shù)值問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)是一門 “描述現(xiàn)實世界實體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作在計算機中如何表示 ”的學(xué)科。1.1數(shù)據(jù)結(jié)構(gòu)第一章 緒論內(nèi)容提要1.1數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法和算法分析所有能被輸入到計算機中，且能被計算機處理的符號的總稱，它是計算機程序加工的

“原料”。如，文字、字符、圖形、圖像、聲音等等。1.數(shù)據(jù)（Data)1.2

基本概念和術(shù)語是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。如， 檢索系統(tǒng)中的一本書的書目信息；井棋弈對弈樹中的一個棋盤格局；煤氣管道鋪設(shè)圖中的一個圓圈等等。2.數(shù)據(jù)元素(Data

Element)1.2

基本概念和術(shù)語一個具體的實體，

一個數(shù)據(jù)元素一般如一個學(xué)生，一本書等。在數(shù)據(jù)模型中， 往往不考慮數(shù)據(jù)元素的具體含義，而抽象成一個結(jié)點。數(shù)據(jù)元素的同義詞是：結(jié)點、頂點、記錄、元素1.2

基本概念和術(shù)語3.數(shù)據(jù)項(Data

Item)數(shù)據(jù)元素的分量，數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。4.數(shù)據(jù)對象(Data

Object)同類型數(shù)據(jù)元素的集合，如一個系的全體學(xué)生等。1.2

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

全體數(shù)據(jù)元素以及數(shù)據(jù)元算機 的表達----數(shù)據(jù)的間的特定關(guān)系在計結(jié)構(gòu)③

為解決問題而對數(shù)據(jù)施加的一組操作----數(shù)據(jù)的運算集合1.2

基本概念和術(shù)語5.數(shù)據(jù)結(jié)構(gòu)(Data

Structure)的含義沒有被一致公認(rèn)的定義。具有三個層面的含義：①

問題所涉及的數(shù)據(jù)對象，以及數(shù)據(jù)對象

各個數(shù)據(jù)元 間的特定關(guān)系----數(shù)據(jù)的邏輯結(jié)構(gòu)其中,

D:一個數(shù)據(jù)對象D={di

|i=1,2,…,n,

n≥0}S:

D內(nèi)數(shù)據(jù)元 間存在的關(guān)系的集合S={sj

|j=1,2,…,m,

m≥1}關(guān)系sj——數(shù)據(jù)元素序偶的集合邏輯結(jié)構(gòu)面向問題，與計算機無關(guān)1.2

基本概念和術(shù)語數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一個二元組來描述:DS=(D,

S)序偶:兩個數(shù)據(jù)元素X和Y之間存在某種特定關(guān)系(如圖a所示)稱為一個序偶，記為<X,

Y>。這里，X稱為Y的直接前驅(qū)；Y稱為X的直接后繼。如果這種關(guān)系是對稱的，也就是說如果存在<X,Y>,就必然有<Y,X>,則記為(X,Y),圖b表示。X圖a圖bYXY1.2

基本概念和術(shù)語<x,

y>（x,

y）舉例：描述6個城市之間的關(guān)系DS=(D,

S)D={

A,

B,

C,

D,

E,

F}S={

s1,

s2,

s3}s1={<A,

B>,

<A,

C>,

<B,

D>,

<B,

E>,

<C,

F>}s2={(A,

B),

(A,

C),

(A,

D),

(B,

C),

(C,

F),

(B,

E)}s3={(A,

B),

(A,

C),

(E,

F),

(B,

D),

(C,

F),

(B,

E)}AFDEs1的圖示CBDs2的圖示CA

B

FE--行政隸屬關(guān)系--公路交通關(guān)系--地理鄰接關(guān)系A(chǔ)DB

CEFs3的圖示幾種常用的數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）：線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)1.2

基本概念和術(shù)語據(jù)元

間存在的關(guān)系。常用的

技術(shù)有：順序 、鏈?zhǔn)?、散列、索引結(jié)構(gòu)面向計算機數(shù)據(jù)的

結(jié)構(gòu)將問題所涉及的數(shù)據(jù)對象中的所有數(shù)據(jù)元素存入計算機，并且在計算機

表達出數(shù)1.2

基本概念和術(shù)語既面向問題又面向計算機：操作集合的定義由問題決定；

操作的實現(xiàn)與數(shù)據(jù)在計算機內(nèi)的方式有關(guān)。數(shù)據(jù)的運算集合對數(shù)據(jù)進行加工和處理的一組算法1.2

基本概念和術(shù)語6.數(shù)據(jù)類型(Data

Type)高級語言的數(shù)據(jù)類型涉及兩個層面的含義：值的集合——數(shù)據(jù)的特征，取值范圍等如int，float操作的集合——對值集定義的一組運算int型：

+,

-,

*,

/,

%

…float型：+,

-,

*,

/…高級語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型稱為固有數(shù)據(jù)類型，只能 簡單的數(shù)據(jù)1.2

基本概念和術(shù)語高級語言提供的數(shù)據(jù)類型使在編程時不用考慮每種數(shù)據(jù)在計算機的細(xì)節(jié)和運算的實現(xiàn)細(xì)節(jié)，直接按照數(shù)據(jù)類型的外部抽象數(shù)學(xué)特性來使用數(shù)據(jù)，大大方便了程序設(shè)計。1.2

基本概念和術(shù)語7.抽象數(shù)據(jù)類型

ADT( Data

Type)一個數(shù)學(xué)模型以及定義在該模型上的一組操作；本課程用ADT來描述數(shù)據(jù)結(jié)構(gòu)ADT可用三元組表示：(D,S,P

)其中： D——

數(shù)據(jù)對象S

——

D中數(shù)據(jù)元 間的關(guān)系P——對D的基本操作的集合1.2

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

基本概念和術(shù)語

高級語言中的固有數(shù)據(jù)類型（如int、float等）只能

簡單的數(shù)據(jù)。用戶在解決實際問題時往往需要構(gòu)建一些復(fù)雜的數(shù)據(jù)類型——描述該數(shù)據(jù)類型的數(shù)學(xué)特性，為它定義一組操作。這正是抽象數(shù)據(jù)類型的建模方法。1.2

基本概念和術(shù)語抽象數(shù)據(jù)類型的定義只涉及數(shù)學(xué)模型的邏輯特性，而不涉及該模型的具體實現(xiàn)細(xì)節(jié)。不管采用什么技術(shù)方法來實現(xiàn)這個抽象數(shù)據(jù)類型，只要模型的數(shù)學(xué)特性不變，都不會影響它的外部使用。從而使外部使用和實現(xiàn)分離?！俺橄蟆钡哪康木褪亲屓藗兗芯Π盐諉栴}的本質(zhì)，研究解決問題的算法，拋開繁瑣的實現(xiàn)細(xì)節(jié)，從而使問題得到簡化?！俺橄蟆笨梢园匆欢ǖ膶哟沃鸩教岣叱橄蟮某潭取哟卧礁?，細(xì)節(jié)就越少，使用就越方便。本課程中定義ADT的格式為：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<對數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<對數(shù)據(jù)關(guān)系的定義>基本操作：<對基本操作的定義>}ADT抽象數(shù)據(jù)類型名1.2

基本概念和術(shù)語基本操作的定義格式為：基本操作名(參數(shù)表)初始條件：<初始條件的描述>

——描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件。初始條件可以為空。操作結(jié)果：<操作結(jié)果的描述>

—出口—說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。1.2

基本概念和術(shù)語舉例:抽象數(shù)據(jù)類型復(fù)數(shù)的定義ADTComplex{數(shù)據(jù)對象：D＝{e1,e2|eiRealSet}數(shù)據(jù)關(guān)系：R1＝{<e1,e2>|e1是實部，e2是虛部}基本操作：plex(&Z,v1,v2)操作結(jié)果：構(gòu)造了復(fù)數(shù)Z,實部和虛部分別賦予參數(shù)v1和v2的值GetReal(Z，&RealPart)初始條件：復(fù)數(shù)Z已經(jīng)存在操作結(jié)果：用參數(shù)RealPart返回實部值GetImag(Z，&ImagPart)初始條件：復(fù)數(shù)Z已經(jīng)存在操作結(jié)果：用參數(shù)ImagPart返回虛部值e1

e2Add(z1,z2,&sum)初始條件：復(fù)數(shù)z1和z2已經(jīng)存在操作結(jié)果：用參數(shù)sum返回z1與z2的和值Subtract(z1,z2,&sub)初始條件：復(fù)數(shù)z1和z2已經(jīng)存在操作結(jié)果：用參數(shù)sub返回z1與z2的差值Multiply(z1,z2,&mult)初始條件：復(fù)數(shù)z1和z2已經(jīng)存在操作結(jié)果：用參數(shù)mult返回z1與z2的積值Division(z1,z2,&div)初始條件：復(fù)數(shù)z1和z2已經(jīng)存在操作結(jié)果：用參數(shù)div返回z1，z2的商值}ADT

Complex小結(jié)：數(shù)據(jù)(Data)數(shù)據(jù)元素

(Data Element

)數(shù)據(jù)項(DataItem)數(shù)據(jù)對象

(

Data Object

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

(

Data

Structure)數(shù)據(jù)類型

(

Data Type

)抽象數(shù)據(jù)類型

( Data

Type

)1.2

基本概念和術(shù)語第一章 緒論內(nèi)容提要1.1數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法和算法分析抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。言的虛擬層次上在高級程序設(shè)計語抽象數(shù)據(jù)類型的，采用類C語言作為描述表示

工具。1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)類C語言采用了標(biāo)準(zhǔn)C語言的語法結(jié)構(gòu)，同時對

一些語法細(xì)節(jié)進行了簡化，并添加了一些描述方法。用類C寫的代碼是偽代碼。因為不完全符合C語言的規(guī)范，所以不能被C編譯器編譯。類C語言簡介1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)類C語言簡介和本 中的一些約定：1.

本 中約定的一些預(yù)定義常量和類型constTRUE=1;真constFALSE=0;假constOK=1;算法正常完成的狀態(tài)constERROR=0算法執(zhí)行出錯的狀態(tài)constINFEASIBLE=-1;算法不可實現(xiàn)的狀態(tài)constOVERFLOW=-2;溢出的狀態(tài)typedef

int

Status

;Status作為類型名，專門用來說明函數(shù)返回值的類型，其值是函數(shù)執(zhí)行結(jié)果的狀態(tài)代碼。1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)2.結(jié)構(gòu)用類型定義(typedef)描述數(shù)據(jù)元素（結(jié)點）的類型名約定為ElemType1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)3.操作算法用以下形式的函數(shù)描述函數(shù)返回值類型 函數(shù)名(參數(shù)表){//對算法的文字說明函數(shù)語句序列}//函數(shù)名1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)4.賦值語句的格式變量名=表達式;變量名1=變量名2=

...=變量名k=表達式;簡單賦值:串聯(lián)賦值:成組賦值:結(jié)構(gòu)體名=結(jié)構(gòu)體名;{變量名1,

...

,

變量名k

}={值1,

...

,值k};

數(shù)組名[]=表達式;

—對整個數(shù)組賦值數(shù)組名[起始下標(biāo)..終止下標(biāo)]=數(shù)組名[起始下標(biāo)..終止下標(biāo)];交換賦值:

變量名變量名;

條件賦值:

條件表達式?表達式T:表達式F;

1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)5.選擇語句條件語句1:if(條件表達式)語句T;條件語句2:if(條件表達式)else

語句F;語句T;1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)開關(guān)語句:格式1:switch(表達式){語句序列1;

break;語句序列2;

break;語句序列n;

break;語句序列n+1;case

值1:case

值2:...case

值n:default:}格式2:switch

{case

條件1:語句序列1;break;case

條件2:語句序列2;break;...case

條件n:語句序列n;break;default:

語句序列n+1;}1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)6.循環(huán)語句for語句

:for(

賦初值句;條件;修改句)語句;while語句:while(條件)語句;do-while語句:do

{語句序列;while(條件);1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)7.結(jié)束語句函數(shù)結(jié)束語句:return;

或

return(表達式);case結(jié)束語句:break;異常結(jié)束語句:exit(錯誤代碼);1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)8.輸入輸出語句輸入語句:cin>>變量1>>變量2>>...>>變量n;scanf(“格式串”,變量1,...,變量n);scanf(變量1,...,變量n);輸出語句:cout<<變量1<<變量2<<...<<變量n;printf(“格式串”,變量1,...,變量n);printf(變量1,...,變量n);1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)9.注釋語句單行注釋://注釋文字1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)10.基本函數(shù)求最大值:求最小值:求絕對值:min(表達式1,...,abs(表達式)求不足整數(shù)值:求進位整數(shù)值:判定文件結(jié)束:判定行結(jié)束:floor(表達式)

或

表達式ceil(表達式)

或

表達式

eof(文件變量)

或

eofeoln(文件變量)

或

eolnfloor(5.8)=5或

5.8

=5max(表達式1,...,ceil(5.1)=6或

5.1

=61.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)11.邏輯運算約定與運算&&:條件表達式A

&&

條件表達式B當(dāng)條件表達式A為假時,不再對條件表達式B求值或運算

||

:條件表達式A

||

條件表達式B當(dāng)條件表達式A為真時,不再對條件表達式B求值1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)12.內(nèi)存的動態(tài)分配與分配空間：指針變量=new

數(shù)據(jù)類型;指針變量=(強制指針類型)malloc(分配長度);指針變量=(強制指針類型)realloc(老基址，新分配的長度);空間：delete

指針變量; delete

[]

指針變量;free(指針變量);1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)realloc函數(shù)的使用：改變數(shù)組空間的大?。ㄔ龌驕p）int

*a=(int*)malloc(sizeof(int)*10),*b;……b=(int*)realloc(a,

sizeof(int)*15);申請新數(shù)組空間2468a5

6

7

8

9b0

1

2

3

4

5

6

7

8

9

10

11

12

13

14老數(shù)組的內(nèi)容老數(shù)組的空間1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)12.

關(guān)于“

參數(shù)”在函數(shù)參數(shù)表中，參數(shù)的前面可以加符號“&”修飾，表示該參數(shù)為

參數(shù)(變參)。在函數(shù)體內(nèi)，如果對

參數(shù)的值進行了修改，這個變化能夠傳遞到相應(yīng)的實參。沒有用“&”修飾的參數(shù)是值參。參數(shù)可以用來作為傳遞運算結(jié)果的管道1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)例:

void add(int

x,

int

&y)

{x++;

y++;}void

main(void

){

int

a=0, b=0

;add

(a,

b);printf(“a=%d,

b=%d”,

a,

b);}打?。篴=0,b=1Demos:指針的與指向指針的指針.cpp1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)舉例：ADT

Complex的類C表示typedef

struct{

//復(fù)數(shù)類型定義float

real,imag;}complex;status//復(fù)數(shù)初始化z.real=v1;return

OK;}plex(complex

&z,

float

v1,

float

v2){z.imag=v2;1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)Status

GetReal(complex

z,

float

&RealPart)

{//取得已知復(fù)數(shù)z的實部RealPart，并返回OKRealPart=z.real;return

OK;}Status

GetImag(complex

z,

float

&ImagPart)

{//取得已知復(fù)數(shù)z的虛部ImagPart，并返回OKImagPart=z.imag;return

OK;}1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)Status

Add(complex

z1,

complex

z2,

complex

&sum)

{//求得兩個復(fù)數(shù)z1和z2的和sum，并返回OKsum.real=z1.real

+

z2.real;sum.imag=z1.imag

+

z2.imag;return

OK;}Status

Subtract(complex

plex//求得兩個復(fù)數(shù)z1和z2的差sub，并返回OKsub.real=z1.real

-

z2.real;sub.imag=z1.imag

-

z2.imag;return

OK;plex

&sub){}1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)Status

Multiply(complex

z1,

complex

z2,complex

&mult){//求得兩個復(fù)數(shù)z1和z2的積mult，并返回OKmult.real=z1.real*z2.real-z1.imag*z2.imag;mult.imag=z1.real*z2.imag+z2.real*z1.imag;return

OK;}1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)Status

Division(complex

z1,

complex

z2,complex

&div){//求得復(fù)數(shù)z1除以復(fù)數(shù)z2的商div，并返回OK//float

temp;if(z2.real==0&&z2.imag==0)

return

ERROR;temp=z2.real*z2.real+z2.imag*z2.imag;div.real=(z1.real*z2.real+z1.imag*z2.imag)/temp;div.imag=(z2.real*z1.imag-z1.real*z2.imag)/temp;return

OK;}1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)第一章 緒論本章內(nèi)容提要用數(shù)據(jù)結(jié)構(gòu)方法解決的問題基本概念和術(shù)語類C語言簡介算法和算法分析算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。1.4

算法和算法分析算法（Algorithm）的定義算法必須滿足的五個重要特性：(P13)有窮性：算法必須能在執(zhí)行有窮步驟之后結(jié)束，每一步驟都能在有限時間內(nèi)完成；確定性：算法的每一個步驟必須是確切定義的。并且，對于一種輸入，算法只有一條執(zhí)行路徑，即對于相同的輸入只能得到相同的輸出；可行性：算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)；

(4)有輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。(5)有輸出：它是一組與“輸入”有確定關(guān)系的量值，是算法進行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。1.4

算法和算法分析算法的描述:本書采用類C語言描述－－比C語言的細(xì)

節(jié)簡單，可讀性強，而且做簡單的修改就可以轉(zhuǎn)換成可以編譯調(diào)試的C程序。算法的要求：正確性，可讀性，健壯性，高效率1.4

算法和算法分析算法效率分析：時間耗費：(漸進)時間復(fù)雜度空間耗費：(漸進)空間復(fù)雜度1.4

算法和算法分析算法的時間分析：語句的頻度：算法中某條語句重復(fù)執(zhí)行的次數(shù)稱為該語句的頻度。算法的時間耗費:i

1其中，ti—語句i執(zhí)行一次所耗費的時間m—算法中可執(zhí)行語句的個數(shù)mT

語句i的頻度

ti1.4

算法和算法分析m語句執(zhí)行的時間ti與機器的性能有關(guān)，與編譯程序的代碼質(zhì)量有關(guān)，與語句的種類有關(guān)。為了排除這些與算法無關(guān)的因素，取ti＝單位1。這樣算法的時間耗費T就簡化為統(tǒng)計算法中所有語句的執(zhí)行次數(shù)：T

語句i的頻度i

1—算法的時間復(fù)雜度在很多情況下，T是問題規(guī)模n的函數(shù)：T(n)1.4

算法和算法分析計算n階方陣的乘積C＝A×Bfor(i=1;

i<=n;

i++)(n+1)次for(j

=1;

j<=n;

j++){n(n+1)次C[i][j]=0;n2次for(k=1;

k<=n;k++)n2(n+1)次C[i][j]+=A[i][k]*B[k][j];n3次}T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+11.4

算法和算法分析希望用一個與T(n)同階的簡單函數(shù)表示算法的時間耗費：設(shè)f(n)是一個已知的簡單函數(shù)，且滿足lim

T

(n)

常數(shù)Cf

(n)n則T(n)與f(n)同階，記為T(n)=O(f(n))。O是Order（數(shù)量級）的第一個字母，它允許用“＝”代替“≈”。如：n3+3n2+2n=O(n3)1.4

算法和算法分析1.4

算法和算法分析用O(f(n))來做為算法時間耗費的度量，稱為算法的漸進時間復(fù)雜度，簡稱為算法的時間復(fù)雜度。對于前面的T(n)=2n3+3n2+2n+1,可記為:T