算法详解 卷1 算法基础

图书标准信息

• 作者 [美]蒂姆·拉夫加登（Tim Roughgarden）
• 出版社 人民邮电出版社
• 出版时间 2019-01
• 版次 1
• ISBN 9787115493521
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 185页
• 字数 200千字

【内容简介】

算法是计算机科学领域*重要的基石之一。算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。
  算法详解系列图书共有4卷，本书是第1卷——算法基础。本书共有6章，主要介绍了4个主题，它们分别是渐进性分析和大O表示法、分治算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题，这为读者的自我检查以及进一步学习提供了较多的便利。
  本书为对算法感兴趣的广大读者提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及在准备面试的应聘者和面试官阅读参考。

【作者简介】

蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷，基于他从2012年开始定期举行的在线算法课程编写。

【目录】

第 1章  绪论1

1.1  为什么要学习算法1

1.2  整数乘法3

1.2.1  问题和解决方案3

1.2.2  整数乘法问题3

1.2.3  小学算法4

1.2.4  操作数量的分析5

1.2.5  还能做得更好吗5

1.3  Karatsuba乘法6

1.3.1  一个具体的例子6

1.3.2  一种递归算法7

1.3.3  Karatsuba乘法9

1.4  MergeSort算法11

1.4.1  推动力11

1.4.2  排序12

1.4.3  一个例子13

1.4.4  伪码14

1.4.5  Merge子程序15

1.5  MergeSort算法分析16

1.5.1  Merge的运行时间17

1.5.2  MergeSort的运行时间18

1.5.3  定理1.2的证明19

1.5.4  小测验1.1～1.2的答案23

1.6  算法分析的指导原则23

1.6.1  第 1个原则：最坏情况分析24

1.6.2  第 2个原则：全局分析25

1.6.3  第3个原则：渐进性分析26

1.6.4  什么是“快速”算法27

1.7  本章要点28

1.8  习题29

挑战题31

编程题31

第 2章  渐进性表示法32

2.1  要旨32

2.1.1  推动力32

2.1.2  高级思维33

2.1.3  4个例子34

2.1.4  小测验2.1～2.4的答案38

2.2  大O表示法40

2.2.1  文本定义40

2.2.2  图形定义40

2.2.3  数学定义41

2.3  两个基本例子42

2.3.1  k阶多项式是O(nk)42

2.3.2  k阶多项式不是O(nk-1)43

2.4  大Ω和大 表示法44

2.4.1  大Ω表示法44

2.4.2  大 表示法45

2.4.3  小O表示法46

2.4.4  渐进性表示法的来源47

2.4.5  小测验2.5的答案48

2.5  其他例子48

2.5.1  在指数中添加一个常数48

2.5.2  指数乘以一个常数49

2.5.3  最大值vs.和49

2.6  本章要点50

2.7  习题51

第3章  分治算法53

3.1  分治法规范53

3.2  以O(n log n)时间计数逆序对54

3.2.1  问题54

3.2.2  一个例子54

3.2.3  协同筛选55

3.2.4  穷举搜索法55

3.2.5  分治法56

3.2.6  高级算法57

3.2.7  关键思路：站在MergeSort的肩膀上57

3.2.8  重温Merge58

3.2.9  Merge和分离逆序对60

3.2.10  Merge_and_CountSplitInv61

3.2.11  正确性61

3.2.12  运行时间62

3.2.13  小测验3.1～3.2的答案62

3.3  Strassen的矩阵相乘算法63

3.3.1  矩阵相乘63

3.3.2  例子（n = 2）64

3.3.3  简单算法64

3.3.4  分治法65

3.3.5  节省一个递归调用67

3.3.6  细节68

3.3.7  小测验3.3的答案69

*3.4  O(n log n)时间的最近点对（Closest Pair）算法70

3.4.1  问题70

3.4.2  热身：1D情况71

3.4.3  预处理71

3.4.4  一种分治方法72

3.4.5  一个微妙的变化74

3.4.6  ClosestSplitPair74

3.4.7  正确性76

3.4.8  辅助结论3.3（a）的证明77

3.4.9  辅助结论3.3（b）的证明78

3.4.10  小测验3.4的答案80

3.5  本章要点80

3.6  习题81

挑战题81

编程题82

第4章  主方法83

4.1  重温整数乘法83

4.1.1  RecIntMult算法84

4.1.2  Karatsuba算法84

4.1.3  比较递归过程85

4.2  形式声明86

4.2.1  标准递归过程86

4.2.2  主方法的陈述和讨论87

4.3  6个例子88

4.3.1  重温MergeSort89

4.3.2  二分搜索89

4.3.3  整数乘法的递归算法90

4.3.4  Karatsuba乘法90

4.3.5  矩阵乘法91

4.3.6  一个虚构的递归过程92

4.3.7  小测验4.2～4.3的答案93

*4.4  主方法的证明94

4.4.1  前言94

4.4.2  重温递归树95

4.4.3  单层所完成的工作96

4.4.4  各层累计97

4.4.5  正义与邪恶：需要考虑3种情况98

4.4.6  预告运行时间上界99

4.4.7  最后的计算：第 一种情况100

4.4.8  迂回之旅：几何级数101

4.4.9  最后的计算：第二种情况和第三种情况102

4.4.10  小测验4.4～4.5的答案103

4.5  本章要点103

4.6  习题104

第5章  快速排序（QuickSort）107

5.1  概述107

5.1.1  排序108

5.1.2  根据基准元素进行划分108

5.1.3  高级描述110

5.1.4  内容前瞻110

5.2  围绕基准元素进行划分111

5.2.1  简易方法111

5.2.2  原地实现：高级计划112

5.2.3  例子113

5.2.4  Partition子程序的伪码115

5.2.5  QuickSort的伪码117

5.3  良好的基准元素的重要性117

5.3.1  ChoosePivot的简单实现118

5.3.2  ChoosePivot的过度实现118

5.3.3  小测验5.1～5.2的答案119

5.4  随机化的QuickSort121

5.4.1  ChoosePivot的随机化实现121

5.4.2  随机化QuickSort的运行时间122

5.4.3  直觉：随机基准元素为什么很好123

*5.5  随机化QuickSort的分析124

5.5.1  预备工作125

5.5.2  分解蓝图126

5.5.3  应用蓝图128

5.5.4  计算比较的概率130

5.5.5  最后的计算132

5.5.6  小测验5.3的答案133

*5.6  排序需要   (n log n)的比较134

5.6.1  基于比较的排序算法134

5.6.2  具有更强前提的更快速排序135

5.6.3  定理5.5的证明136

5.7  本章要点138

5.8  习题139

挑战题140

编程题141

第6章  线性时间级的选择142

6.1  RSelect算法143

6.1.1  选择问题143

6.1.2  简化为排序144

6.1.3  分治法145

6.1.4  RSelect的伪码146

6.1.5  RSelect的运行时间147

6.1.6  小测验6.1～6.2的答案149

*6.2  RSelect的分析150

6.2.1  根据阶段追踪进展150

6.2.2  简化为掷硬币151

6.2.3  综合结论153

*6.3  DSelect算法154

6.3.1  基本思路：中位的中位元素154

6.3.2  DSelect的伪码155

6.3.3  理解DSelect156

6.3.4  DSelect的运行时间157

*6.4  DSelect的分析159

6.4.1  递归调用之外所完成的工作159

6.4.2  一个粗略的递归过程159

6.4.3  30-70辅助结论160

6.4.4  解析递归过程163

6.4.5  先猜后验方法164

6.5  本章要点166

6.6  本章习题166

挑战题167

编程题168

附录A  快速回顾数学归纳法169

附录B  快速回顾离散概率173