算法分析导论 第2版PDF电子书下载

第1章 算法分析 1

1.1为什么要做算法分析 1

1.2算法理论 3

1.3算法分析概述 8

1.4平均情况分析 10

1.5实例：快速排序算法的分析 12

1.6渐近近似 18

1.7分布 20

1.8随机算法 22

参考文献 25

第2章 递归关系 28

2.1基本性质 29

2.2一阶递归 33

2.3一阶非线性递归 35

2.4高阶递归 38

2.5求解递归的方法 42

2.6二分分治递归和二进制数 49

2.7一般的分治递归 57

参考文献 62

第3章 母函数 64

3.1普通型母函数 65

3.2指数型母函数 69

3.3利用母函数求解递归 72

3.4母函数的展开 79

3.5利用母函数进行变换 82

3.6关于母函数的函数方程 84

3.7利用OGF求解三项中值Quicksort递归 87

3.8利用母函数计数 89

3.9概率母函数 93

3.10双变量母函数 96

3.11特殊函数 101

参考文献 107

第4章 渐近逼近 109

4.1渐近逼近的概念 111

4.2渐近展开式 116

4.3处理渐近展开式 123

4.4有限和的渐近逼近 129

4.5欧拉-麦克劳林求和 131

4.6二元渐近 137

4.7拉普拉斯方法 149

4.8算法分析中的“正态”举例 152

4.9算法分析中的“泊松”举例 155

参考文献 159

第5章 分析组合 161

5.1正式的基础 162

5.2无标记类的符号方法 163

5.3有标记类的符号方法 169

5.4参数的符号方法 177

5.5母函数系数逼近 182

参考文献 188

第6章 树 189

6.1二叉树 190

6.2森林和树 192

6.3树和二叉树的组合等价 194

6.4树的性质 200

6.5树算法的例子 204

6.6二叉搜索树 207

6.7随机Catalan树 211

6.8二叉搜索树中的路径长度 216

6.9随机树的附加参数 219

6.10高度 223

6.11树属性在平均情况下的结果总结 229

6.12拉格朗日反演 230

6.13无序树 233

6.14标记树 242

6.15其他类型的树 245

参考文献 253

第7章 排列 256

7.1排列的基本性质 257

7.2排列算法 263

7.3排列的表示法 266

7.4计数问题 271

7.5通过CGF分析排列的性质 275

7.6逆序和插入排序 285

7.7从左到右最小值和选择排序 291

7.8环与原地排列 297

7.9极值参数 300

参考文献 304

第8章 字符串与字典树 306

8.1字符串搜索 307

8.2位串的组合性质 310

8.3正则表达式 320

8.4有穷状态自动机和KMP算法 323

8.5上下文无关的语法 326

8.6字典树 332

8.7字典树算法 336

8.8字典树的组合性质 340

8.9更大的字符表 345

参考文献 347

第9章 单词与映射 350

9.1使用分离链接的散列 351

9.2球与瓮的模型和单词的性质 353

9.3生日悖论与优惠券收集者问题 360

9.4占据限制与极值参数 367

9.5占据分布 372

9.6开放寻址散列法 379

9.7映射 386

9.8整数因子分解与映射 396

参考文献 401