數(shù)據(jù)結(jié)構(gòu) CH1 緒論 12-02-19

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)2001vb@163.com山東理工大學(xué)·理學(xué)院殷超山東理工大學(xué)·理學(xué)院殷超···引言《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)學(xué)科的核心課程，是一門專業(yè)技術(shù)基礎(chǔ)課。學(xué)科目的:了解數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法和把現(xiàn)實(shí)世界中的問題在計(jì)算機(jī)內(nèi)部表示的方法；及培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。先修課程:計(jì)算機(jī)文化基礎(chǔ)、C語言程序設(shè)計(jì)

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

程序設(shè)計(jì)語言課的區(qū)別C語言：側(cè)重通過編寫具體的程序而理解、把握語言的特性及語言的運(yùn)用。數(shù)據(jù)結(jié)構(gòu)：側(cè)重于數(shù)據(jù)的組織形式及在此基礎(chǔ)上解決問題的策略和方法（算法）。

算法與

程序的區(qū)別什么是算法？程序的對(duì)象？算法的對(duì)象？算法的真正意圖？可讀性與抽象性第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念1.3算法和算法的度量一、計(jì)算機(jī)解決問題的步驟問題

(分析)(數(shù)學(xué))模型(技巧)

算法(語言)

程序調(diào)試運(yùn)行

1.1什么是數(shù)據(jù)結(jié)構(gòu)

Algorithm

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

為計(jì)算機(jī)處理問題編制的一組指令集。

處理問題的策略。問題的(數(shù)學(xué))模型。許多實(shí)際問題可以通過抽象出一個(gè)數(shù)學(xué)模型，用數(shù)學(xué)方法加以解決。如：求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型為線性方程組；預(yù)報(bào)人口增長(zhǎng)的數(shù)學(xué)模型為微分方程。然而，還有很多非數(shù)值計(jì)算問題不能描述成數(shù)學(xué)語言，下面我們來看幾個(gè)例子：算法+數(shù)據(jù)結(jié)構(gòu)=程序N.維爾特

（NiklausWirth)教授提出：NiklausWirth(1934--)是一位瑞士的計(jì)算機(jī)科學(xué)家，他設(shè)計(jì)了有名的Pascal結(jié)構(gòu)化語言，并且在軟件工程界有許多杰出的研究。1984他獲得了有「計(jì)算機(jī)界的諾貝爾獎(jiǎng)」之稱的「圖靈獎(jiǎng)」theTuringAward。注：Wirth讀作維爾特。

2010年6月NiklausWirth應(yīng)邀訪問西北大學(xué)。耿國華-數(shù)據(jù)結(jié)構(gòu)國家精品課程例一、書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表二、非數(shù)值計(jì)算的程序設(shè)計(jì)問題登錄號(hào)分類號(hào)例二、人機(jī)對(duì)奕問題樹……..……..…...…...…...…...設(shè)某田徑比賽共有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）。設(shè)計(jì)比賽日程表，使比賽能在盡可能短的時(shí)間內(nèi)完成。例三、田徑比賽的時(shí)間安排問題（1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米

A B CDE F（2）用頂點(diǎn)代表比賽項(xiàng)目;（3）在不能同時(shí)進(jìn)行比賽的頂點(diǎn)之間連上一條邊;

（同一選手參加的項(xiàng)目之間必定有邊相連）（4）給頂點(diǎn)涂色：任何有邊相連的頂點(diǎn)不能涂同一種顏色，且使涂色數(shù)目盡量少。解法如下：姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一ABE劉二CD

張三CEF李四DFA王五BF比賽時(shí)間比賽項(xiàng)目1A,C2B,D3E4F只需安排四個(gè)單位時(shí)間進(jìn)行比賽BCDEAFBDECAF圖例四、多叉路口交通燈管理問題圖EDABCABACADBABCBDDADBDCEAEBECED

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。概括地說，1.1結(jié)束1.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)(數(shù)值、字符等)的集合。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素:如:整數(shù)“5”,字符“N”，棋盤的一個(gè)“格局”等。

其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。例如：描述一個(gè)學(xué)生的數(shù)據(jù)元素稱之為組合項(xiàng)原子項(xiàng)姓名學(xué)號(hào)班級(jí)性別出生日期入學(xué)成績(jī)年月日數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合有一個(gè)特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。指數(shù)據(jù)元素之間存在的關(guān)系例如，可以用三個(gè)

4位的十進(jìn)制數(shù)表示一個(gè)含

12位數(shù)的十進(jìn)制數(shù)。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素a1、a2和a3

之間存在著“次序”關(guān)系

a1,a2

、

a2,a3

3214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:···序偶由某個(gè)集合中元素x與y,以確定的順序所組成的一對(duì):第一個(gè)是x,第二個(gè)是y,稱為序偶,記為<x,y>或(x,y)。平面上點(diǎn)的坐標(biāo),就是實(shí)數(shù)集的一個(gè)序偶,(3,5)與(5,3)表示不同的點(diǎn)。哈密頓*用序偶來表示復(fù)數(shù)*,這種用序偶來定義一類數(shù)的思想,已成為公理化又例，在2行3列的二維數(shù)組中{a1,a2,a3,a4,a5,a6}六個(gè)元素之間存在兩類關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

a1a2a3a4a5a6

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”。從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”

和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)

是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。數(shù)據(jù)結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。定義“班集體”為一個(gè)數(shù)據(jù)結(jié)構(gòu)Class=(D,S)D={a,b1,…,bn,c1,…cn,d1,…dn

}S={R1,R2}R1={<a,b1>,<a,c1>,<a,d1>}R2={<b1,bj>,<c1,cj>,<d1,dj>|j=2,3,…,n}例如:學(xué)生考勤事務(wù)管理系統(tǒng)（班長(zhǎng)—組長(zhǎng)—成員）設(shè)某班有一個(gè)班長(zhǎng)，三個(gè)組長(zhǎng)，每組n個(gè)成員。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關(guān)系的映象方法：（表示

x,y

的方法）順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:

令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C；通常取x存儲(chǔ)位置之后的位置（即位置相鄰）。整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。x

y鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法，

當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語言中提供的整數(shù)數(shù)組類型，

typedef

int

Long_int[3]定義長(zhǎng)整數(shù)為:再如:typedef

struct{

inty;//年號(hào)Year

intm;//月號(hào)Month

intd;//日號(hào)Day}

DateType;//日期類型定義“日期”為:定義“學(xué)生”為:typedef

struct{

charid[8];//學(xué)號(hào)

charname[16];//姓名

chargender;//性別‘M/F’:男/女

DateType

bdate;//出生日期}Student;//學(xué)生類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型二、數(shù)據(jù)類型

在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所

屬的數(shù)據(jù)類型。例如，C

語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool雙精度型double

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

是一個(gè)值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型

(AbstractDataType

簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。例如:“整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語言無關(guān)。

“抽象”的意義在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性?！ぁぁふ麛?shù)（Integer）：像-2，-1，0，1，2這樣的數(shù)稱為整數(shù)。（整數(shù)是表示物體個(gè)數(shù)的數(shù)，0表示有0個(gè)物體）整數(shù)是人類能夠掌握的最基本的數(shù)學(xué)工具。代數(shù)性質(zhì)

下表給出任何整數(shù)a，b和c的加法和乘法的基本性質(zhì)。

分配律a×(b+c)=(a×b)+(a×c)抽象數(shù)據(jù)類型還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個(gè)相對(duì)獨(dú)立的模塊時(shí)，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內(nèi)部給出它們的表示和實(shí)現(xiàn)細(xì)節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。例例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,z3)操作的結(jié)果z3=z1+z2即為：ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）；數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對(duì)象，

S是D上的關(guān)系的集合，

P是對(duì)D的基本操作的集合。ADT

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

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

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

賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。若初始條件為空，則省略之。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)typedef

struct{

float

realpart；

float

imagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

AssignComplex(complex&Z,

float

realval,float

imagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值float

GetReal(cpmplexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

GetImag(cpmplexZ)；

//返回復(fù)數(shù)Z的虛部值voidAdd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和//-----基本操作的實(shí)現(xiàn)voidAdd(complexz1,complexz2,complex&sum){

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;

sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略

}回顧數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或幾種特定關(guān)系的數(shù)據(jù)元素的集合。是一個(gè)值的集合和定義在此集合上的一組操作的總稱。抽象數(shù)據(jù)類型：是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。數(shù)據(jù)類型：

1.3算法和算法的度量一、算法二、算法設(shè)計(jì)的原則三、算法效率的度量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求

算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)滿足以下五個(gè)重要特性：1．有窮性

2．確定性3．可行性4．有輸入5．有輸出一、算法1．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；

2．確定性

對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；例1一個(gè)不是算法的例子(1)begin(2)n=1(3)n=n+1(4)repeat(3)(5)end例2一個(gè)不超過100次計(jì)數(shù)的算法(1)begin(2)n=1(3)n=n+1(4)ifn=100do(5),elserepeat(3)(5)outputn(6)end3．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；

5．有輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲(chǔ)量需求1．正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：

c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第

c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；a．程序中不含語法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；···白盒法：邏輯覆蓋（1.語句覆蓋2.判定覆蓋3.條件覆蓋4.條件判定覆蓋5.條件組合覆蓋6.路徑覆蓋）黑盒測(cè)試：等價(jià)劃分類、邊界值分析、錯(cuò)誤推測(cè)法、因果圖法。窮舉測(cè)試

2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；例：a=a＋b；

b=a－b；

a=a－b；a?b3．健壯性

當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4．高效率與低存儲(chǔ)量需求

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。兩者都與問題的規(guī)模有關(guān)。三、算法效率的度量方法和準(zhǔn)則通常有兩種度量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1、必須執(zhí)行程序

2、其它因素掩蓋算法本質(zhì)與算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。

假如，隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度···

O是數(shù)學(xué)符號(hào)，它的嚴(yán)格定義是“若T(n)和f(n)是在正整數(shù)集合上定義的兩個(gè)函數(shù)，則T(n)=O(f(n))表示存在正常數(shù)C和n0，使得當(dāng)n≥n0時(shí)，滿足0≤T(n)≤C·f(n)

”。

用容易理解的話說----這兩個(gè)函數(shù)當(dāng)整型自變量n趨向于無窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對(duì)于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。例一兩個(gè)矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

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];

}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)例二選擇排序

void

select_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sort基本操作:

比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:

O(n2)j=i;//

選擇第i個(gè)最小元素,為什么不是0或其它值for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;if(j!=i)a[j]←→

a[i]for(i=0;i<n-1;++i){}練習(xí)voidtemp(){

x＝91；

y＝100；

whiley＞0

{ifx＞100

{x＝x–10；

y––；

}

elsex＋＋；

}}//temp求時(shí)間復(fù)雜度

T(n)=O(1),這個(gè)程序總共循環(huán)運(yùn)行了1100次,但是我們看到n沒有？沒有。這段程序的運(yùn)行是和n無關(guān)的,就算再循環(huán)一萬年,它也只是一個(gè)常數(shù)階的函數(shù)。解答：If語句的執(zhí)行次數(shù)：voidtemp(){x＝91；

y＝100；

whiley＞0

{ifx＞100

{x＝x–10；

y––；

}

elsex＋＋；

}

}//temp執(zhí)行后xy1次921002次93100…9次10010010次10110011次9199…21次1019922次9199…33次9198……1109190……1100910四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與f(n)的增長(zhǎng)率相同。S(n)=O(f(n))算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間3．輔助變量所占空間

若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。