數據結構：第1章 緒論

1、第第1章章 緒論緒論 1.2 算法及其描述算法及其描述 1.1 什么是數據結構什么是數據結構1.3 算法分析算法分析 本章小結本章小結1.4 數據結構算法程序數據結構算法程序 1.1.1 1.1.1 數據結構的定義數據結構的定義1.1.2 1.1.2 邏輯結構類型邏輯結構類型 1.1.3 1.1.3 存儲結構類型存儲結構類型1.1.4 1.1.4 數據結構和數據類型數據結構和數據類型 1.1 1.1 什么是數據結構什么是數據結構 數據數據：是所有能被輸入到計算機中是所有能被輸入到計算機中, ,且能被計算且能被計算機處理的符號的集合。它是計算機操作的對象的總機處理的符號的集合。它是計算機操作的對

2、象的總稱稱, ,也是計算機處理的信息的某種特定的符號表示也是計算機處理的信息的某種特定的符號表示形式。形式。 數據元素數據元素：是數據：是數據(集合集合)中的一個中的一個“個體個體”,是數是數據的基本單位。據的基本單位。 1.1.1 1.1.1 數據結構的定義數據結構的定義 數據項數據項：是具有獨立含義的數據最小單位，也稱：是具有獨立含義的數據最小單位，也稱字段或域。字段或域。 例如例如,某班中每個學生數據記錄都是一個數據元某班中每個學生數據記錄都是一個數據元素素, 而其中的而其中的“張三張三”是一個數據項是一個數據項)。 數據結構：是指數據結構：是指數據數據以及數據元素相互之間的以及數據元素

3、相互之間的聯系聯系。可以看作是相互之間存在著某種特定關系的數據元素可以看作是相互之間存在著某種特定關系的數據元素的集合。的集合。 因此因此,可時把數據結構看成是帶結構的數據元素的可時把數據結構看成是帶結構的數據元素的集合。集合。 數據結構包括如下幾個方面：數據結構包括如下幾個方面： (1) 數據元素之間的邏輯關系數據元素之間的邏輯關系,即數據的邏輯結構。即數據的邏輯結構。 (2) 數據元素及其關系在計算機存儲器中的存儲數據元素及其關系在計算機存儲器中的存儲方式方式,即數據的存儲結構即數據的存儲結構,也稱為數據的物理結構。也稱為數據的物理結構。 (3) 施加在該數據上的操作施加在該數據上的操作,

4、即數據的運算即數據的運算。 例例1.1 有一個學生表如表有一個學生表如表1.1所示。這個表中所示。這個表中的數據元素是學生記錄的數據元素是學生記錄,每個數據元素由四個數每個數據元素由四個數據項據項(即學號、姓別、性別和班號即學號、姓別、性別和班號)組成。組成。學號學號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強董強男男99025王萍王萍女女9901表表1.1 學生表學生表 該表中的記錄順序反映了數據元素之間的邏輯關系該表中的記錄順序反映了數據元素之間的邏輯關系, , 用學號標識每個學生記錄用

5、學號標識每個學生記錄, ,這種邏輯關系可以表示為：這種邏輯關系可以表示為： , 其中尖括號其中尖括號“”表示元素表示元素ai和和ai+1之間是相鄰之間是相鄰的的,即即ai在在ai+1之前之前,ai+1在在ai之后。之后。 數據數據在計算機存儲器中的存儲方式就是在計算機存儲器中的存儲方式就是存儲存儲結構結構。 C/C+語言中，通常采用結構體數組和鏈表兩語言中，通常采用結構體數組和鏈表兩種方式實現其存儲結構。種方式實現其存儲結構。存放學生表的結構體數組存放學生表的結構體數組Stud定義為：定義為： struct int no; /*存儲學號存儲學號*/ char name8; /*存儲姓名存儲姓名

6、*/ char sex2; /*存儲性別存儲性別*/ char class4; /*存儲班號存儲班號*/ Stud7=1,“張斌張斌”,“男男”,“9901”, 5,王萍王萍,女女,9901; 結構體數組結構體數組Stud各元素在內存中順序存放各元素在內存中順序存放,即即第第i(1i6)個學生對應的元素個學生對應的元素Studi存放在第存放在第i+1個學生對應的元素個學生對應的元素Studi+1之前之前,Studi+1正好正好在在Studi之后。之后。9901女王萍59901男張斌張斌1Stud0Stud6Stud數組起始地址數組起始地址 存放學生表的鏈表的結點類型存放學生表的鏈表的結點類型S

7、tudType定義為：定義為： typedef struct studnode int no; /*存儲學號存儲學號*/ char name8; /*存儲姓名存儲姓名*/ char sex2; /*存儲性別存儲性別*/ char class4; /*存儲班號存儲班號*/ struct studnode *next; /*存儲指向下一個學生的指針存儲指向下一個學生的指針*/ StudType；鏈表首結點地址鏈表首結點地址headhead1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強董強男男 99025王萍王萍

8、女女 9901 學生表構成的鏈學生表構成的鏈表如右圖所示。其表如右圖所示。其中的中的head為第一個為第一個數據元素的指針。數據元素的指針。 學生表構成的鏈表學生表構成的鏈表 對于對于“學生表學生表”這種數據結構這種數據結構, ,可以進行一系列可以進行一系列的運算的運算, ,例如例如, ,增加一個學生記錄、刪除一個學生記增加一個學生記錄、刪除一個學生記錄、查找性別為錄、查找性別為“女女”的學生記錄、查找班號為的學生記錄、查找班號為“99029902”的學生記錄等等。的學生記錄等等。 從前面介紹的兩種存儲結構看到從前面介紹的兩種存儲結構看到, ,同樣的運算同樣的運算, ,在不同的存儲結構中在不同

9、的存儲結構中, ,其實現過程是不同的。其實現過程是不同的。 例如例如,查找學號為查找學號為20的學生的姓名的學生的姓名： 對于對于Stud數組數組,可以從可以從Stud0開始比較開始比較,Stud0.no不等于不等于20,再與再與Stud1.no比較比較,直到直到Stud3.no等于等于20,返回返回S。 對于對于head為首結點指針的鏈表為首結點指針的鏈表,從從head所指結點開所指結點開始比較始比較,head-no不等于不等于20,從它的從它的next得到下一個結點得到下一個結點的地址的地址,再與下一個結點的再與下一個結點的no域比較域比較,直到某結點的直到某結點的no域

10、等于域等于20,返回其返回其name域域。 為了更確切地描述一種數據結構為了更確切地描述一種數據結構,通常采用二通常采用二元組表示：元組表示： B=(D,R) 其中其中,B是一種數據結構是一種數據結構,它由數據元素的集合它由數據元素的集合D和和D上二元關系的集合上二元關系的集合R所組成。其中：所組成。其中： D=di| 1in,n0 R=rj| 1jm,m0 邏輯結構的描述或表示：邏輯結構的描述或表示： 其中：其中： di表示集合表示集合D中的第中的第i個結點或數據元素。個結點或數據元素。 n為為D中結點的個數中結點的個數,特別地特別地,若若n=0,則則D是一個空是一個空集集,因而因而B也就無

11、結構可言也就無結構可言,有時也可以認為它具有任有時也可以認為它具有任一結構。一結構。 rj表示集合表示集合R中的第中的第j個二元關系個二元關系(后面均簡稱關后面均簡稱關系系)。 m為為R中關系的個數中關系的個數,特別地特別地,若若m=0,則則R是一個空是一個空集集,表明集合表明集合D中的元結點間不存在任何關系中的元結點間不存在任何關系,彼此是彼此是獨立的。獨立的。 序偶序偶(x,yD) x為第一結點為第一結點,y為第二結點。為第二結點。 x為為y的的直接前驅結點直接前驅結點(通常簡稱通常簡稱前驅結點前驅結點) y為為x的的直接后繼結點直接后繼結點(通常簡稱通常簡稱后繼結點后繼結點)。 若某個結

12、點沒有前驅結點若某個結點沒有前驅結點,則稱該結點為則稱該結點為開始結點開始結點；若某個結點沒有后繼結點若某個結點沒有后繼結點,則稱該結點為則稱該結點為終端結點終端結點。 說明：說明：表示有向關系，表示有向關系，(x,y)表示無向表示無向關系。采用離散數學的表示方法。關系。采用離散數學的表示方法。 例如例如,采用二元組表示例采用二元組表示例1.1的學生表。的學生表。 學生表中共有學生表中共有7個結點個結點,依次用依次用d1d7表示表示,則對應則對應的二元組表示為的二元組表示為B=(D,R),其中：其中： D=d1,d2,d3,d4,d5,d6,d7 R=r /只有一種關系只有一種關系 r=,又例

13、如又例如, ,有如下數據即一個矩陣：有如下數據即一個矩陣： 119105471281362 對應的二元組表示為對應的二元組表示為B=(D,R),其中：其中： D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中其中,r1表示行關系表示行關系,r2表示列關系表示列關系 r1=, , r2=, , 一個二維數組一個二維數組 可以可以利用圖形形象地表示邏輯結構。利用圖形形象地表示邏輯結構。 例如，上述例如，上述“學生表學生表”數據結構用下圖的圖形數據結構用下圖的圖形表示。表示。 k1 k2 k3 k4 k5 k6 k7 學生表數據結構圖示學生表數據結構圖示 (1) 線性結構

14、線性結構 結點之間關系：結點之間關系：一對一。一對一。 特點：特點：開始結點和終端結點都是惟一的開始結點和終端結點都是惟一的, ,除了開始除了開始結點和終端結點以外結點和終端結點以外, ,其余結點都有且僅有一個前驅結其余結點都有且僅有一個前驅結點點, ,有且僅有一個后繼結點。順序表就是典型的線性結有且僅有一個后繼結點。順序表就是典型的線性結構。構。1.1.2 1.1.2 邏輯結構類型邏輯結構類型 (2) 樹形結構樹形結構 結點之間關系：結點之間關系：一對多。一對多。 特點：特點：開始結點惟一開始結點惟一, ,終端結點不惟一。除終端結點不惟一。除終端結點以外終端結點以外, ,每個結點有一個或多個

15、后續(xù)結每個結點有一個或多個后續(xù)結點；除開始結點外，每個結點有且僅有一個前點；除開始結點外，每個結點有且僅有一個前驅結點。驅結點。例例 人機對奕問題樹結構樹結構.將每個棋局都抽象成一個結點：將每個棋局都抽象成一個結點：棋局棋局1棋局棋局2棋局棋局3棋局棋局4棋局棋局5棋局棋局6棋局棋局7棋局棋局8棋局棋局9棋局棋局10整體：是一個數據結構，叫整體：是一個數據結構，叫“樹結構樹結構”運算：遍歷整棵樹，找出運算：遍歷整棵樹，找出“贏贏”的路線；等的路線；等 (3) 圖形結構圖形結構 結點之間關系：結點之間關系：多對多。多對多。 特點：特點：沒有開始結點和終端結點，所有結沒有開始結點和終端結點，所有結

16、點都可能有多個前驅結點和多個后繼結點。點都可能有多個前驅結點和多個后繼結點。 例：例：田徑賽的時間安排問題田徑賽的時間安排問題: : 設有設有六個六個比賽比賽項目項目，規(guī)定每個選，規(guī)定每個選手手至多至多可參加可參加三個項目三個項目，有，有五人五人報名報名參加參加比賽比賽（如下表所示）設計比賽日（如下表所示）設計比賽日程表，使得在盡可能短的時間內完成程表，使得在盡可能短的時間內完成比賽。比賽。姓 名 項目 1 項目 2 項目 3 丁 一 跳高 跳 遠 100 米 馬 二 標 槍 鉛 球 張 三 標 搶 100 米 200 米 李 四 鉛 球 200 米 跳 高 王 五 跳 遠 200 米 姓名姓

17、名項目項目1項目項目2項目項目3丁一丁一 A B E馬二馬二 C D 張三張三 C E F李四李四 D F A王五王五 B FAEBFDC比賽比賽時間時間比賽項目比賽項目1A，C2B，D3E4F1.1.設代號代表不同的項目設代號代表不同的項目 跳高跳高 跳遠跳遠 標槍標槍 A B C 鉛球鉛球 100米米 200米米 D E F2.2.用頂點代表比賽項目用頂點代表比賽項目: : 不能同時進行比賽的項目不能同時進行比賽的項目之間連上一條邊。之間連上一條邊。 安排安排四個單四個單位時間位時間進行比進行比賽賽AEBFDC(2) 鏈式存儲方法鏈式存儲方法 (3) 索引存儲方法索引存儲方法 (4) 散列

18、存儲方法散列存儲方法 1.1.3 1.1.3 存儲結構類型存儲結構類型(1) 順序存儲方法順序存儲方法 細節(jié)省略 (1) 數據類型數據類型 高級程序語言中高級程序語言中,一般須對程序中出現的每個變量、一般須對程序中出現的每個變量、常量或表達式常量或表達式,明確說明它們所屬的數據類型。不同明確說明它們所屬的數據類型。不同類型的變量類型的變量,其所能取的值的范圍不同其所能取的值的范圍不同,所能進行的操所能進行的操作不同。作不同。 數據類型數據類型是一個值的集合和定義在此集合上的是一個值的集合和定義在此集合上的一組操作的總稱。一組操作的總稱。1.1.4 1.1.4 數據結構和數據類型數據結構和數據類

19、型 如如C/C+中的中的int就是整型數據類型。它是所有整就是整型數據類型。它是所有整數的集合數的集合(在在16位計算機中為位計算機中為3276832767的全體整的全體整數數)和相關的整數運算和相關的整數運算(如、等如、等)。C/C+其它數據類型省略 (2) 抽象數據類型抽象數據類型 抽象數據類型抽象數據類型(Abstract Data Type簡寫為簡寫為ADT)指的是用戶進行軟件系統(tǒng)設計時從問題的數學模型指的是用戶進行軟件系統(tǒng)設計時從問題的數學模型中抽象出來的邏輯數據結構和邏輯數據結構上的運中抽象出來的邏輯數據結構和邏輯數據結構上的運算算,而不考慮計算機的具體存儲結構和運算的具體實而不考

20、慮計算機的具體存儲結構和運算的具體實現算法。現算法。 抽象數據類型抽象數據類型=數據元素集合抽象運算數據元素集合抽象運算例如例如,抽象數據類型抽象數據類型復數復數的定義：的定義：ADT Complex 數據對象：數據對象： D=e1,e2|e1,e2均為實數均為實數數據關系：數據關系： R1=| e1是復數的實數部分是復數的實數部分,e2 是復數的是復數的 虛數部分虛數部分 e1e2i基本操作：基本操作： AssignComplex(&Z,v1,v2)：構造復數：構造復數Z。 DestroyComplex(&Z):復數復數Z被銷毀。被銷毀。 GetReal(Z,&rea

21、l):返回復數返回復數Z的實部值。的實部值。 GetImag(Z,&Imag):返回復數返回復數Z的虛部值。的虛部值。 Add(z1,z2,&sum):返回兩個復數返回兩個復數z1,z2的和。的和。 ADT Complex1.2 1.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述1.2.1 1.2.1 什么是算法什么是算法 數據元素之間的關系有邏輯關系和物理關系數據元素之間的關系有邏輯關系和物理關系,對應的操作對應的操作有邏輯結構上的操作功能和具體存儲結構上的操作實現。有邏輯結構上的操作功能和具體存儲結構上的操作實現。 通常把具體存

22、儲結構上的操作實現步驟或過程稱為通常把具體存儲結構上的操作實現步驟或過程稱為算法算法。廣義地說，廣義地說，算法是對特定問題求解步驟的一種描述，它是指算法是對特定問題求解步驟的一種描述，它是指令的有限序列令的有限序列，其中每個指令表示計算機的一個或多個操作，其中每個指令表示計算機的一個或多個操作。算法的五個重要的特性算法的五個重要的特性 (1) 有窮性有窮性:在有窮步之后結束。在有窮步之后結束。(2) 確定性確定性:無二義性。無二義性。 (3) 可行性可行性:可通過基本運算有限次執(zhí)行來實現?？赏ㄟ^基本運算有限次執(zhí)行來實現。(4) 有輸入有輸入 (5) 有輸出有輸出 例例1.2 考慮下列兩段描述：

23、考慮下列兩段描述：(1) 描述一描述一void exam1() n2; while (n%20) nn+2; printf(%dn,n);華中科大考研題華中科大考研題 (2) 描述二描述二void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 這兩段描述均不能滿足算法的特征這兩段描述均不能滿足算法的特征,試問它們試問它們違反了哪些特征？違反了哪些特征？ 解：解：(1)算法是一個死循環(huán)算法是一個死循環(huán),違反了算法的有窮違反了算法的有窮性特征。性特征。 (2)算法包含除零錯誤算法包含除零錯誤,違反了算法的可行性特征。違反了算法的可行性特征。 1.2.2 1.2

24、.2 算法描述算法描述 本書中采用本書中采用C/C+C/C+語言描述算法。語言描述算法。 說明：說明：C+語言中提供了一種語言中提供了一種引用引用運算符運算符“&”,引用是個別名引用是個別名,當建立引用時當建立引用時,程序用另一個程序用另一個已定義的變量或對象已定義的變量或對象(目標目標)的名字初始化它的名字初始化它,從那從那時起時起,引用作為目標的別名而使用引用作為目標的別名而使用,對引用的改動對引用的改動實際就是對目標的改動。實際就是對目標的改動。 注意：注意：Turbo C不支持引用類型。不支持引用類型。 編寫一個函數編寫一個函數swap1(x,y)，當執(zhí)行語句，當執(zhí)行語句swa

25、p1(a,b)時時,交換交換a和和b的值。的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：注意：a a和和b b的值不會發(fā)生了交換。的值不會發(fā)生了交換。 為此，采用指針的方式來回傳形參的值，需將上為此，采用指針的方式來回傳形參的值，需將上述函數改為：述函數改為： void swap2(int *x,int *y) int tmp; tmp=*x;/*將將x的值放在的值放在tmp中中*/ *x=*y; /*將將x所指的值改為所指的值改為*y*/ *y=tmp； /*將將y所指的值改為所指的值改為tmp*/ 上述函數的調用改為上述函

26、數的調用改為swap2(&a,&b)，顯然遠不，顯然遠不如采用引用方式簡潔。所以本書后面很多算法都采如采用引用方式簡潔。所以本書后面很多算法都采用引用形參。用引用形參。引入引入“引用引用”的概念的概念例如：例如： int a=4; /*a為普通的整型變量為普通的整型變量*/ int &b=a; /*b是是a的引用變量的引用變量*/ 這里說明這里說明b變量是變量變量是變量a的引用的引用,b也等于也等于4,之后之后這兩個變量同步改變。當這兩個變量同步改變。當a改變時改變時b也同步改變，也同步改變，同樣，當同樣，當b改變時改變時a也同步改變。也同步改變。難點難點main()

27、int a=2; int &b=a; printf(a=%d,b=%dn,a,b); /*輸出：輸出：a=2,b=2*/ b+; printf(a=%d,b=%dn,a,b); /*輸出：輸出：a=3,b=3*/ a+; printf(a=%d,b=%dn,a,b); /*輸出：輸出：a=4,b=4*/ 引用引用常用于函數形參中常用于函數形參中,采用引用型形參時采用引用型形參時,在函數在函數調用時將形參的改變回傳給實參調用時將形參的改變回傳給實參,例如例如,有如下函數有如下函數(其其中的形參均為引用型形參中的形參均為引用型形參)： void swap(int &x,int &a

28、mp;y) /*形參前的形參前的“&”符號不是指針運算符符號不是指針運算符*/ int tmp=x; x=y;y=tmp 當用執(zhí)行語句當用執(zhí)行語句swap(a,b)時時,a和和b的值發(fā)生了交換。的值發(fā)生了交換。 例例1.3 編寫一個算法編寫一個算法, 讀入三個整數讀入三個整數x,y和和z的值的值,要要求從大到小輸出這三個數。求從大到小輸出這三個數。 解：依次輸入解：依次輸入x,y和和z這三個整數這三個整數,通過比較交換后通過比較交換后,使得使得xyz,然后輸出然后輸出x,y,z。 在算法中應考慮對這三個元素作盡可能少的比較在算法中應考慮對這三個元素作盡可能少的比較和移動和移動,如下述算

29、法在最壞的情況下只需進行如下述算法在最壞的情況下只需進行3次比較次比較和和7次移動。次移動。void Descending() printf(輸入輸入x,y,z); scanf(%d,%d,%d,&x,&y,&z); if (x=y*/ if (yz*/ if (x=temp) y=temp； else y=x;x=temp; printf(%d,%d,%dn,x,y,z); 1.3 1.3 算法分析算法分析 1.3.1 算法設計的目標算法設計的目標 1.3.2 算法效率分析算法效率分析 1.3.3 算法存儲空間分析算法存儲空間分析 設計的目標：設計的目標： 正確性。要

30、求算法能正確地執(zhí)行預先規(guī)定的正確性。要求算法能正確地執(zhí)行預先規(guī)定的功能和性能要求。功能和性能要求。 可使用性。要求算法能方便地使用。也叫用可使用性。要求算法能方便地使用。也叫用戶友好性。戶友好性。 可讀性。算法應該易于理解?？勺x性。算法應該易于理解。 健壯性。能對異常數據作出特殊處理，不會健壯性。能對異常數據作出特殊處理，不會造成異常中斷或死機。造成異常中斷或死機。 高效率和低存儲量需求。高效率和低存儲量需求。1.3.1 1.3.1 算法設計的目標算法設計的目標 一個算法是由控制結構一個算法是由控制結構(順序、分支和循環(huán)順序、分支和循環(huán)三種三種)和原操作和原操作(指固有數據類型的操作指固有數據

31、類型的操作)構成的構成的,則算法時間取決于兩者的綜合效果。則算法時間取決于兩者的綜合效果。1.3.2 1.3.2 算法時間復雜度分析算法時間復雜度分析 控制語句控制語句1原操作原操作控制語句控制語句n原操作原操作一個算法一個算法 同一問題可以采用多種算法實現。如何同一問題可以采用多種算法實現。如何比較算法執(zhí)行效率？比較算法執(zhí)行效率？ 算法描述的語言不同算法描述的語言不同 算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同 其他因素其他因素 所以不能用絕對執(zhí)行時間進行比較所以不能用絕對執(zhí)行時間進行比較 為了便于比較同一問題的不同算法為了便于比較同一問題的不同算法,通常從算通常從算法中選取一種對于所研究的問題來

32、說是基本運算法中選取一種對于所研究的問題來說是基本運算的原操作的原操作(以下將基本運算的原操作簡稱為以下將基本運算的原操作簡稱為基本基本運算運算)。 算法執(zhí)行時間大致為基本運算所需的時間與算法執(zhí)行時間大致為基本運算所需的時間與其運算次數其運算次數(也稱為頻度也稱為頻度)的乘積。的乘積。 被視為算法被視為算法基本運算基本運算的一般是最深層循環(huán)內的一般是最深層循環(huán)內的語句。的語句。 在一個算法中在一個算法中, ,進行基本運算的次數越少進行基本運算的次數越少, ,其運行其運行時間也就相對地越少；基本運算次數越多時間也就相對地越少；基本運算次數越多, ,其運行時其運行時間也就相對地越多。間也就相對地越

33、多。 所以所以, ,通常把算法中包含基本運算次數的多少稱通常把算法中包含基本運算次數的多少稱為算法的時間復雜度為算法的時間復雜度, ,也就是說也就是說, ,一個算法的時間復雜一個算法的時間復雜度是指該算法的基本運算次數度是指該算法的基本運算次數。 算法中算法中基本運算次數基本運算次數T(n)是問題規(guī)模是問題規(guī)模n的某個函數的某個函數f(n),記作記作： T(n)=O(f(n) 記號記號“O”讀作讀作“大大O”,它表示隨問題規(guī)模它表示隨問題規(guī)模n的增的增大算法執(zhí)行時間的增長率和大算法執(zhí)行時間的增長率和f(n)的增長率相同。的增長率相同?！癘”的形式定義為：的形式定義為： 若若f(n)是正整數是正

34、整數n的一個函數的一個函數,則則T(n)=O(f(n)表示表示存在一個正的常數存在一個正的常數M,使得當使得當nn0時都滿足：時都滿足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的最高階的最高階,忽略其低階忽略其低階項和常系數項和常系數,這樣既可簡化這樣既可簡化T(n)的計算的計算,又能又能比較客觀地反映出當比較客觀地反映出當n很大時很大時,算法的時間性算法的時間性能。能。 例如例如,T(n)=3n2-5n+10000=O(n2)本質上講，是一種本質上講，是一種最高數量級的比較最高數量級的比較 一個沒有循環(huán)的算法的基本運算次數與問題規(guī)模一個沒有循環(huán)的算法的基本運算次數與問題

35、規(guī)模n無關無關,記作記作O(1),也稱作也稱作常數階常數階。 一個只有一重循環(huán)的算法的基本運算次數與問題一個只有一重循環(huán)的算法的基本運算次數與問題規(guī)模規(guī)模n的增長呈線性增大關系的增長呈線性增大關系,記作記作O(n),也稱也稱線性階線性階。 其余常用的還有平方階其余常用的還有平方階O(n2)、立方階、立方階O(n3)、對數、對數階階O(log2n)、指數階、指數階O(2n)等。等。 各種不同數量級對應的值存在著如下關系：各種不同數量級對應的值存在著如下關系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)當當n n取得取得很大時很大時，指數階算法和多

36、項式，指數階算法和多項式時間時間算法算法在在所需時間所需時間上上非常懸殊非常懸殊。多項式時間算法解決的問題叫多項式時間算法解決的問題叫P P問題；問題；指數階算法指數階算法解決的問題叫解決的問題叫NPNP問題。問題。世界難題：世界難題： NPNP問題問題 = P= P問題問題若有人能將現有若有人能將現有NPNP問題中的任何一個問題中的任何一個算法化簡為多項式時間算法，那就取算法化簡為多項式時間算法，那就取得了一個偉大的成就。得了一個偉大的成就。？例例：多項式時間算法與指數時間算法的執(zhí)行時間比較。假設算法P1的時間復雜度為T1(n) = n2，算法P2的時間復雜度為T2(n) = 2 n , 計

37、算機的運算速度是1微秒（即每秒1000000次運算）。 nP1運算次數運算次數P1運算時間運算時間P2運算次數運算次數P2運算時間運算時間101000.0001秒秒10240.001024秒秒204000.0004秒秒10485761.049秒秒309000.0009秒秒107374802417.9分鐘分鐘4016000.0016秒秒1099511627776305.42小時小時6036000.0036秒秒115292150460684697636558. 9年年例例：多項式時間算法與階乘時間算法的執(zhí)行時間比較。假設算法P1的時間復雜度為T1(n) = n2，算法P2的時間復雜度為T2(n)

38、= n! , 計算機的運算速度是每秒1億次運算）。 nP1運算次數運算次數P1運算時間運算時間P2運算次數運算次數P2運算時間運算時間101000.000001秒秒36288000.036288秒秒204000.000004秒秒2.43101777.13年年309000.000009秒秒2.6510328.41016 年年 例例1.4 求兩個求兩個n階方陣的相加階方陣的相加C=A+B的算法的算法如下如下,分析其時間復雜度。分析其時間復雜度。 #define MAX 20 /*定義最大的方階定義最大的方階*/ void matrixadd(int n,int AMAXMAX, int BMAXM

39、AX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 該算法中的基本運算是兩重循環(huán)中最深層的語句該算法中的基本運算是兩重循環(huán)中最深層的語句Cij=Aij+Bij,分析它的頻度分析它的頻度,即即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的時間復雜度。分析以下算法的時間復雜度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; r

40、eturn(s); 基本語句或基本操作基本語句或基本操作 解：解：該算法的基本操作是語句該算法的基本操作是語句s+,其頻度：其頻度： T(n)= =O(n3)則該算法的時間復雜度為則該算法的時間復雜度為O(n3)。 niijjk0001例例1.6 分析以下算法的時間復雜度。分析以下算法的時間復雜度。void func(int n) int i=0,s=0; while (sn) i+; s=s+i; 基本語句基本語句 解：對于解：對于while循環(huán)語句，設執(zhí)行的次數為循環(huán)語句，設執(zhí)行的次數為m，i從從0開始遞增開始遞增1，直到，直到m為止，有：為止，有： s=0+1+2+m-1=m(m-1)/

41、2， 并滿足并滿足s=m(m-1)/2n，則有，則有m 。 T(n)=O( ) 所以，該算法的時間復雜度為所以，該算法的時間復雜度為O( )。 nnn 例例1.7 有如下算法：有如下算法： void fun(int a,int n,int k) /*數組數組a共有共有n個元素個元素*/ int i;if (k=n-1) for (i=0;in;i+) printf(%dn,ai);else for (i=k;in;i+)ai=ai+i*i; fun(a,n,k+1); 調用上述算法的語句為調用上述算法的語句為fun(a,n,0)，求其時間復雜度。，求其時間復雜度。 解：設解：設fun(a,n,

42、0)的時間復雜度為的時間復雜度為T(n),則則fun(a,n,k)的執(zhí)行時間為的執(zhí)行時間為T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當當k=n-1時時 T1(n,k)= (n-k)+T1(n,k+1) 其他情況其他情況 則則 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)+ +2+n=O(n2) 所以調用所以調用fun(a,n,0)的時間復雜度為的時間復雜度為O(n2)。 空間復雜度是對一個算法在運行過程中空間復雜度是對一個算法在運行過程中臨時占用的臨時占用的存儲空間存儲空間大

43、小的量度大小的量度,一般也作為問題規(guī)模一般也作為問題規(guī)模n的函數的函數,以以數量級形式給出數量級形式給出,記作：記作： S(n) = O(g(n) 若所需額外空間相對于輸入數據量來說是常數若所需額外空間相對于輸入數據量來說是常數,則稱則稱此算法為原地工作。若所需存儲量依賴于特定的輸入此算法為原地工作。若所需存儲量依賴于特定的輸入,則通常按最壞情況考慮。則通常按最壞情況考慮。1.3.3 1.3.3 算法空間復雜度分析算法空間復雜度分析 返回返回 例例1.8 分析例分析例1.4和例和例1.5的空間復雜度。的空間復雜度。 解：由于這兩個算法中臨時變量的個數與問解：由于這兩個算法中臨時變量的個數與問題

44、規(guī)模題規(guī)模n無關無關,所以空間復雜度均為所以空間復雜度均為O(1)。1.4 數據結構算法程序數據結構算法程序 數據結構對算法的影響主要在兩方面數據結構對算法的影響主要在兩方面 （1 1）數據結構的存儲能力）數據結構的存儲能力數據結構存儲能力強、存儲信息多算法將數據結構存儲能力強、存儲信息多算法將會較好設計（時間少），存儲空間大。會較好設計（時間少），存儲空間大。時間和空間的平衡時間和空間的平衡（2 2）定義在數據結構上的操作）定義在數據結構上的操作在數據結構上定義基本操作算法調用這些在數據結構上定義基本操作算法調用這些基本操作?；静僮??；静僮髟酵暾?，基本操作越完整，算法設計就越容算法設計就

45、越容易易算法算法基本操作基本操作基本算法基本算法應用程序應用程序應用程序是通過應用程序是通過調用基本算法實調用基本算法實現的現的選擇數據結構需要考慮的幾個方面：選擇數據結構需要考慮的幾個方面：（1）數據結構要適應問題的狀態(tài)描述）數據結構要適應問題的狀態(tài)描述（2）數據結構應與所選擇的算法相適應）數據結構應與所選擇的算法相適應（3）數據結構的選擇同時要兼顧程序設計的方便）數據結構的選擇同時要兼顧程序設計的方便（4）靈活應用已有知識）靈活應用已有知識例如，有若干學生數據（學生數小于例如，有若干學生數據（學生數小于50），每個學生數據包含學號（每個學生學），每個學生數據包含學號（每個學生學號是惟一的，

46、但學生記錄不一定按學號順序號是惟一的，但學生記錄不一定按學號順序存放）、姓名、班號和若干門課程成績（每存放）、姓名、班號和若干門課程成績（每個學生所選課程數目可能不等，但最多不超個學生所選課程數目可能不等，但最多不超過過6門）。門）。要求設計一個程序輸出每個學生的學號、要求設計一個程序輸出每個學生的學號、姓名和平均分以及每門課程（課程編號從姓名和平均分以及每門課程（課程編號從16）的平均分。）的平均分。設計方案設計方案1 1：將學生的全部數據項放在一個將學生的全部數據項放在一個表中，一個學生的全部數據對應一條記錄。由于表中，一個學生的全部數據對應一條記錄。由于課程最多可選課程最多可選6 6門，對應的成績項也應有門，對應的成績項也應有6 6個。對個。對應的數據結構如下：應的數據結構如下：struct stud int no;/*學號學號*/char name10;/*姓名姓名*/int bno;/*班號班號*/int deg1;/*課程課程1分數分數*/int deg2;/*課程課程2分數分數*/int deg3;/*課程課程3分數分數*/int deg4;/*課程課程4分數分數