算法设计与分析2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

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

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

目录1

第1章　算法的基本概念1

1.1 引言1

1.1.1　算法的定义和特征1

1.1.2　算法设计的例子，穷举法3

1.1.3　算法的复杂性分析5

1.2　算法的时间复杂性6

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

1.2.2　运行时间的上界，O记号9

1.2.3　运行时间的下界，Ω记号10

1.2.4　运行时间的准确界，？记号10

1.2.5　复杂性类型和o记号13

1.3　算法的时间复杂性分析14

1.3.1　循环次数的统计15

1.3.2　基本操作频率的统计18

1.3.3　计算步的统计21

1.3.4　最坏情况和平均情况22

1.3.5　最坏情况分析23

1.3.6 平均情况分析25

1.4　算法的空间复杂性28

1.5　最优算法29

习题29

参考文献31

第2章　常用的数学工具33

2.1　常用的函数和公式33

2.1.1　整数函数33

2.1.2　对数函数34

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

2.1.4　级数求和36

2.2.1　生成函数及其性质37

2.2　用生成函数求解递归方程37

2.2.2　用生成函数求解递归方程39

2.3　用特征方程求解递归方程42

2.3.1　k阶常系数线性齐次递归方程43

2.3.2 k阶常系数线性非齐次递归方程45

2.4　用递推方法求解递归方程48

2.4.1　递推48

2.4.2　用递推法求解变系数递归方程49

2.4.3　换名50

习题52

参考文献53

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

3.1 合并排序55

3.1.1　合并排序算法的实现55

3.1.2　合并排序算法的分析57

3.2.1　堆58

3.2　基于堆的排序58

3.2.2　堆的操作59

3.2.3　堆的建立63

3.2.4　堆的排序65

3.3　基数排序66

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

3.3.2　基数排序算法的实现68

3.3.3　基数排序算法的分析70

3.4　离散集合的操作71

3.4.1　离散集合的数据结构71

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

习题75

参考文献76

4.1.2　递归算法的例子78

4.1.1　归纳法的思想方法78

第4章　递归和分治78

4.1　基于归纳的递归算法78

4.1.3　多项式求值的递归算法81

4.1.4　排列问题的递归算法82

4.1.5　递归算法的讨论83

4.2　分治法84

4.2.1　分治法引言84

4.2.2　分治法的设计原理87

4.2.3　快速排序91

4.2.4　多项式乘积的分治算法96

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

4.2.6　选择问题107

习题113

参考文献114

5.1　贪婪法引言115

第5章　贪婪法115

5.1.1　贪婪法的设计思想116

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

5.2　背包问题118

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

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

5.3　单源最短路径问题120

5.3.1　解最短路径的狄斯奎诺（Dijkstra）算法121

5.3.2　狄斯奎诺算法的实现122

5.3.3　狄斯奎诺算法的分析124

5.4　最小花费生成树问题125

5.4.1　最小花费生成树引言125

5.4.2　克鲁斯卡尔（Kruskal）算法126

5.4.3　普里姆（Prim）算法130

习题133

参考文献135

第6章　动态规划136

6.1　动态规划的思想方法136

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

6.1.2　动态规划实例、货郎担问题137

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

6.2.1　多段图的决策过程139

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

6.3　资源分配问题143

6.3.1　资源分配的决策过程143

6.3.2　资源分配算法的实现146

6.4　设备更新问题148

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

6.4.2　设备更新算法的实现150

6.5　最长公共子序列问题152

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

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

6.6 0/1背包问题156

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

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

习题159

参考文献160

第7章　回溯162

7.1　回溯法的思想方法162

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

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

7.1.3 回溯法的一般性描述165

7.2　n后问题168

7.2.1 四后问题的求解过程168

7.2.2　n后问题算法的实现169

7.3　图的着色问题171

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

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

7.4　哈密尔顿回路问题175

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

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

7.5 0/1背包问题178

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

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

7.6　回溯法的效率分析184

习题186

参考文献187

第8章　分支与限界188

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

8.2　货郎担问题190

8.2.1 费用矩阵的特性及归约190

8.2.2　界限的确定和分支的选择192

8.2.3　货郎担问题的求解过程195

8.2.4　几个辅助函数的实现198

8.2.5　货郎担问题分支限界算法的实现204

8.3 0/1背包问题206

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

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

8.4　作业分配问题211

8.4.1　分支限界法解作业分配问题的思想方法211

8.4.2　分支限界法解作业分配问题算法的实现214

习题216

参考文献217

第9章　随机算法218

9.1　随机算法引言218

9.1.1　随机算法的类型218

9.1.2　随机数发生器219

9.2.1　随机快速排序算法220

9.2　舍伍德（Sherwood）算法220

9.2.2　随机选择算法221

9.3　拉斯维加斯（Las Vegas）算法224

9.3.1　字符串匹配225

9.3.2　整数因子228

9.4　蒙特卡罗（Monte Carlo）算法229

9.4.1　数组的主元素问题230

9.4.2　素数测试231

习题234

参考文献235

第10章　图和网络问题236

10.1 图的遍历236

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

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

10.1.3　无向图的接合点243

10.1.4　有向图的强连通分支246

10.2　网络流量249

10.2.1　预备知识249

10.2.2 Ford_Fulkerson方法和最大容量扩张251

10.2.3　最短路径扩张255

10.3 分图的最大匹配问题258

10.3.1　预备知识259

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

习题266

参考文献268

第11章　计算几何问题269

11.1 引言269

11.2　平面线段的交点问题271

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

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

11.3　凸壳问题278

11.3.1 凸壳问题的格雷厄姆（Graham）扫描法279

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

11.4　平面点集的直径问题282

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

11.4.2　平面点集直径的求取284

习题286

参考文献286

第12章　NP完全问题287

12.1 P类和NP类问题288

12.1.1 P类问题288

12.1.2 NP类问题289

12.2 NP完全问题291

12.2.1 NP完全问题的定义291

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

12.2.3　其他的NP完全问题298

12.3 co_NP类和NPI类问题299

习题301

参考文献302

第13章　计算复杂性303

13.1　计算模型303

13.1.1 图灵机的基本模型303

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

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

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

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

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

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

13.2.3　填充变元320

13.3　归约性关系321

13.4　完备性325

13.4.1　NLOGSPACE完全问题325

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

习题328

参考文献329

第14章　下界330

14.1　平凡下界330

14.2　判定树模型330

14.2.1　检索问题331

14.2.2　排序问题332

14.3　代数判定树模型333

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

14.3.2　极点问题335

14.4　线性时间归约336

14.4.1　凸壳问题336

14.4.2　多项式插值问题337

习题338

参考文献339

第15章　近似算法340

15.1　近似算法的性能340

15.2　装箱问题341

15.2.1　首次适宜算法342

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

15.3　顶点覆盖问题344

15.4　货郎担问题347

15.4.1　欧几里德货郎担问题347

15.4.2　一般的货郎担问题349

15.5　多项式近似方案350

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

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

习题355

参考文献356

参考文献357