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

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

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

第1章 算法的基本概念1

1．1 引言1

1．1．1 算法的定义和特征1

1．1．2 算法设计的例子，穷举法3

1．1．3 算法的复杂性分析6

1．2 算法的时间复杂性6

1．2．1 算法的输入规模和运行时间的阶6

1．2．2 运行时间的上界，O记号10

1．2．3 运行时间的下界，Ω记号11

1．2．4 运行时间的准确界，Θ记号11

1．2．5 O记号、Ω记号、Θ记号的性质15

1．2．6 复杂性类型和o记号16

习题17

参考文献18

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

2．1 常用的函数和公式19

2．1．1 整数函数19

2．1．2 对数函数20

2．1．3 排列、组合和二项式系数21

2．1．4 级数求和22

2．2 算法的时间复杂性分析23

2．2．1 循环次数的统计23

2．2．2 基本操作频率的统计27

2．2．3 计算步的统计30

2．3 最好情况、最坏情况和平均情况分析31

2．3．1 最好情况、最坏情况和平均情况31

2．3．2 最好情况和最坏情况分析32

2．3．3 平均情况分析34

2．4 用生成函数求解递归方程38

2．4．1 生成函数及其性质38

2．4．2 用生成函数求解递归方程40

2．5 用特征方程求解递归方程44

2．5．1 k阶常系数线性齐次递归方程44

2．5．2 k阶常系数线性非齐次递归方程46

2．6 用递推方法求解递归方程49

2．6．1 递推49

2．6．2 用递推法求解变系数递归方程49

2．6．3 换名51

2．7 算法的空间复杂性53

2．8 最优算法54

习题55

参考文献57

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

3．1 合并排序58

3．1．1 合并排序算法的实现58

3．1．2 合并排序算法的分析60

3．2 基于堆的排序62

3．2．1 堆62

3．2．2 堆的操作62

3．2．3 堆的建立67

3．2．4 堆的排序69

3．3 基数排序70

3．3．1 基数排序算法的思想方法71

3．3．2 基数排序算法的实现72

3．3．3 基数排序算法的分析74

3．4 离散集合的Union_Find操作75

3．4．1 用于Union_Find操作的数据结构75

3．4．2 union、find操作及路径压缩77

习题80

参考文献81

第4章 递归和分治82

4．1 基于归纳的递归算法82

4．1．1 基于归纳的递归算法的思想方法82

4．1．2 递归算法的例子83

4．1．3 排列问题的递归算法86

4．1．4 求数组主元素的递归算法90

4．1．5 整数划分问题的递归算法93

4．2 分治法94

4．2．1 分治法的例子95

4．2．2 分治法的设计原理99

4．2．3 快速排序106

4．2．4 多项式乘积和大整数乘法111

4．2．5 平面点集最接近点对问题117

4．2．6 选择问题125

4．2．7 残缺棋盘问题131

习题136

参考文献138

第5章 贪婪法139

5．1 贪婪法引言140

5．1．1 贪婪法的设计思想140

5．1．2 贪婪法的例子——货郎担问题141

5．2 背包问题142

5．2．1 背包问题贪婪算法的实现142

5．2．2 背包问题贪婪算法的分析144

5．3 单源最短路径问题145

5．3．1 解最短路径的狄斯奎诺算法145

5．3．2 狄斯奎诺算法的实现147

5．3．3 狄斯奎诺算法的分析149

5．4 最小花费生成树问题150

5．4．1 最小花费生成树引言150

5．4．2 克鲁斯卡尔（Kruskal）算法151

5．4．3 普里姆算法155

5．5 霍夫曼（Huffman）编码问题159

5．5．1 前缀码和最优二叉树159

5．5．2 霍夫曼编码的实现162

习题164

参考文献166

第6章 动态规划168

6．1 动态规划的思想方法168

6．1．1 动态规划的最优决策原理168

6．1．2 动态规划实例——货郎担问题169

6．2 多段图的最短路径问题171

6．2．1 多段图的决策过程172

6．2．2 多段图动态规划算法的实现174

6．3 资源分配问题175

6．3．1 资源分配的决策过程176

6．3．2 资源分配算法的实现178

6．4 设备更新问题180

6．4．1 设备更新问题的决策过程181

6．4．2 设备更新算法的实现184

6．5 最长公共子序列问题186

6．5．1 最长公共子序列的搜索过程186

6．5．2 最长公共子序列算法的实现189

6．6 0／1背包问题190

6．6．1 0／1背包问题的求解过程190

6．6．2 0／1背包问题的实现192

6．7 RNA最大碱基对匹配问题193

6．7．1 RNA最大碱基对匹配的搜索过程194

6．7．2 RNA最大碱基对匹配算法的实现196

习题199

参考文献201

第7章 回溯202

7．1 回溯法的思想方法202

7．1．1 问题的解空间和状态空间树202

7．1．2 状态空间树的动态搜索203

7．1．3 回溯法的一般性描述205

7．2 n后问题208

7．2．1 4后问题的求解过程208

7．2．2 n后问题算法的实现210

7．3 图的着色问题212

7．3．1 图着色问题的求解过程212

7．3．2 图的m着色问题算法的实现214

7．4 哈密尔顿回路问题215

7．4．1 哈密尔顿回路的求解过程216

7．4．2 哈密尔顿回路算法的实现217

7．5 0／1背包问题219

7．5．1 回溯法解0／1背包问题的求解过程219

7．5．2 回溯法解0／1背包问题算法的实现222

7．6 回溯法的效率分析225

习题227

参考文献228

第8章 分支与限界229

8．1 分支与限界法的基本思想229

8．2 作业分配问题231

8．2．1 分支限界法解作业分配问题的思想方法231

8．2．2 分支限界法解作业分配问题算法的实现234

8．3 单源最短路径问题236

8．3．1 分支限界法解单源最短路径问题的思想方法237

8．3．2 分支限界法解单源最短路径问题算法的实现239

8．4 0／1背包问题241

8．4．1 分支限界法解0／1背包问题的思想方法和求解过程242

8．4．2 0／1背包问题分支限界算法的实现244

8．5 货郎担问题247

8．5．1 费用矩阵的特性及归约247

8．5．2 界限的确定和分支的选择249

8．5．3 货郎担问题的求解过程252

8．5．4 几个辅助函数的实现255

8．5．5 货郎担问题分支限界算法的实现261

习题263

参考文献265

第9章 随机算法266

9．1 随机算法引言266

9．1．1 随机算法的类型266

9．1．2 随机数发生器267

9．2 舍伍德算法268

9．2．1 随机快速排序算法268

9．2．2 随机选择算法269

9．3 拉斯维加斯算法273

9．3．1 字符串匹配273

9．3．2 整数因子277

9．4 蒙特卡罗算法278

9．4．1 数组的主元素问题278

9．4．2 素数测试280

习题283

参考文献284

第10章 图和网络问题285

10．1 图的遍历285

10．1．1 图的深度优先搜索遍历285

10．1．2 图的广度优先搜索遍历289

10．1．3 无向图的接合点292

10．1．4 有同图的强连通分支296

10．2 网络流299

10．2．1 网络流的概念299

10．2．2 Ford_Fulkerson方法和最大容量增广302

10．2．3 最短路径增广306

10．3 二分图的最大匹配问题311

10．3．1 预备知识311

10．3．2 二分图最大匹配的匈牙利树方法314

习题319

参考文献321

第11章 计算几何问题323

11．1 引言323

11．2 平面线段的交点问题325

11．2．1 寻找平面线段交点的思想方法326

11．2．2 寻找平面线段交点的实现328

11．3 凸壳问题333

11．3．1 凸壳问题的格雷厄姆（Graham）扫描法333

11．3．2 格雷厄姆扫描法的实现335

11．4 平面点集的直径问题337

11．4．1 求取平面点集直径的思想方法337

11．4．2 平面点集直径的求取339

习题341

参考文献342

第12章 NP完全问题343

12．1 P类和NP类问题344

12．1．1 P类问题344

12．1．2 NP类问题345

12．2 NP完全问题347

12．2．1 NP完全问题的定义347

12．2．2 几个典型的NP完全问题349

12．2．3 其他的NP完全问题355

12．3 co_NP类和NPI类问题355

习题357

参考文献358

第13章 计算复杂性360

13．1 计算模型360

13．1．1 图灵机的基本模型360

13．1．2 k带图灵机和时间复杂性363

13．1．3 离线图灵机和空间复杂性365

13．1．4 可满足性问题和Cook定理367

13．2 复杂性类型之间的关系370

13．2．1 时间复杂性和空间复杂性的关系370

13．2．2 时间谱系定理和空间谱系定理373

13．2．3 填充变元378

13．3 归约性关系379

13．4 完备性383

13．4．1 NLOGSPACE完全问题383

13．4．2 PSPACE完全问题和P完全问题384

习题385

参考文献387

第14章 下界388

14．1 平凡下界388

14．2 判定树模型388

14．2．1 检索问题389

14．2．2 排序问题390

14．3 代数判定树模型391

14．3．1 代数判定树模型及下界定理391

14．3．2 极点问题393

14．4 线性时间归约394

14．4．1 凸壳问题395

14．4．2 多项式插值问题395

习题397

参考文献397

第15章 近似算法399

15．1 近似算法的性能399

15．2 装箱问题400

15．2．1 首次适宜算法401

15．2．2 最适宜算法及其他算法402

15．3 顶点覆盖问题404

15．4 货郎担问题406

15．4．1 欧几里得货郎担问题407

15．4．2 一般的货郎担问题409

15．5 多项式近似方案409

15．5．1 0／1背包问题的多项式近似方案410

15．5．2 子集求和问题的完全多项式近似方案413

习题415

参考文献416

参考文献417