算法设计与分析 第3版PDF|Epub|txt|kindle电子书版本网盘下载

算法设计与分析 第3版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1篇 算法设计与分析的基本概念2

第1章 算法的基本概念2

1.1 引言2

1.1.1 算法的定义和特征2

1.1.2 算法设计的例子——穷举法4

1.1.3 算法的复杂性分析7

1.2 算法的时间复杂性8

1.2.1 算法的输入规模和运行时间的阶8

1.2.2 运行时间的上界——Ο记号11

1.2.3 运行时间的下界——Ω记号12

1.2.4 运行时间的准确界——Θ记号13

1.2.5 Ο记号、Ω记号、Θ记号的性质17

1.2.6 复杂性类型和ο记号18

习题19

参考文献20

第2章 算法的复杂性分析21

2.1 常用的函数和公式21

2.1.1 整数函数21

2.1.2 对数函数22

2.1.3 排列、组合和二项式系数23

2.1.4 级数求和24

2.2 算法的时间复杂性分析25

2.2.1 循环次数的统计25

2.2.2 基本操作频率的统计29

2.2.3 计算步的统计32

2.3 最好情况、最坏情况和平均情况分析33

2.3.1 最好情况、最坏情况和平均情况33

2.3.2 最好情况和最坏情况分析34

2.3.3 平均情况分析37

2.4 用生成函数求解递归方程40

2.4.1 生成函数及其性质40

2.4.2 用生成函数求解递归方程43

2.5 用特征方程求解递归方程46

2.5.1 k阶常系数线性齐次递归方程47

2.5.2 k阶常系数线性非齐次递归方程49

2.6 用递推方法求解递归方程51

2.6.1 递推52

2.6.2 用递推法求解变系数递归方程52

2.6.3 换名54

2.7 算法的空间复杂性56

2.8 最优算法57

习题58

参考文献60

第2篇 算法设计的基本技术62

第3章 排序问题和离散集合的操作62

3.1 合并排序62

3.1.1 合并排序算法的实现62

3.1.2 合并排序算法的分析64

3.2 基于堆的排序65

3.2.1 堆66

3.2.2 堆的操作67

3.2.3 堆的建立70

3.2.4 堆的排序73

3.3 基数排序74

3.3.1 基数排序算法的思想方法74

3.3.2 基数排序算法的实现76

3.3.3 基数排序算法的分析78

3.4 离散集合的Union_Find操作79

3.4.1 用于Union_Find操作的数据结构79

3.4.2 union、find操作及路径压缩81

习题84

参考文献85

第4章 递归和分治86

4.1 基于归纳的递归算法86

4.1.1 基于归纳的递归算法的思想方法86

4.1.2 递归算法的例子87

4.1.3 排列问题的递归算法91

4.1.4 求数组主元素的递归算法95

4.1.5 整数划分问题的递归算法98

4.2 分治法100

4.2.1 分治法的例子100

4.2.2 分治法的设计原理104

4.2.3 快速排序111

4.2.4 多项式乘积和大整数乘法116

4.2.5 平面点集最接近点对问题123

4.2.6 选择问题130

4.2.7 残缺棋盘问题136

习题141

参考文献143

第5章 贪婪法145

5.1 贪婪法概述146

5.1.1 贪婪法的设计思想146

5.1.2 贪婪法的例子——货郎担问题147

5.2 背包问题148

5.2.1 背包问题贪婪算法的实现148

5.2.2 背包问题贪婪算法的分析150

5.3 单源最短路径问题151

5.3.1 解最短路径的狄斯奎诺算法151

5.3.2 狄斯奎诺算法的实现153

5.3.3 狄斯奎诺算法的分析155

5.4 最小花费生成树问题156

5.4.1 最小花费生成树概述156

5.4.2 克鲁斯卡尔算法157

5.4.3 普里姆算法161

5.5 霍夫曼编码问题165

5.5.1 前缀码和最优二叉树165

5.5.2 霍夫曼编码的实现169

习题171

参考文献173

第6章 动态规划174

6.1 动态规划的思想方法174

6.1.1 动态规划的最优决策原理174

6.1.2 动态规划实例——货郎担问题175

6.2 多段图的最短路径问题177

6.2.1 多段图的决策过程178

6.2.2 多段图动态规划算法的实现180

6.3 资源分配问题181

6.3.1 资源分配的决策过程182

6.3.2 资源分配算法的实现184

6.4 设备更新问题187

6.4.1 设备更新问题的决策过程187

6.4.2 设备更新算法的实现190

6.5 最长公共子序列问题192

6.5.1 最长公共子序列的搜索过程192

6.5.2 最长公共子序列算法的实现195

6.6 0/1背包问题196

6.6.1 0/1背包问题的求解过程196

6.6.2 0/1背包问题的实现198

6.7 RNA最大碱基对匹配问题199

6.7.1 RNA最大碱基对匹配的搜索过程200

6.7.2 RNA最大碱基对匹配算法的实现203

习题205

参考文献207

第7章 回溯208

7.1 回溯法的思想方法208

7.1.1 问题的解空间和状态空间树208

7.1.2 状态空间树的动态搜索209

7.1.3 回溯法的一般性描述211

7.2 n皇后问题213

7.2.1 n皇后问题的求解过程213

7.2.2 n皇后问题算法的实现215

7.3 图的着色问题217

7.3.1 图着色问题的求解过程218

7.3.2 图的m着色问题算法的实现220

7.4 哈密尔顿回路问题222

7.4.1 哈密尔顿回路的求解过程222

7.4.2 哈密尔顿回路算法的实现224

7.5 0/1背包问题225

7.5.1 回溯法解0/1背包问题的求解过程226

7.5.2 回溯法解0/1背包问题算法的实现229

7.6 回溯法的效率分析231

习题234

参考文献235

第8章 分支与限界236

8.1 分支与限界法的基本思想236

8.2 作业分配问题238

8.2.1 分支限界法解作业分配问题的思想方法238

8.2.2 分支限界法解作业分配问题算法的实现241

8.3 单源最短路径问题244

8.3.1 分支限界法解单源最短路径问题的思想方法244

8.3.2 分支限界法解单源最短路径问题算法的实现246

8.4 0/1背包问题248

8.4.1 分支限界法解0/1背包问题的思想方法和求解过程249

8.4.2 0/1背包问题分支限界算法的实现251

8.5 货郎担问题254

8.5.1 费用矩阵的特性及归约254

8.5.2 界限的确定和分支的选择256

8.5.3 货郎担问题的求解过程259

8.5.4 几个辅助函数的实现262

8.5.5 货郎担问题分支限界算法的实现268

习题271

参考文献272

第9章 随机算法273

9.1 随机算法概述273

9.1.1 随机算法的类型273

9.1.2 随机数发生器274

9.2 舍伍德算法275

9.2.1 随机快速排序算法275

9.2.2 随机选择算法277

9.3 拉斯维加斯算法280

9.3.1 字符串匹配280

9.3.2 整数因子284

9.4 蒙特卡罗算法285

9.4.1 数组的主元素问题286

9.4.2 素数测试287

习题290

参考文献291

第3篇 计算机应用领域的一些算法294

第10章 图和网络问题294

10.1 图的遍历294

10.1.1 图的深度优先搜索遍历294

10.1.2 图的广度优先搜索遍历299

10.1.3 无向图的接合点301

10.1.4 有向图的强连通分支305

10.2 网络流308

10.2.1 网络流的概念308

10.2.2 Ford_Fulkerson方法和最大容量增广312

10.2.3 最短路径增广315

10.3 二分图的最大匹配问题320

10.3.1 预备知识321

10.3.2 二分图最大匹配的匈牙利树方法323

习题329

参考文献331

第11章 计算几何问题332

11.1 引言332

11.2 平面线段的交点问题334

11.2.1 寻找平面线段交点的思想方法335

11.2.2 寻找平面线段交点的实现337

11.3 凸壳问题342

11.3.1 凸壳问题的格雷厄姆扫描法343

11.3.2 格雷厄姆扫描法的实现344

11.4 平面点集的直径问题346

11.4.1 求取平面点集直径的思想方法346

11.4.2 平面点集直径的求取348

习题350

参考文献351

第4篇 算法设计与分析的一些理论问题354

第12章 NP完全问题354

12.1 P类和NP类问题355

12.1.1 P类问题355

12.1.2 NP类问题356

12.2 NP完全问题358

12.2.1 NP完全问题的定义358

12.2.2 几个典型的NP完全问题360

12.2.3 其他NP完全问题366

12.3 co_NP类和NPI类问题366

习题369

参考文献370

第13章 计算复杂性371

13.1 计算模型371

13.1.1 图灵机的基本模型371

13.1.2 k带图灵机和时间复杂性374

13.1.3 离线图灵机和空间复杂性376

13.1.4 可满足性问题和Cook定理379

13.2 复杂性类型之间的关系381

13.2.1 时间复杂性和空间复杂性的关系382

13.2.2 时间谱系定理和空间谱系定理384

13.2.3 填充变元389

13.3 归约性关系391

13.4 完备性394

13.4.1 NLOGSPACE完全问题394

13.4.2 PSPACE完全问题和P完全问题396

习题397

参考文献398

第14章 下界399

14.1 平凡下界399

14.2 判定树模型399

14.2.1 检索问题400

14.2.2 排序问题401

14.3 代数判定树模型402

14.3.1 代数判定树模型及下界定理402

14.3.2 极点问题404

14.4 线性时间归约405

14.4.1 凸壳问题406

14.4.2 多项式插值问题406

习题408

参考文献408

第15章 近似算法409

15.1 近似算法的性能409

15.2 装箱问题410

15.2.1 首次适宜算法411

15.2.2 最适宜算法及其他算法412

15.3 顶点覆盖问题414

15.4 货郎担问题416

15.4.1 欧几里得货郎担问题417

15.4.2 一般的货郎担问题419

15.5 多项式近似方案419

15.5.1 0/1背包问题的多项式近似方案420

15.5.2 子集求和问题的完全多项式近似方案423

习题425

参考文献426

参考文献427