算法详解 卷1 Part 1 算法基础 The basicsPDF电子书下载

第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大Ο表示法 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.42大？表示法 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重温Merge 58

3.2.9 Merge和分离逆序对 60

3.2.10 Merge_ and CountSplitInv 61

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 ClosestSplitPair 74

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.1RecIntMult算法 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重温MergeSort 89

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随机化的QuickSort 121

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理解DSelect 156

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