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

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

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

第1章　绪论1

1.1　什么是算法2

习题1.16

1.2　算法问题求解基础7

1.2.1 理解问题8

1.2.2 了解计算设备的性能8

1.2.3　在精确解法和近似解法之间做出选择9

1.2.4 确定适当的数据结构9

1.2.5　算法的设计技术9

1.2.6　算法的描述10

1.2.7　算法的正确性证明10

1.2.8　算法的分析11

1.2.9　为算法写代码12

习题1.213

1.3　重要的问题类型14

1.3.1 排序15

1.3.2 查找16

1.3.3　字符串处理16

1.3.4　图问题16

1.3.5　组合问题17

1.3.6　几何问题17

1.3.7　数值问题18

习题1.318

1.4　基本数据结构20

1.4.1　线性数据结构20

1.4.2　图22

1.4.3　树25

1.4.4　集合与字典28

习题1.429

小结30

第2章　算法效率分析基础32

2.1 分析框架33

2.1.1　输入规模的度量33

2.1.2　运行时间的度量单位34

2.1.3 　增长次数35

2.1.4　算法的最优、最差和平均效率36

2.1.5　分析框架概要38

习题2.139

2.2　渐进符号和基本效率类型40

2.2.1 非正式的介绍40

2.2.2　符号O41

2.2.3　符号Ω41

2.2.4　符号？42

2.2.5　渐进符号的有用特性43

2.2.6　利用极限比较增长次数44

2.2.7　基本的效率类型45

习题2.246

2.3　非递归算法的数学分析47

习题2.351

2.4　递归算法的数学分析53

习题2.458

2.5　例题：斐波那契数列60

2.5.1　第n个斐波那契数的精确公式61

2.5.2　计算斐波那契数的算法62

习题2.564

2.6　算法的经验分析65

习题2.669

2.7　算法可视法70

小结73

第3章　蛮力法75

3.1.1 选择排序76

3.1 选择排序和冒泡排序76

3.1.2 冒泡排序77

习题3.178

3.2　顺序查找和蛮力字符串匹配79

3.2.1 顺序查找79

3.2.2　蛮力字符串匹配80

习题3.281

3.3　最近对和凸包问题的蛮力算法82

3.3.1　最近对问题83

3.3.2 凸包问题83

习题6.686

习题3.386

3.4　穷举查找87

3.4.1　旅行商问题87

3.4.2　背包问题89

3.4.3 分配问题90

习题3.491

小结92

第4章　分治法94

4.1 合并排序95

习题4.197

4.2　快速排序99

习题4.2102

4.3　折半查找103

习题4.3105

4.4 二叉树遍历及其相关特性106

习题4.4108

4.5 大整数乘法和Strassen矩阵乘法109

4.5.1　大整数乘法110

4.5.2　Strassen矩阵乘法111

4.6.1　最近对问题113

4.6　用分治法解最近对问题和凸包问题113

习题4.5113

4.6.2　凸包问题115

习题4.6117

小结118

第5章　减治法119

5.1 插入排序121

习题5.1123

5.2　深度优先查找和广度优先查找124

5.2.1　深度优先查找125

5.2.2　广度优先查找127

习题5.2129

5.3　拓扑排序130

习题5.3133

5.4　生成组合对象的算法134

5.4.1 生成排列135

5.4.2　生成子集136

习题5.4137

5.5　减常因子算法138

5.5.2　俄式乘法139

5.5.1　假币问题139

5.5.3　约瑟夫斯问题140

习题5.5141

5.6　减可变规模算法142

5.6.1　计算中值和选择问题142

5.6.2　插值查找144

5.6.3 二叉查找树的查找和插入145

5.6.4　拈游戏146

习题5.6147

小结148

第6章　变治法150

6.1 预排序151

习题6.1153

6.2　高斯消去法154

6.2.1　LU分解及其他应用158

6.2.2　计算矩阵的逆159

6.2.3　计算矩阵的行列式160

习题6.2161

6.3 平衡查找树162

6.3.1 AVL树163

6.3.2　2-3树167

习题6.3168

6.4 堆和堆排序169

6.4.1　堆的概念170

6.4.2　堆排序174

习题6.4175

6.5.1 霍纳法则176

6.5　霍纳法则和二进制幂176

6.5.2 二进制幂177

习题6.5179

6.6　问题化简181

6.6.1 求最小公倍数181

6.6.2　计算图中的路径数量182

6.6.3　优化问题的化简182

6.6.4　线性规划183

6.6.5　简化为图问题185

小结188

第7章　时空权衡190

7.1 计数排序191

习题7.1193

7.2　字符串匹配中的输入增强技术194

7.2.1 Horspool算法195

7.2.2 Boyer-Moore算法197

习题7.2201

7.3 散列法202

7.3.1 开散列（分离链）203

7.3.2　闭散列（开式寻址）205

习题7.3207

7.4　B树208

习题7.4211

小结211

第8章　动态规划213

8.1　计算二项式系数214

习题8.1215

8.2　Warshall算法和Floyd算法216

8.2.1 Warshall算法217

8.2.2 计算完全最短路径的Floyd算法220

习题8.2222

8.3　最优二叉查找树223

习题8.3227

8.4　背包问题和记忆功能228

8.4.1 背包问题228

8.4.2　记忆功能230

习题8.4231

小结232

第9章　贪婪技术233

9.1　Prim算法234

习题9.1238

9.2　Kruskal算法239

习题9.2245

9.3　Dijkstra算法246

习题9.3249

9.4　哈夫曼树250

习题9.4253

小结254

第10章　迭代改进255

10.1 单纯形法256

10.1.1　线性规划的几何解释256

10.1.2 单纯形法概述259

10.1.3　单纯形法其他要点264

习题10.1265

10.2　最大流量问题267

习题10.2274

10.3　二分图的最大匹配276

习题10.3281

10.4　稳定婚姻问题282

习题10.4285

小结286

第11章　算法能力的极限287

11.1　如何求下界288

11.1.1　平凡下界288

11.1.2　信息论下界289

11.1.3　敌手下界289

11.1.4　问题化简290

习题11.1291

11.2 决策树292

11.2.1　排序算法的决策树293

11.2.2　查找有序数组的决策树295

习题11.2296

11.3　P、NP和NP完全问题298

11.3.1 P和NP问题298

11.3.2　NP完全问题301

习题11.3304

11.4　数值算法的挑战306

习题11.4311

小结312

第12章　超越算法能力的极限314

12.1 回溯法314

12.1.1 n皇后问题315

12.1.2 哈密顿回路问题316

12.1.3 子集和问题317

12.1.4 一般性说明318

习题12.1319

12.2　分支界限法321

12.2.1 分配问题321

12.2.2　背包问题324

12.2.3　旅行商问题325

习题12.2327

12.3　NP困难问题的近似算法328

12.3.1 旅行商问题的近似算法329

12.3.2　背包问题的近似算法338

习题12.3341

12.4　解非线性方程的算法342

12.4.1 平分法343

12.4.2　试位法346

12.4.3　牛顿法347

习题12.4349

小结350

跋351

附录A　算法分析的实用公式354

附录B　递推关系简明指南357

习题提示366

参考文献400