《算法设计与分析基础第3版》PDF (美)Anany Levitin

瑾年安好 281 0

《算法设计与分析基础第3版》PDF (美)Anany Levitin

大小 : 20.15 MB |  下载量 : 6 次 |  文件类型 : PDF文档  

信息简介

书名:《算法设计与分析基础第3版》

副标题:《算法设计与分析基础第3版》

作者:(美)AnanyLevitin

类别:计算编程

页数:437

格式:PDF

ISBN:9787302386346

出版社:清华大学出版社

出版日期:2015年01月

内容简介

作者莱维汀基于丰富的教学经验,开发了一套全新的算法分类方法。该分类法站在通用问题求解策略的高度,对现有大多数算法准确分类,从而引领读者沿着一条清晰、一致、连贯的思路来探索算法设计与分析这一迷人领域。本书作为第3版,相对前版调整了多个章节的内容和顺序,同时增加了一些算法,并扩展了算法的应用,使得具体算法和通用算法设计技术的对应更加清晰有序;各章累计增加了70道习题,其中包括一些有趣的谜题和面试问题。

《算法设计与分析基础(第3版)》十分适合用作算法设计和分析的基础教材,也适合任何有兴趣探究算法奥秘的读者使用,只要读者具备数据结构和离散数学的知识即可。

作者简介

作品目录

第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符号42

2.2.4符号42

2.2.5渐近符号的有用特性43

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

2.2.7基本的效率类型45

习题2.246

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

习题2.352

2.4递归算法的数学分析54

习题2.459

2.5例题:计算第n个斐波那契数62

习题2.565

2.6算法的经验分析66

习题2.669

2.7算法可视法70

小结73

第3章蛮力法75

3.1选择排序和冒泡排序76

3.1.1选择排序76

3.1.2冒泡排序77

习题3.178

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

3.2.1顺序查找80

3.2.2蛮力字符串匹配81

习题3.282

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

3.3.1最近对问题83

3.3.2凸包问题84

习题3.387

3.4穷举查找89

3.4.1旅行商问题89

3.4.2背包问题90

3.4.3分配问题91

习题3.493

3.5深度优先查找和广度优先查找94

3.5.1深度优先查找94

3.5.2广度优先查找96

习题3.598

小结100

第4章减治法101

4.1插入排序103

习题4.1105

4.2拓扑排序106

习题4.2109

4.3生成组合对象的算法111

4.3.1生成排列111

4.3.2生成子集113

习题4.3114

4.4减常因子算法115

4.4.1折半查找116

4.4.2假币问题117

4.4.3俄式乘法118

4.4.4约瑟夫斯问题119

习题4.4120

4.5减可变规模算法122

4.5.1计算中值和选择问题122

4.5.2插值查找125

4.5.3二叉查找树的查找和插入126

4.5.4拈游戏127

习题4.5128

小结129

第5章分治法131

5.1合并排序133

习题5.1135

5.2快速排序136

习题5.2140

5.3二叉树遍历及其相关特性141

习题5.3143

5.4大整数乘法和Strassen矩阵乘法144

5.4.1大整数乘法145

5.4.2Strassen矩阵乘法146

习题5.4148

5.5用分治法解最近对问题和凸包问题149

5.5.1最近对问题149

5.5.2凸包问题151

习题5.5153

小结154

第6章变治法155

6.1预排序156

习题6.1158

6.2高斯消去法160

6.2.1LU分解164

6.2.2计算矩阵的逆165

6.2.3计算矩阵的行列式166

习题6.2167

6.3平衡查找树168

6.3.1AVL树169

6.3.22-3树173

习题6.3174

6.4堆和堆排序175

6.4.1堆的概念176

6.4.2堆排序180

习题6.4181

6.5霍纳法则和二进制幂182

6.5.1霍纳法则182

6.5.2二进制幂184

习题6.5186

6.6问题化简187

6.6.1求最小公倍数188

6.6.2计算图中的路径数量189

6.6.3优化问题的化简189

6.6.4线性规划190

6.6.5简化为图问题192

习题6.6193

小结194

第7章时空权衡196

7.1计数排序197

习题7.1199

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

7.2.1Horspool算法201

7.2.2Boyer-Moore算法204

习题7.2207

7.3散列法209

7.3.1开散列(分离链)210

7.3.2闭散列(开式寻址)211

习题7.3213

7.4B树214

习题7.4217

小结218

第8章动态规划219

8.1三个基本例子220

习题8.1224

8.2背包问题和记忆功能226

8.2.1背包问题226

8.2.2记忆化227

习题8.2229

8.3最优二叉查找树230

习题8.3234

8.4Warshall算法和Floyd算法235

8.4.1Warshall算法235

8.4.2计算完全最短路径的Floyd算法238

习题8.4241

小结242

第9章贪婪技术243

9.1Prim算法245

习题9.1249

9.2Kruskal算法250

习题9.2255

9.3Dijkstra算法256

习题9.3259

9.4哈夫曼树及编码260

习题9.4264

小结265

第10章迭代改进266

10.1单纯形法267

10.1.1线性规划的几何解释267

10.1.2单纯形法概述270

10.1.3单纯形法其他要点275

习题10.1276

10.2最大流量问题278

习题10.2285

10.3二分图的最大匹配286

习题10.3291

10.4稳定婚姻问题292

习题10.4295

小结296

第11章算法能力的极限297

11.1如何求下界298

11.1.1平凡下界298

11.1.2信息论下界299

11.1.3敌手下界299

11.1.4问题化简300

习题11.1302

11.2决策树302

11.2.1排序的决策树303

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

习题11.2306

11.3P、NP和NP完全问题308

11.3.1P和NP问题308

11.3.2NP完全问题311

习题11.3314

11.4数值算法的挑战316

习题11.4322

小结323

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

12.1回溯法325

12.1.1n皇后问题326

12.1.2哈密顿回路问题328

12.1.3子集和问题328

12.1.4一般性说明329

习题12.1331

12.2分支界限法332

12.2.1分配问题332

12.2.2背包问题335

12.2.3旅行商问题336

习题12.2338

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

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

12.3.2背包问题的近似算法349

习题12.3352

12.4解非线性方程的算法353

12.4.1平分法355

12.4.2试位法357

12.4.3牛顿法358

习题12.4360

小结361

跋363

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

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

习题提示380

参考文献414

大小 : 20.15 MB |  下载量 : 6 次 |  文件类型 : PDF文档  

标签: 计算编程

发表评论 (已有0条评论)

还木有评论哦,快来抢沙发吧~