目　　錄
前言
教學(xué)建議
第1章　概述　1
1.1　算法與數(shù)據(jù)結(jié)構(gòu)及程序的關(guān)系　1
1.1.1　什么是算法　1
1.1.2　算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系　1
1.1.3　算法與程序的關(guān)系　2
1.1.4　選擇排序的例子　2
1.1.5　算法的偽碼表示　2
1.2　算法復(fù)雜度分析　 3
1.2.1　算法復(fù)雜度的度量　3
1.2.2　算法復(fù)雜度與輸入數(shù)據(jù)規(guī)模的關(guān)系　4
1.2.3　輸入數(shù)據(jù)規(guī)模的度量模型　4
1.2.4　算法復(fù)雜度分析中的兩個(gè)簡化假設(shè)　5
1.2.5　最好情況、最壞情況和平均情況
的復(fù)雜度分析　5
1.3　函數(shù)增長漸近性態(tài)的比較　6
1.3.1　三種比較關(guān)系及O、、記號(hào)　6
1.3.2　表示算法復(fù)雜度的常用函數(shù)　7
1.4　問題復(fù)雜度與算法復(fù)雜度的關(guān)系　9
1.4.1　問題復(fù)雜度是算法復(fù)雜度的
下界　9
1.4.2　問題復(fù)雜度與最佳算法　9
1.4.3　易處理問題和難處理問題　9
習(xí)題　 10
第2章　分治法　11
2.1　分治法原理　11
2.1.1　二元搜索的例子　11
2.1.2　表示復(fù)雜度的遞推關(guān)系　12
2.2　遞推關(guān)系求解　13
2.2.1　替換法　13
2.2.2　序列求和法與遞歸樹法　15
2.2.3　常用序列和公式　16
2.2.4　主方法求解　18
2.3　例題示范　19
習(xí)題　 20
第3章　基于比較的排序算法　24
3.1　插入排序　　24
3.1.1　插入排序的算法 24
3.1.2　插入排序算法的復(fù)雜度分析　25
3.1.3　插入排序的優(yōu)缺點(diǎn)　26
3.2　合并排序　26
3.2.1　合并算法及其復(fù)雜度　26
3.2.2　合并排序的算法及其復(fù)雜度　27
3.2.3　合并排序的優(yōu)缺點(diǎn)　29
3.3　堆排序　 30
3.3.1　堆的數(shù)據(jù)結(jié)構(gòu)　30
3.3.2　堆的修復(fù)算法及其復(fù)雜度　31
3.3.3　為輸入數(shù)據(jù)建堆　32
3.3.4　堆排序算法　33
3.3.5　堆排序算法的復(fù)雜度　34
3.3.6　堆排序算法的優(yōu)缺點(diǎn)　35
3.3.7　堆用作優(yōu)先隊(duì)列　35
3.4　快排序　36
3.4.1　快排序算法　36
3.4.2　快排序算法最壞情況復(fù)雜度　39
3.4.3　快排序算法平均情況復(fù)雜度　40
3.4.4　快排序算法最好情況復(fù)雜度　41
3.4.5　快排序算法的優(yōu)缺點(diǎn)　42
習(xí)題　 42
第4章　不基于比較的排序算法　46
4.1　比較排序的下界　46
4.1.1　決策樹模型及排序最壞情況下界　46
4.1.2　二叉樹的外路徑總長與排序平均
情況下界　 49
4.1.3　二叉樹的全路徑總長與堆排序
最好情況下界　 51
4.2　不基于比較的線性時(shí)間排序算法　54
4.2.1　計(jì)數(shù)排序　 54
4.2.2　基數(shù)排序　57
4.2.3　桶排序　58
習(xí)題　60
第5章　中位數(shù)和任一順序數(shù)的選擇　63
5.1　問題定義　63
5.2　最大數(shù)和最小數(shù)的選擇　63
5.2.1　最大和最小順序數(shù)的選擇算法及
其復(fù)雜度　64
5.2.2　同時(shí)找出最大數(shù)和最小數(shù)的
算法　65
5.3　線性時(shí)間找出任一順序數(shù)的算法　66
5.3.1　最壞情況復(fù)雜度為O(n)的算法 66
5.3.2　平均情況復(fù)雜度為O(n)的算法　 68
5.4　找出k個(gè)最大順序數(shù)的算法　69
5.4.1　一個(gè)理論聯(lián)系實(shí)際的問題　69
5.4.2　利用堆來找k個(gè)最大順序數(shù)的
算法　 70
5.4.3　利用錦標(biāo)賽樹來找k個(gè)最大順序數(shù)
的算法　70
習(xí)題　 71
第6章　動(dòng)態(tài)規(guī)劃　 73
6.1　動(dòng)態(tài)規(guī)劃的基本原理　73
6.2　矩陣連乘問題　 75
6.2.1　定義子問題　75
6.2.2　歸納公式　77
6.2.3　算法偽碼和例子　78
6.3　最長公共子序列問題　81
6.3.1　定義子問題　81
6.3.2　歸納公式　82
6.3.3　算法偽碼和例子　82
6.4　最佳二元搜索樹問題　84
6.4.1　定義子問題和歸納公式　85
6.4.2　算法偽碼和例子　87
6.5　多級(jí)圖及其應(yīng)用　 89
6.6　最長遞增子序列問題　92
6.6.1　定義子問題　93
6.6.2　歸納公式　93
6.6.3　算法偽碼和例子　93
習(xí)題　 95
第7章　貪心算法　 103
7.1　最佳郵局設(shè)置問題　103
7.2　一個(gè)簡單的最佳活動(dòng)安排問題　105
7.3　其他最佳活動(dòng)安排問題　106
7.3.1　兩個(gè)大禮堂的最佳活動(dòng)安排
問題　106
7.3.2　等長時(shí)間的活動(dòng)的最佳安排
問題　109
7.4　哈夫曼編碼問題　112
7.4.1　前綴碼　112
7.4.2　最佳前綴碼——哈夫曼編碼　114
7.5　最佳加油計(jì)劃問題　118
7.5.1　最佳加油計(jì)劃問題的描述　118
7.5.2　貪心算法的基本思路　119
7.5.3　貪心算法的偽碼　120
習(xí)題　 121
第8章　圖的周游算法　 128
8.1　圖的表示　128
8.1.1　鄰接表　129
8.1.2　鄰接矩陣 129
8.2　廣度優(yōu)先搜索及應(yīng)用　130
8.2.1　廣度優(yōu)先搜索策略　130
8.2.2　廣度優(yōu)先搜索算法及距離樹　131
8.2.3　無向圖的二著色問題　133
8.3　深度優(yōu)先搜索及應(yīng)用　136