算法設計與分析 第2版

前言
教學建議
第一部分計算模型
第1 章抽象的算法設計與分析 2

11 RAM 模型的引入 2

111 計算的基本概念 2

112計算模型的基本概念 3
113RAM 模型 3

114計算模型的選擇：易用性與精確性 5
12 抽象算法設計 6

121 算法問題規(guī)約 6

122 算法正確性證明：數(shù)學歸納法 7

13 抽象算法分析 8

131 抽象算法的性能指標 8
132 最壞情況時間復雜度分析 9

133 平均情況時間復雜度分析 10

14 習題 11
第2 章從算法的視角重新審視數(shù)學的概念 14
21 數(shù)學運算背后的算法操作 14

211 取整 x 和 x 14
212 對數(shù)log n 14
213 階乘n! 15
214 常用級數(shù)求和f (i) 16
215 期望E[X] 18

22 函數(shù)的漸近增長率 19

23 “分治遞歸”求解 21

231 替換法 21
232 分治遞歸與遞歸樹 21
233 Master 定理 22
24 習題 23
第二部分從蠻力到分治
第3 章蠻力算法設計 31

31 蠻力選擇與查找 31
32 蠻力排序 32
321選擇排序 32
322插入排序 33
33 習題 35
第4 章分治排序 37
41 快速排序 37
411插入排序的不足 37
412快速排序的改進 38
413最壞情況時間復雜度分析 39

414基于遞歸方程的平均情況時間復雜度分析 40
415基于指標隨機變量的平均情況時間復雜度分析 41
42 合并排序 43
43 基于比較的排序的下界 44
431決策樹的引入 45
432比較排序的最壞情況時間復雜度的下界 45
433比較排序的平均情況時間復雜度的下界 46
44 習題 48
第5 章線性時間選擇 50
51 期望線性時間選擇 50

511選擇算法設計 50
512選擇算法分析 51
52 最壞情況線性時間選擇 52
521選擇算法設計 52
522選擇算法分析 53
53 習題 54
第6 章對數(shù)時間查找 57
61 折半查找 57
611經(jīng)典折半查找 57
612查找峰值 58
613計算√N 59

62 平衡二叉搜索樹 59
621二叉搜索樹及其平衡性 59

622紅黑樹的定義 60
623紅黑樹的平衡性 62
63 習題 62
第7 章分治算法設計要素 65
71 分治算法的關鍵特征 65
72 計算逆序?qū)Φ膫€數(shù) 66

721依托于合并排序的逆序?qū)τ嫈?shù) 66
722原地的逆序?qū)τ嫈?shù) 67
73 整數(shù)乘法 68
731簡單分治 69
732更精細的分治