算法设计与分析PDF电子书下载

基础篇 3

第1章 算法的基本概念 3

1.1算法的定义与特征 3

1.2求解问题的一般过程 4

1.3算法设计及其方法 6

1.3.1算法设计应注意的问题 7

1.3.2算法设计的基本方法 7

1.4算法的描述方法 9

1.4.1算法描述简介 9

1.4.2算法描述约定 14

1.4.3实例分析 17

第2章 算法分析基础 20

2.1算法的分析体系 20

2.1.1算法分析的评价 20

2.1.2算法的时间复杂性分析 21

2.1.3算法的空间复杂性分析 30

2.2算法分析实例 31

2.3 NP完全理论 39

第3章 算法基本工具和优化技巧 45

3.1循环和递归 45

3.1.1循环的设计 45

3.1.2递归的设计 53

3.1.3循环与递归的比较 56

3.2算法与数据结构 64

3.2.1常用的数据结构 64

3.2.2利用数据结构构造趣味矩阵 76

3.3算法优化基本技巧 80

3.3.1算术运算的应用 80

3.3.2标志位的应用 83

3.3.3信息数字化 87

3.4优化算法的实例模型 90

3.4.1杨辉三角形的应用 92

3.4.2最大公约数与最小公倍数的应用 94

3.4.3猜数游戏 97

3.4.4数字移位运用 100

核心篇 105

第4章 算法基本策略 105

4.1迭代算法 105

4.1.1递推法 105

4.1.2倒推法 108

4.2蛮力算法 113

4.2.1排序算法 113

4.2.2枚举法 121

4.3分治算法 127

4.3.1分治思想 127

4.3.2二分法 129

4.3.3二分法变异 136

4.4贪心算法 143

4.4.1贪心算法思想 143

4.4.2哈夫曼编码 145

4.4.3单源最短路径问题 148

4.4.4最小生成树问题 149

4.5动态规划 155

4.5.1动态规划 155

4.5.2货郎担问题 158

4.5.3资源分配问题 162

4.5.4设备更新问题 164

4.5.5最长公共子序列问题 166

4.6回溯算法 170

4.6.1回溯算法思想 171

4.6.2 n后问题 175

4.6.3图的着色问题 176

4.7随机算法 178

4.7.1数值概率算法 180

4.7.2舍伍德（Sherwood）算法 181

4.7.3拉斯维加斯（Las Vegas）算法 184

4.7.4蒙特卡罗（Monte carlo）算法 189

4.8各种算法策略的比较 194

4.8.1各种算法特点分析 194

4.8.2算法侧重的问题类型 197

第5章 图的搜索算法 200

5.1图的搜索概述 200

5.1.1图及其术语 200

5.1.2图的搜索及其术语 204

5.2图的遍历 205

5.2.1图的深度优先搜索遍历 206

5.2.2图的广度优先搜索遍历 209

5.3网络流量问题 213

5.3.1网络流量引言 213

5.3.2 Ford_ Fulkerson方法和最大容量扩张 217

5.3.3最短路径扩张问题 222

5.4二分图的最大匹配问题 227

5.4.1二分图引言 227

5.4.2二分图最大匹配的匈牙利方法 230

应用篇 241

第6章 算法设计实践 241

6.1递归与分治策略实例 241

6.2贪心算法实例 251

6.3动态规划算法实例 263

6.4其他算法 274

6.4.1货郎担问题的其他解法 274

6.4.2背包问题的其他解法 281

参考文献 293